[C++] 분할 정복 & 재귀 정리

 

최근 백준 문제를 푸는데, 분할 정복 & 재귀 알고리즘을 사용하는 문제가 있는데 못 풀어서

정리를 해야할 것 같아서 개념 정리를 한다.

 

2630번: 색종이 만들기

위 문제는 분할 정복 & 재귀의 아주 간단한 문제이다.

 

분할 정복이란?

분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 빠른 정렬이나 합병 정렬로 대표되는 정렬 알고리즘 문제와 고속 푸리에 변환(FFT) 문제가 대표적이다. 출처 : 위키피디아 - https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그림으로 이해해 보자면 다음과 같다.

 

분할 정복 알고리즘을 사용해서 정렬하는 합병 정렬의 예시. 출처 - https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

위 사진은 분할 정복을 사용하는 합병 정렬 알고리즘의 사진을 예로 든 것이다.

가장 최소 단위로 쪼갠 후에 정렬을 시켜주고 다시 각 부분들을 합치면서 정렬을 시키는 것이다.

이렇게 하면 O(n log n)의 시간복잡도를 가지게 된다.

• log n : 나누고(log n), 합치는(log n) 데 걸리는 시간.
• n : 해당 데이터를 몇 개를 읽는가? 위 그림에서는 한 줄마다 n개씩 읽는다.

-> 따라서 n개의 데이터를 읽는 것을 2 * log n번 반복하므로, O(n log n)이라고 할 수 있다.

 

분할 정복의 예시를 보았고, 이제 위에서 설명한 색종이 만들기 문제를 봐보자.

문제를 보면, 1*1, 2*2, 4*4, 8*8, ... 의 2^i * 2^i의 칸이 모두 같은 색일 경우엔

그 종이를 하나의 종이로 자른다고 되어있다.

색종이가 모두 같은 색인지는 위 그림처럼 확인이 가능하다.

1. 맨 처음에 한 장의 종이가 있을 때, 만일 다른 칸이 하나라도 있다면 4등분한다. 다른 칸이 없다면 그냥 그종이를 해당 색의 종이로 만든다.
2. 만일 다른 색이 있어 4등분했다면, 자른 4장을 각각 한 장의 종이라고 생각하고 1번으로 돌아간다.

1, 2번을 반복해서 해결해주면 된다. 이렇게 큰 문제(하나의 색종이)를 분할해서(4등분) 풀 수 있게 된다.

그리고 문제의 가로, 세로의 크기가 2의 n승으로 주어지므로 해당하는 방법으로 풀 수 있다. 

사용한 stl과 변수

코드는 간단하다. 사용한 변수는

가로, 세로의 크기 widthHeight를 입력받고 board 배열에 색종이의 색에 정보를 입력받는다.

후에 하얀색종이의 개수를 whiteCnt에, 파란색종이의 개수를 blueCnt에 저장한다.

 

분할 정복하는 재귀 메서드

현재 위치에서의 색을 입력받고, 다른 색이 있는지를 확인하는 same 변수를 만든다.

그리고 현재 위치에서 사이즈까지 칸들을 확인했을 때, 다른색이 있다면 same 변수를 false로 만든다.

그리고 same 변수가 false라면, 색종이를 4등분한다.

그리고 2 * 2의 size를 1로 자르면, 이중 for문을 들어가지 않으므로 해당 색의 색종이의 개수가 증가되게 된다.

 

메인함수

메인함수에서는 문제의 입력들을 입력받고 분할정복 메서드를 호출한 후,

결과값을 출력한다.

 

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인 가능하다.

 

분할 정복 & 재귀는 다른 알고리즘과 달리 한번 정리할 필요가 있을 것 같아서 정리했다.