문제를 분할하고 정복한다는 것은?
한 번에 해결하기 어려운 문제가 있다고 합시다.
해당 문제를 해결할 수 있는 작은 문제로 나누고,
작은 문제들을 해결하여 합쳐서
큰 문제를 해결하는 방법론입니다.
예를 들어, 한 번에 먹기 어려운 음식이 있다고 생각해보죠.
보통 사람들에게 귤을 한 입에 먹기란 어려운 일이죠.
그래서 귤을 쪼개서 옆 사람에게 한 입 넣어주고, 본인도 한 입 하게 되죠.
귤 맛있겠다
다음으로, 운동을 통해 살펴봅시다.
만약 살을 뺀다고 했을때, 하루만에 20kg을 뺄 순 없습니다.
운동을 해서 몸을 키운다고 했을때, 근육량을 하루만에 20kg 찌울 순 없겠죠.
그래서 사람들은 1년 이상의 계획을 잡고, 꾸준히 식이요법과 운동을 통해 건강을 관리합니다.
음식을 본인 입에 맞게, 소화할 수 있을 만큼 쪼개서 먹거나
운동을 긴 시간을 잡고 쪼개서 꾸준히 진행함으로
한 번에 해결하기 어려운 문제를 작게 나눠서 해결해나갑니다.
알고리즘 문제에서도 마찬가지 입니다.
한 방에 해결하기 어려운 문제를
내가 해결할 수 있는 작은 단위까지 문제를 분할해서 정복한 후
해결한 문제들을 합쳐서 큰 문제를 해결하는 절차를 가집니다.
컴퓨터로 문제를 해결하는 상황에서 분할정복은?
이 또한 실생활 예를 통해 살펴보도록 합시다.
첫번째는, 자원과 분할정복을 통해 시간적 이득을 취하는 상황입니다.
지금 당신은 돈이 필요하여 피자박스 접기 알바를 시작했습니다.
사장은 10,000개 단위의 피자박스를 접어야 돈을 준다고 합니다.
10,000개의 피자박스를 혼자 접을 경우 10시간이 걸린다고 가정합시다.
이를 4명에서 나눠서 접을 경우 2.5시간이면 10,000개를 접을 수 있겠죠?
위 예제에서 나온 "피자박스 접기" 행동을 "프로그램"이라고 생각합시다.
"사람"은 해당 프로그램을 실행시키는 "컴퓨터"가 되겠죠.
같은 행동을 하는 여러 컴퓨터를 만들어서 분할정복을 하는 방식을
병렬처리라고 합니다.
주로, 빅데이터 처리를 하는데에 Map-Reduce를 구현하는데에 사용되는 방식입니다.
두번째로, 탐색 공간을 분할정복을 통해 줄여서 시간적 이득을 취하는 상황입니다.
당신은 사람과 대화를 할때, 상대방이 열받으면 매우 기뻐하는 침착한 사람입니다.
어떤 말을 해야 상대방이 열만 받고 나와의 관계를 유지하는지를 알아내는 것이
이 삶을 즐기는데 매우 중요한 포인트 입니다.
선 넘는 발언을 할 경우, 나와 관계가 멀어지거나 나에게 해를 가할 수 있습니다.
너무 약한 발언을 할 경우, 내가 재미가 없고, 상대방 반응 또한 재미가 없습니다.
따라서, 상대방이 열받지만 나에게 해가 없고,
나는 매우 즐거운 선을 농담 몇 마디를 통해 찾아야합니다.
처음에 내가 생각하는 선을 넘지않는 발언과 매우 순한 발언을 준비합니다.
그 중간 정도인 발언을 해서 상대방 반응을 살핀 뒤
적정선을 찾아 계속해서 시도합니다.
만약 내 발언의 수위를 숫자로 표현한다면,
숫자에 해당하는 각각의 발언들이 존재할 것입니다.
가장 위험한 발언이 10, 가장 온순한 발언이 1이 되겠죠.
그 중간인 5의 발언을 해보고, 상대방의 반응을 살펴봅니다.
상대가 화내지 않는다면 5에서 더 높은 수위의 발언을 진행합니다.
이때도 앞과 마찬가지로 5와 10 중 가운데 수인 7의 발언을 해봅니다.
만약 상대가 화를 냈다면 7보다 낮은 6의 발언을 해봅니다.
수위가 1인 발언부터 10인 발언까지 순차적으로 했다면 10의 발언이 소모됩니다.
이와 달리, 이분 탐색을 통해 발언의 수위를 찾아서 3번의 발언이 소모되었습니다.
이처럼 수열에서 특정 수를 찾아야하는 일이 있을때,
수열이 정렬된 상태라면 가운데 숫자와 특정 수를 비교해봄으로
가운데보다 앞쪽 숫자들을 봐야할지, 가운데보다 뒷쪽 숫자들을 봐야할지 결정할 수 있습니다.
이분 탐색 문제들을 예로 들 수 있습니다.
세번째로, 연산 횟수를 분할정복을 통해 줄여서 시간 이득을 취합니다.
다시 한 번 귤을 데려와서 설명하겠습니다.
귤 하나를 까서 한꺼번에 입에 넣으면,
제한된 입 크기로 인해 먹는데 걸리는 시간이 10이라고 합시다.
한꺼번에 입에 넣지않고, 반을 쪼개서 2번에 걸쳐 먹는 시간이 8이 걸립니다.
작게 쪼개서, 입에 넣고, 먹는 작업처럼
분할하고, 정복하고, 결합하는 작업을 통해
그냥 문제를 푸는 것보다
더 빠르게 문제를 풀 수 있습니다.
합병 정렬, 최근접 점의 쌍 구하기 문제를 예로 들 수 있습니다.
그래서 언제 써먹을까?
주로 하는 일이 똑같은데 매우 많이 반복되는 경우 사용됩니다.
각각의 상황에 대한 패턴
Map-Reduce
Input
– Two matrices, A and B
▪ Map
– Input: <[A|B], i, j, value>
– Output: <key={i,j}, value=[Aij|Bij]>
▪ Reduce
– Input: <key, a list of values={Aij, Bij}>
– Output: <key={i,j}, value=Aij+Bij>
- 맵 함수의 입력데이터를 정의한다.
- 리듀스 함수의 킷값을 정의한다.
- 맵 함수에서 출력할 키-값 쌍을 정의한다.
- 리듀스 함수를 정의한다.
프랙탈
재귀
이분 탐색
수의 범위, 좌표 범위, 작업 범위
블록화
분할, 정복, 결합
주로 2분할인데,
= 왼쪽, 오른쪽
빼놓지않고 생각해줘야하는 부분
= 왼쪽과 오른쪽 사이
정복시 나이브하게 풀 때의 근본 연산 적용
결합시 원하는 문제해결 최종 상태를 생각
예시 문제
WxH의 격자판에서 K-목이 몇 개 완성되었는지 찾으시오.
1은 바둑돌이 놓인 칸, 0은 아무것도 없는 칸이다.
Brute-force
- (1, 1)부터 (H, W)까지 2중for문을 통해 탐색
- 1을 발견했을시 왼쪽, 아래, 대각선(왼쪽아래, 오른쪽아래), 4방향으로 K개 탐색 시작
- 복잡도는 O(WHK)
Divide-and-conquer
- W를 기준으로 반으로 쪼갬
- 왼쪽, 오른쪽 영역에 Brute-force 로직 시행
- 왼쪽 오른쪽 사이 영역 중 봐야할 범위는 2K
- 사이 영역에 대해 Brute-force 로직 시행
- 복잡도는 O(HKlogW)
마무리
분할정복을 하면 좋을 상황에 적용을 잘 시켜야합니다.
분할정복은 주로 3가지 문제로 귀결됩니다.
- 탐색 공간 버리기: 이분탐색
- 그림 그리기: 프랙탈
- 쪼개서 해결하고 합치기: 합병 정렬, 최근접 점의 쌍 구하기, 히스토그램
(더 있다면 댓글로 공유해주시면 감사하겠습니다!)
만약 분할정복을 애매하게 사용했다간 정말 고통스러울 수 있습니다.
주로 재귀함수로 코드를 작성하기때문에
함수 정의가 제대로 되지않는다면, 디버깅하기 어렵습니다.
완전히 모든 공간이 탐색되었는지도 잘 확인해야합니다.
참고한 자료
Map-Reduce 패턴: 빅데이터처리 수업, 김영훈 교수님
합병정렬 복잡도 계산: [알고리즘] 합병 정렬(merge sort)이란
분할정복 패턴: [알고리즘] 분할정복 방법 - 이진 탐색, 퀵 정렬 알고리즘
최근접쌍 및 분할정복 개념 자체: 8. 분할 정복 알고리즘 (Divide and Conquer)
다음 시간 예고
Dynamic Programming 에 대해서 알아봅시다.
