분할정복
분할 정복 알고리즘이란 분할하고 정복하는 것이다! 이게 무슨 소리냐? 분할 정복은 아래의 단계를 따른다.
단계 1. 문제를 더 작은 문제로 쪼갠다.
단계 2. 쪼갠 문제 각각을 해결한다.
단계 3. 해결한 작은 문제들을 병합하여 큰 문제를 해결한다.
이를 탑 다운 방식이라고 한다.
Top-down방식은 큰 문제를 작은 문제로 분할하고, 작은 문제를 해결한 결과를 이용해 큰 문제를 해결하는 방식이다. (위에서 설명한 그대로이다.)
탑 다운 방식은 재귀 함수를 이용하여 구현할 수 있다. 참고로 재귀함수로 구현 가능한 것은 대부분(아마 전부?) 스택 + 반복문으로 구현이 가능하다.
분할정복 알고리즘 장점
분할 정복 알고리즘의 장점으로, 어려운 문제를 다소 쉽게 해결 할 수 있다는 점이 있다.
또한 작은 각 부분을 모듈화해서 표현 가능하다는 장점이 존재한다.
분할정복 알고리즘 단점
분할 정복 알고리즘의 단점으로, 메모리 소비가 많다는 것이 있다. 분할된 작은 문제들을 별도의 공간에 저장해야 하기 때문이다. 또한 재귀함수를 이용하기 때문에 반복이 불필요하게 많아질 수 있으며, 구해낸 해가 최적의 해가 아닐 수 있다.
대표적인 분할 정복 알고리즘
대표적인 분할정복 알고리즘으로는 병합 정렬(Merge sort), 퀵 정렬(Quick sort), 이분탐색(BinarySearch) 등이 있다.
분할정복 관련 백준 문제 모음
https://www.acmicpc.net/step/20
분할정복 - 이분탐색
역시 설명에는 예제가 빠질 수 없다. 이 글은 무엇보다 몇년 뒤, 내가 모든 것을 잊은 채 다시 봐도 한눈에 배운 걸 떠올리기 위함이므로 가능한 쉽고 구체적으로 기술한다.
이분탐색이란?
이분 탐색이란 데이터가 절렬되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 여기에서는 정렬된 배열에서 특정 값의 인덱스 번호를 찾아내도록 구현하였다.
이분탐색 방법
1. 배열의 중앙값을 선택한다. 만약 해당 값과 찾는 값이 같으면 반환한다.
2. 중앙값을 기준으로 배열을 왼쪽과 오른쪽으로 나눈다.
위의 과정을 값을 찾을 때까지 반복한다.
현재 미드 값 : 12
현재 미드 값 : 22
현재 미드 값 : 87
현재 미드 값 : 45
인덱스 위치 : 11
문제를 작게 생각해보자. 1개의 배열이 있다면 해당 값이 정답이다. 해당 값이 mid이기 때문이다. 만약 2개의 배열이 있다면? 배열 크기가 2이니 1번이 미드값, 0번이 left가 될 것이다. 만약 찾는 값이 mid라면 바로 출력, 그렇지 않다면 return binarySearch(arr, left, mid-1, findingValue);을 사용한다.
해당 함수로 들어가면 현재 mid-1의 값이 right값이 된다. 즉, left == 0, right == 0, mid또한 0이므로, 당시의 mid값이 출력된다.
이분탐색 그림
나는 예전부터 재귀함수가 이상하게 바로 와닿지 않았다. 다른 무엇보다 함수가 콜 되는 순서가 직관적이지 않다고 생각되기 때문이다. 당장 생각하기에는 왼쪽 정렬 재귀함수, 오른쪽 정렬 재귀함수 순으로 되어있다면, 단순히 왼쪽 정렬, 오른쪽 정렬 순으로 된다, 이겠지만. 함수 콜과 리턴의 순서가 머릿속에 바로 그려지지 않는다. 그렇기에 오늘 제대로 정리를 하고자한다.
아마 아래 그림을 보면 나같이 평소 재귀함수를 쓰면서도 확실히 안 와닿는 사람들에게 도움이 될 것이라고 확신한다.
즉 위 코드를 그대로 도식화하면 아래와 같은 형식이 되겠다.
우선 mid값인 12를 findingValue와 비교한다. 그 후, findinfValue가 더 크기에 오른쪽을 기준으로 다시 함수를 실행.... 이 과정을 반복한다.
결국 mid가 45라는 것을 알게 되면, return을 반복하며 원래 함수로 돌아가게 되는 형식이다.
이분탐색의 시간복잡도
사실 학교에서 배우는데도 시간복잡도를 계산하기 다소 난해한 점이 있었다. 이분탐색의 시간 복잡도에 대한 설명은 아래와 같다.
우선 처음에는 확인해야 할 요소가 배열의 크기, 즉 N이다. 그 이후 1번 깊이 들어가면 확인해야 할 요소의 크기가 반이 된다.
그 이후 2번 깊이에 들어가면 또 반이 된다. 즉 N * (1/2) * (1/2)가 된다.
이를 k번(끝까지) 반복하면, 아래의 식을 얻을 수 있다. N*(1/2)^k = 1
왜냐하면 마지막에는 결국 요소의 크기가 1일 테니까.(그림을 보면 마지막에 요소가 하나 남았을 때 해당 값이 mid와 일치하여 반환된다.)
양 변에 2^k를 곱한 후, log2를 밑으로 취하면 아래 식을 얻을 수 있다.
즉, 이분탐색의 시간복잡도는 O(logN)이다.
나의 의문
이는 매 순간 모든 요소를 검사하는 경우이므로 O(logN)이라고 표현된다.
여기서 내가 느낀 의문점은 이것이었다. 매 순간 배열의 모든 값을 탐색한다면 배열의 크기만큼 시간복잡도가 더해지는 것이 맞겠으나, 알고리즘상 그렇지 않다. 짜는 알고리즘마다 다르겠으나, left, right, mid와 관련된 비교 연산, 대입 연산 몇 개만 있을 뿐이다. 아직 내가 시간 복잡도에 대한 개념이 부족해서 그러리라 생각한다.
아무튼 결론을 말하자면 매순간마다 요소 크기만큼 시간복잡도가 더해지는 것은 어림값이다. 또한 O를 쓰기 때문에 아무리 늦어도 해당 요소 시간 안에는 찾을 수 있다는 의미를 가진다.
다시 말해, 알고리즘을 정확히 판단하지 않고 매호출마다 함수가 가질 수 있는 값을 어림잡아서 최대의 경우 N번의 시간 복잡도를 가진다고 기술하고 있는 것이다.
분할정복 - 합병정렬
이번에는 합병정렬이다. 합병 정렬이야말로 분할정복 알고리즘의 대표적인 정렬 알고리즘이라고 할 수 있다. 합병정렬은 각 요소를 쪼개서 다시 합치는 방식으로 작동한다.
분할하고 – 정복하고 – 병합하는 그야말로 분할정복 그 자체라고 할 수 있다. 아래 그림을 보면 이해가 될 것이다.
이 알고리즘 역시 이분 탐색과 비슷하게 mid값을 기준으로 좌우로 나눠서 파고들었다가 종료 조건이 되면(left == right, 즉 요소가 1개인 경우) 병합한다.
병합의 경우 미드를 기준으로 배열 왼쪽(left ~ mid)과 오른쪽(mid+1 ~ right)를 비교해 차례대로 차곡차곡 작은 순서로 채워나간다.
이곳에서 중요한 것이 바로 merge함수이다. 당장 보면 우선 미드를 기준으로 왼쪽으로 다파고들고, 그 다음 오른쪽으로 파고든다. 종료 조건은 left가 right보다 크거나 같은 경우이다. 즉, 현재 요소가 딱 하나만 남았다는 의미이다.
이렇게 모두 분할하고 나면 merge를 비로소 호출하게 된다.
merge에서는 임시 배열을 생성(코드에서는 요소 갯수가 4개이므로 그냥 4로 하였다)하며, 작은 left배열과 right배열로부터 값부터해당 배열을 채운다. 이를 설명하자면
while (i <= mid && j <= right) { //왼쪽에서 미드까지, 혹은 미드+1부터 right까지 반복
if (arr[i] < arr[j]) {// left의 현재 검사중인 값이 right의 검사중인 값보다 작다면
while (i <= mid) { //left값을 마저 모두 할당
마지막 부분을 하는 부분은, left와 rigt을 비교해서 할당하다보면 left나 right배열이 종료 조건(mid에 닿거나, right에 닿음)을 만족하게 된다. 그렇다면 left배열이나 right배열 중 남겨지는 요소가 있는데, 이를 임시 배열에 할당하는 것이다.
이렇게 막 할당해도 괜찮은 것이, left나 right역시 left는 left내에서 정렬된 상태이고 right는 right내에서 정렬된 상태이기 때문이다. 왜냐하면 merge함수는 가장 작은 단위 즉, 나누어진 요소가 1개일 때부터 불러지기 때문이다.
사실 합병 정렬 역시 한 눈에 파악하기는 쉽지 않다고 생각한다. 위 코드는 아래의 순서를 따른다. 각 부분마다 순서와 역할을 기술하였다.
(녹색 글자는 mid임을 나타낸다)
즉, 배열을 쪼개고, 다시 거슬러 올라가며 병합하여 마지막에 펑션을 콜한 마지막 부분에서 최종 병합을 한다.
+)
나는 처음 위 쪼개고 병합하는 그림을 보고 바로 코드를 떠올리기 힘들었는데, 그 이유를 생각해보니 이랬다. 그림만 보자면 마지막으로 쪼개진 부분에서 병합을 하고 있다. 즉, 재귀함수의 마지막 깊이에서 병합을 하는 듯 보인다.
그러나 실제로는 마지막 깊이에서는 더 이상 파고 들 곳이 없음을 (종료 조건임을) 확인하고 돌아오며, 해당 재귀함수를 콜한 부분에서 병합 처리를 하고 있다. 즉 마지막 1개의 요소씩만 남기는 것은 확인하는 것일 뿐, merge함수를 부르는 것 자체는 그 이후이다.
물론 이렇게 말해도 1개가 남도록 쪼갠 후 합치는 게 맞긴 하다. 그러나 이전 DFS등 깊이 파고 들 때마다 항상 종료 조건이 한단계 위에 걸리는가 아래에 걸리는가가 헷갈려 본격적으로 정리해보았다. 이젠 헷갈리지 않도록.
합병정렬 시간복잡도
합병 정렬의 시간 복잡도를 계산해보겠다.
합병 정렬의 시간 복잡도를 계산할 때에는 일반적으로 분할 과정을 고려하지 않는다. 이유는 분할 과정은 단순히 배열을 반으로 나누기만 하며, 실제 정렬 작업이 이루어지지 않기 때문이다. 물론 분할 단계에서도 엄밀히 따지면 상수의 시간 복잡도를 가진다.(펑션 콜 등) 그러나 시간 복잡도 표기에서 상수시간은 무시되므로 계산하지 않는다.
k가 분할 횟수, N이 비교 대상이라고 생각한다면, n은 2^k임을 알 수 있다. 즉 아래의 식이 성립한다.
위의 그림으로 생각해보자면, k = 0(분할이 0)이면 요소의 개수(비교 대상)가 1개이다. 반면, k=2일때는 비교횟수가 4임을 알 수 있다.
여기서 아래 식을 얻을 수 있다.
이렇게 된다.
여기서 k는 각 단계(깊이)라고 하였다.
여기에 각 깊이마다 merge함수를 호출하므로, 해당 함수의 시간 복잡도를 곱해야한다.
크기가 1인 부분 2개를 합병하는 데에는 최대 2번의 비교 연산이 필요하다.
크기가 2인 부분 2개를 합병하려면? 최대 4번의 비교 연산이 필요하다. 즉 최대 현재 요소의 개수만큼 비교 연산을 함을 알 수 있다. 따라서 각 단계마다 N의 시간 복잡도가 추가된다.
즉, 최종적으로는
빅 오 표기법으로 아래의 시간 복잡도를 얻게 되는 것이다.
'컴퓨터 > 알고리즘:자료구조' 카테고리의 다른 글
| [자료구조] 그래프 자료구조 정리 및 구현/BFS, DFS 구현 코드 및 설명 (0) | 2022.12.10 |
|---|---|
| [자료구조] C++트리 설명 및 구현(이진트리)/이진트리 구현 (0) | 2022.11.28 |
| [자료구조] C++ list자료구조 정리/list 함수/list예시 (0) | 2022.11.03 |
| [자료구조] C++ vector자료구조 정리/vector 함수 (0) | 2022.10.27 |
| [자료구조] c++ 배열(STL Array)의 각종 사용 방법/동적 할당, 함수 파라미터, 2차원 배열 (0) | 2022.10.02 |
댓글