알고리즘 문제 해결 전략을 읽고
(p.175 ~ p.205)
CH 07. 분할정복
7.1 도입
"분할 정복은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있습니다."
"분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 냅니다."
첫 문장을 처음 읽었을 때는 이게 무슨 말인가 싶었는데, 바로 나오는 두 번째 문장을 읽으니 무슨 의미인지 바로 파악할 수 있었다. 전체를 부분으로 나누어 각 부분에 대한 답을 계산한다는 점에서 각개 격파라고 말한 것이었다.
분할 정복을 이용하는 알고리즘들의 구성 요소
- 문제를 더 작은 문제로 분할하는 과정
- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
- 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제
7.2 문제: 쿼드 트리 뒤집기
7.3 풀이: 쿼드 트리 뒤집기
쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집을 그림을 출력하는 프로그램
- 쿼드 트리가 재귀적으로 정의되어 있기 때문에 쿼드 트리를 압축하거나 해제할 때 재귀 호출로 이를 구현한다.
- 모든 압축을 풀고 메모리에 저장하는 대신 압축을 푼 결과를 곧장 생성한다.
7.4 문제: 울타리 잘라내기
7.5 풀이: 울타리 잘라내기
울타리가 주어졌을 때, 울타리의 일부에서 가장 큰 직사각형을 출력하는 프로그램
- 가운데를 기점으로 왼쪽 오른쪽을 나누어서 직사각형이 왼쪽에서만 만들어지는지, 오른쪽에서만 만들어지는지, 두 부분에 걸쳐있는지를 확인한다.
- 왼쪽 또는 오른쪽에서만 만들어지는 경우에는 재귀 호출을 통해 구하고, 두 부분에 걸쳐있는 경우엔 사각형을 확장하는 방식으로 계산하여 구해준다.
7.6: 문제: 팬미팅
7.7: 풀이: 팬미팅
멤버들의 성별과 팬들의 성별이 주어졌을 때, 모든 멤버들이 포옹을 하는 횟수를 출력하는 프로그램
- 주어진 성별을 1과 0으로 구분한 뒤 곱셈을 통해 답을 구한다.
