알고리즘

안녕하세요 허언증입니다. Heap Sort 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리입니다. 힙에는 최대 힙과 최소 힙이 존재 최대 힙은 '부모 노드'가 '자식 노드'보다 큰 경우 일 때. 일단 힙 정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 합니다. 6 => 부모 노드(root) 2,3 => 자식노드 부모노드의 값(6)이 자식노드(2,3) 보다 클 경우 그림 처럼 최 상단에 제일 큰 값이 있는 경우 2 => 부모 노드(root) 1,4 => 자식노드 현재의 경우에는 부모노드에 2가 있고 자식노드에 1,4가 있지만 4는 2보다 값이 더 크기 때문에 서로 교체를 해줘야 힙 형태가 된다. 이를 "힙 정렬"이라고 한다 이진트리가 힙정렬이 완료가 되..

안녕하세요. 허언증 입니다. 저같은 경우 C++로 풀었습니다. python, Java로 안 풀었어요!! 문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net ■ 문제 조건 ■ 시간 제한 : 시간 복잡도 - 시간 3초 메모리 제한 : 공간 복잡도 – 메모리 8MB 정답 비율 : 22% 메모리 ,시간 제한 둘다 고려를 해야 해서 어려운 문제인거 같다. 메모리 오버 에러 당연히 / 시간 오버 에러 당연히 경험했다. 두 가지의 경우를 다 겪고 결국 해결 했다. 다른 분들도 이 글을 보고 참고가 되었으면 합니다!!! 1. 메모리 오버 >..

안녕하세요. 허언증 입니다. 저같은 경우 C++로 풀었습니다. python, Java로 안 풀었어요!! 문제 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 백준(Baekjoon)__11650_좌표 정렬하기 실패코드 #include #include using namespace std; int main(void) { int N; cin >> N; int input[10001][2] = { 0 }; for (int i = 0; i ..

안녕하세요. 허언증 입니다. 저같은 경우 C++로 풀었습니다. python, Java로 안 풀었어요!! 문제 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 백준(Baekjoon)_10828_Stack #include #include #include using namespace std; int main() { int N; cin >> N; stack s; string command; for (int i = 0; i > comma..

안녕하세요. 허언증 입니다. 저같은 경우 C++로 풀었습니다. python, Java로 안 풀었어요!! 문제 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 www.acmicpc.net 백준(Baekjoon)_5585_거스름돈 #include using namespace std;..

안녕하세요. 허언증 입니다. 저같은 경우 C++로 풀었습니다. python, Java로 안 풀었어요!! 문제 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 백준(Baekjoon)_11047_동전 0 #include using namespace std; const int num_MAX = 10; int main() { int kind_of, money; int array[11]; int mok, count = 0, namu = 0; cin >> k..

안녕하세요! 허언증입니다. 버블정렬에 대해 공부 하도록 하겠습니다. 버블정렬(Bubble Sort)? 옆에 있는 값과 비교 후 작은 값을 앞으로 보내면 어떨까? 생각에서 만들어지게 된 알고리즘 입니다. 곧 바로 예시로 한 번 알아보도록 하겠습니다. 1, 5, 3, 10, 4, 7, 9, 2, 6, 8 (정렬되지 않은 숫자 1~10까지의 나열 된 상태입니다) 버블정렬의 방식으로 나열을 시작하면 첫 번째 자리에 있는 1을 기준으로 2번 자리 값과 비교를 하고 작은 수와 자리를 바꿔줍니다. 1은 이미 제일 작은 수 이기도 하고 첫 번째자리에 있으니 변화가 없습니다. 이제는 두 번째 자리와 세 번째 자리와 비교를 합니다. 1, 5, 3, 10, 4, 7, 9, 2, 6, 8 두 번째자리인 5 와 세 번째 자리를..

안녕하세요! 허언증입니다. 선택정렬에 대해 공부 하도록 하겠습니다. 선택정렬(Selection Sort)? 가장 작은 것을 앞으로 이동시키면 어떨까? 생각에서 만들어지게 된 알고리즘 입니다. 곧 바로 예시로 한 번 알아보도록 하겠습니다. 1, 5, 3, 10, 4, 7, 9, 2, 6, 8 (정렬되지 않은 숫자 1~10까지의 나열 된 상태입니다) 선택정렬의 방식으로 나열을 시작하면 첫 번째 자리에 있는 1을 기준으로 2~10번 자리까지 비교를 하고 제일 작은 수와 자리를 바꿔줍니다. 1은 이미 제일 작은 수 이기도 하고 첫 번째자리에 있으니 변화가 없습니다. 이젠 첫 번째 자리를 제외하고 두 번째 자리에 있는 5를 가지고 비교를 시작합니다. 1, 5, 3, 10, 4, 7, 9, 2, 6, 8 3~10번..