개념 완전탐색은 알고리즘에 입문하는 사람들이 가장 처음으로 접하는 내용일것입니다. 그만큼 어려운 내용은 아니며, 말 그대로 완전히 탐색하는 것입니다. 영어로는 brute-force라고 하는데, 이것을 번역해보면 "무식하게 풀기"라는 뜻입니다. 구현 완전탐색을 할 때 사용되어지는 방식은 크게 두가지로 볼 수 있습니다. 1. Iterative 2. recursion 1번은 for문을 이용한 풀이 이고 2번은 재귀 호출을 이용하여 푸는 방법입니다. 예를 들어, 1부터 n까지의 합을 구하는 코드를 구성해보겠습니다. // iterator // 조건 : n >=1 // 1~n의 합을 반환한다. int sum(int n) { int ret = 0; for (int i = 1; i < n; ++i) ret += i; ..

원리 1. 배열 리스트 중 하나를 선택한다. 이 원소를 피벗이라고 함. 2. 피벗을 기준으로 피벗 앞에는 피벗보다 작은 모든 원소들이 오고 피벗 뒤에는 피벗보다 큰 원소가 옴 3. 분할 : 리스틀 피벗을 기준으로 두 리스트로 나눈다. 4. 분할된 리스트들에서 1-3번 과정을 반복한다. 위와 같은 과정을 반복한다면 매번 분할시 피벗으로 한 원소의 위치를 정할 수 있으므로 모든 수를 정렬할 수 있는 것은 자명합니다. 앞서 포스팅한 병합정렬에서와 마찬가지로 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 분할 정복을 모른다면 공부하고 읽는 것을 권장드립니다. 하지만 포스트를 통해서 이해는 할 수 있습니다. [ 16, 11, 6, 19, 12, 2, 2, 10 ] pivot값은 맨앞의 값..

원리 1. 정렬할 배열을 사이즈가 1이 될때까지 반으로 나눈다. (분할) 2. 나눌 수 없을때까지 나눈뒤 정렬을 한다. (정복) 3. 정렬 한 결과를 병합한다. (병합) [ 16, 11, 6, 19, 12, 2, 2, 10 ] 정렬하기에 앞서 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 모르더라도 이번 기회에 직접 이해해 보도록 하겠습니다. 분할은 배열을 절반씩 나누어서 사이즈가 1이 될때까지 나눈 것입니다. 그리고 정렬을 하고 병합을 하는 식으로 구성되어있습니다. 방식은 쉽게 이해하실 수 있습니다. 그렇다면 왜 굳이 분할을 해서 다시 합치면서 정렬을 해야할까요? 이는 아래 시간복잡도를 알아보면서 이해해보도록 하겠습니다. 구현 template vector MergeSort(co..