초코레

힙(heap)을 사용하여 정렬하는 알고리즘 힙은 '부모 값 >= 자식 값' 라는 조건을 만족하는 완전이진트리이다. 완전이진트리의 특징은 '완전이진' 상태이다. 완전 : 부모는 자식을 왼쪽부터 추가하는 모양을 유지한다는 뜻 이진 : 부모가 가질 수 있는 자식의 개수는 최대 2개라는 뜻 따라서 힙의 가장 위쪽에 있는 루트가 가장 큰 값이 된다. 힙은 형제의 대소 관계는 정해져 있기 않기 때문에 부분순서트리(partial ordered tree)라고도 한다. 힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 관계는 다음과 같다. 부모는 a[(i - 1) / 2] 왼쪽 자식은 a[i * 2 + 1] 오른쪽 자식은 a[i * 2 + 2] 힙 정렬은 '가장 큰 값이 루트에 위치'한다는 특징을 이용하는 정렬 알고리즘..

배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘 먼저 배열을 앞부분과 뒷부분으로 나눈다. 이때 앞뒤의 각 배열을 정렬할 때는 다시 병합 정렬을 적용한다. 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다. 배열의 요소 개수가 2개 이상인 경우에 배열의 앞부분과 뒷부분을 각각 병합 정렬로 정렬하고 병합한다. java.util.Arrays 패키지에서 배열을 정렬하는 클래스 메서드인 sort를 제공한다. 기본 자료형의 배열을 정렬하는 sort 메서드는 퀵 정렬 알고리즘을 개선한 것으로 안정적이진 않다. 클래스 객체 배열을 정렬하는 sort 메서드는 병합 정렬을 개선한..

가장 빠른 정렬 알고리즘 중 하나 피벗을 기준으로 피벗보다 작은 요소로 이루어진 부분과 피벗보다 큰 요소 이루어진 부분으로 나눔을 반복함으로써 최종적으로 정렬 된다. 즉 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹의 개수가 1이 되면 정렬을 마친다. 서로 이웃하지 않고 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않은 알고리즘이다. 시간 복잡도는 O(n log n) 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간 복잡도가 증가하는 경우도 있다. 최악의 시간 복잡도는 O(n^2)이 된다. 배열을 두 그룹으로 나누기 피벗 이하의 요소를 배열 왼쪽으로 옮긴다. a[pl] >= x 가 성립할 때까지 pl을 오른쪽으로 스캔 피벗 이상의 요소를 배열 오른쪽으로 옮긴다. a[pr] pr..

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법 퀵 정렬이 고안되기 전까지 가장 빠른 알고리즘으로 알려져 있었다. 4칸만큼 떨어진 요소를 모아 그룹을 4개로 나누어 정렬하는 방법을 '4-정렬'이라고 한다. 4-정렬 → 2-정렬 → 1-정렬을 적용하면 정렬을 마치게 된다. 4-정렬, 2-정렬로 조금이라고 정렬에 가까운 상태로 만든 다음 마지막으로 단순 삽입 정렬을 수행하여 정렬을 마친다. 여러 개의 그룹으로 나누어 정렬하는 이유는 단순 삽입 정렬의 장점은 살리고 단점은 보완하기 위해서이다. 셸 정렬 과정에서 수행하는 각각의 정..

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 열의 '알맞은 위치에 삽입'하는 작업을 n - 1회 반복하여 정렬하는 알고리즘 2번째 요소부터 선택하여 진행한다. 선택한 요소의 왼쪽에 이웃한 요소가 더 크면 그 값을 선택한 요소에 대입하고 앞으로 이동하면서 이 작업을 반복한다. 그러다가 선택한 요소 값 이하의 요소를 만나면 그 보다 앞쪽은 검사할 필요가 없으므로 해당 위치에 선택한 요소 값을 대입한다. 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적인 알고리즘이다. 시간 복잡도는 O(n^2) 장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다. 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다. 1234567891011//단순 삽입 정렬stat..

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다. 안정된 정렬이란 같은 값을 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 안정되지 않은 알고리즘은 정렬 후에 같은 값의 요소의 순서가 바뀔 수도 있다. 시간 복잡도는 O(n^2) 단순 선택 정렬의 교환 과정 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택한다. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다. 1 2 3 4 5 6 7 8 9 10 11 // 단순 선택 정렬 static void selectionSort(int[] a, int n) { for (int i = 0; i

이웃한 두 요소의 대소 관계를 비교/교환을 반복하여 최종적으로 배열을 정렬시키는 알고리즘 6 4 3 7 1 9 8 먼저 오른쪽 끝에 있는 두 요소부터 비교/교환한다. 오름차순으로 정렬한다면 왼쪽 요소 값이 오른쪽 요소 값보다 클 때 교환한다. 그 다음 오른쪽에서 2, 3번째 요소를 비교/교환한다. 이 작업을 첫 번째 요소까지 반복한다. 길이가 n인 배열에서 n - 1회 비교/교환을 하면 가장 작은 요소가 왼쪽 끝으로 이동한다. 이런 하나의 사이클을 패스(pass)라고 하며, 첫 번째 패스가 끝나면 두 번째 패스는 왼쪽 끝으로 이동한 요소를 제외한 배열에 대해 비교/교환을 한다. 두 번째 패스의 비교 횟수는 첫 번째 패스보다 정렬한 요소가 하나 줄었기 때문에 1회 적은 n - 2회이다. 모든 정렬이 끝나려..

재귀 알고리즘에 대한 예제로 자주 등장하며 문제는 아래와 같다. 서로 공격하여 잡을 수 없도록 8개의 퀸를 8 x 8 체스판에 놓으세요. (퀸은 서 있는 지점에서 체스판으로 어떤 지점으로든 여덟 방향으로 직선 이동이 가능하다.) 퀸을 배치하기 위해 다음과 같은 규칙을 세울 수 있다. [규칙 1] : 각 열에 퀸을 1개만 배치한다. → 가지 뻗기로 퀸을 배치하는 조합을 나열 [규칙 2] : 각 행에 퀸을 1개만 배치한다. → 분기를 한정하기 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법을 한정(bounding) 조작이라고 하고, 가지 뻗기와 한정 조작을 조합하여 문제를 풀어 가는 방법을 분기 한정법(branching and bounding method)이라고 한다. 1 2 3 4 5 6 7 8 9..

문제 해결 방법 중에서 가장 유명한 재귀적 알고리즘 하노이의 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법 퀵 정렬(quick sort)이나 병합 정렬(merge sort)도 분할 정복 알고리즘이다. 분할 정복 전략은 다음과 같이 동작한다. 기본 단계를 찾는다. 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾는다. 재귀로 배열의 합계 구하기 기본단계 : 원소의 개수가 0이면 합계는 0을 반환한다. 재귀단계 : 기본단계가 될 때까지 대상이 되는 배열의 크기를 줄여서 보낸다. 12345678910pydef sum(arr): if len(arr) == 0: return 0 return arr[0] + sum(arr[1:]) def main():..

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에 옮기는 문제 모든 원반이 규칙에 맞게 첫 번째 기둥에 쌓여있고 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 한다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다. 3개의 기둥을 각각 시작 기둥, 중간 기둥, 목표 기둥이라고 부르고, 가장 큰 원반을 최소의 단계로 목표 기둥으로 옮기려면 가장 먼저 그룹(가장 큰 원반을 제외한 원반들)을 중간 기둥으로 옮겨야 한다. 다시 그룹 중에서 가장 큰 원반을 제외한 원반을 그룹으로 보고 같은 방식으로 옮긴다. 이 방식으로 반복하여 원반이 N개인 하노이의 탑 문제를 해결할 수 있다. 123456789101112131415//하노이의 탑publi..