알고리즘

분할정복법 분할정복법이란 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할(Divide)하고, 각각의 문제들을 순환적으로 해결(정복, Conquer)하고, 작은 문제의 해들을 합병(Merge)하여 원래 문제에 대한 해를 구하는 방법이다. 분할정복법에는 합병정렬(merge sort), 퀵정렬(quick sort) 등이 있다. 1. 합병정렬(Merge sort) 합병정렬의 작동 원리는 다음과 같다. 데이터가 저장된 배열을 절반으로 분할한다. 순환적으로 배열을 분할 후 정렬한다. 정렬된 두 개의 배열을 합쳐 전체를 정렬한다. 합병 정렬에서는 배열이 주어지면 이를 순환적으로 분할하여 정렬(정복)한 후 다시 합병하는 과정을 거친다. 배열을 분할하여 정렬하고 이를 병합하는 것을 반복할 때, 단계의 높이는 $..

1. Selection sort (선택 정렬) 선택 정렬의 작동 원리 리스트에서 최소값을 찾는다. 최소값을 찾으면, 배열의 맨 앞 원소와 자리를 교체한다. 루프에서 맨 앞의 원소를 제외한 후 다시 루프를 돈다. 배열에서 어떤 값 하나를 선택해서 교체한다고 하여 선택 정렬이라고 한다. 이는 최소값이 아닌 최대값에도 작동한다. 최대값을 중심으로 정렬하는 경우, 배열의 맨 뒤 원소와 자리를 교체하며 루프를 돈다. 위 예시에서 최대값인 37을 찾았으므로 맨 뒷자리와 교체한다. 그렇다면 37은 정렬된 것이므로 제외하고, 나머지에 대해 다시 루프를 돈다. 나머지 중의 최대값인 29를 찾으면, 맨 뒷자리를 제외한 부분 중 가장 뒷자리인 13의 자리와 교체한다. 이후 모두 정렬될 때까지 반복한다. void select..