이것저것 코딩하는 블로그

0. Binary Search (이진 탐색) 이란? 업-다운 게임을 생각해보자 (술을 많이 안 먹으면 모를 수도 있다..이 경우엔 검색해보자). 범위 내에서 특정 숫자를 말하면 업, 다운을 이야기하며 맞추면 당연히 모두 읊는 것보다 시간이 덜 소요될 것이다. 이진 탐색과 이 개념은 정확히 일치한다. 배열이 정렬되었다고 가정하자. 이진 탐색은 정렬된 배열에 대해서만 가능하다. 정렬된 배열의 가운데에서 업, 다운 중 하나를 선택하면 왼쪽 혹은 오른쪽으로 이동할 것이다. 이제 이동한 배열의 가운데를 다시 기준으로 업, 다운을 선택하면, 범위가 계속 좁아지며 결국 원하는 대상을 찾을 수 있을 것이다. 만약 원하는 대상이 없다면, 배열의 원소가 하나만 남았을 때도 원하는 대상이 아닐 것이고, 이 때는 찾을 수 없..

0. Heap Sort란? 자료구조인 heap을 이용한 정렬이다. 먼저 heap이 무엇인지 살펴보자. 1) Heap heap은 max-heap, min-heap 두 개로 나눌 수 있다. max-heap을 이해하면 min-heap을 이해하기 쉬우니 max-heap을 살펴보자. heap은 이진 트리의 형태를 띈다. 이진 트리란, 트리 구조를 가지고 있으면서 각 노드가 최대 2개의 자식을 갖는 트리이다. max-heap이란, 부모의 값이 자식의 값보다 항상 큰 이진 트리이다. 따라서 루트 노드는 전체의 최댓값을 갖게 된다. min-heap은 부모의 값이 자식의 값보다 항상 작은 이진 트리이다. 따라서 루트 노드는 전체의 최솟값을 갖게 된다. 2) 이진 트리를 배열으로 구현하기 이진 트리 형태를 떠올리면 배열과..

0. Quick Sort (퀵 정렬) 이란? 기준 (pivot)을 잡아 pivot보다 큰 원소는 뒤에, 작은 원소는 앞에 놓으면서 정렬하는 것이다. 마지막엔 가운데에 pivot을 넣어준다. 그러나 pivot보다 작은 원소, 큰 원소끼리는 정렬되어 있지 않을 것이다. 즉, pivot의 왼쪽, 오른쪽에 대해 다시 정렬을 수행해야 한다는 것이다. 따라서 이도 재귀를 이용한다. [1, 4, 3, 5, 2] 를 맨 오른쪽 원소를 pivot으로 삼아 정렬한다고 하자. 한 번의 pivot을 기준으로 한 분할을 이용하면 다음과 같은 결과가 출력될 것이다. [1, 2, 4, 3, 5] 2의 왼쪽에는 1 하나뿐이므로 더 이상 정렬할 필요가 없다. 따라서 우리는 [4, 3, 5]를 정렬해야 한다. 마찬가지로 가장 오른쪽 원..

0. Merge Sort (병합 정렬) 이란? 병합 정렬이란, 배열을 쪼개서 정렬한 후 다시 그 쪼개진 배열들을 정렬하며 합치는 것을 말한다. 예를 들어, [1, 3, 5, 2] 이라는 배열이 있다고 하자. 이 배열을 반으로 쪼개면 [1, 3], [5, 2] 이 될 것이다. 이들을 각각 정렬하면 [1, 3], [2, 5] 가 된다. 이들을 합치며 정렬한다는 것은, 각각의 원소를 비교하여 작은 것부터 새 배열에 입력하는 것이다. 1 2 이므로 2가 두번째, 3 < 5 이므로 3이 세번째, 마지막에 5가 입력될 것이다. 이를 어떻게 코드로 구현할 수 있을까? 지금 든 예제는 4개여서 반으로 갈라 정렬하는 것이 쉬웠지만, 실제로는 그렇지 않다. 따라서 배열의 원소가 하나..

0. Radix Sort (기수 정렬) 이란? 기수 정렬이란, 맨 뒤에 있는 자릿수부터 해당 자릿수를 기준으로 정렬한 뒤, 한 칸씩 (한 자리씩) 앞으로 이동하며 각 자리수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법이다. 숫자들 간의 자릿수가 다르다면 어떻게 할까? 자릿수가 작은 수의 앞을 0으로 채우면 반드시 작아지게 된다. (ex. 100, 99의 경우 100과 099를 비교하면 마지막에는 가장 높은 자리수와 비교하므로 1과 0이 비교되어 100이 더 크다고 판별된다). 음수가 섞여 있는 경우에는 음수랑 양수를 구분하여 정렬한 후 합치면 된다. 이 때 음수는 절댓값으로 변환하여 비교한 뒤 reverse해주면 정렬된 값을 얻을 수 있다. (ex. -3, -40, -12 ..

0. Insertion Sort (삽입 정렬) 이란? Insertion Sort란, 앞에서부터 순서대로 보면서 앞에 있는 모든 원소가 정렬이 되어있다는 가정 하에 현재 원소의 위치를 적절하게 집어넣는 정렬이다. 앞의 모든 원소가 정렬이 되어있으므로, 현재 위치의 원소가 어디에 들어갈 지 앞의 모든 원소를 한 번만 돌아보면 알 수 있을것이다. 이 과정을 현재 원소가 두번째일때부터 n번째일때까지 반복한다. n개의 원소에 대해 값 삽입을 수행해야 하는데, k번째 원소의 경우 최대 k-1개의 원소를 이동해야 하므로 비교 연산이 1+2+...+(n-1) = n*(n-1)/2번 일어난다. 따라서 시간복잡도는 O(n^2)이다. 1. 구현 n = int(input()) nums = input() num = nums.s..