07 분할정복 (7.4~7.7)
7.4 문제 : 울타리 잘라내기
[문제]
너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있다.
울타리를 구성하는 각 판자의 높이가 주어질 때, 울타리에서 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요.
단, 판자의 너비는 모두 1이며 비스듬히 잘라낼 수 없다.
[시간 및 메모리 제한]
프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
[입력]
첫 줄에 테스트 케이스의 개수 C(C≤50)가 주어집니다.
각 테스트 케이스의 첫 줄에는 판자의 수 N(1≤N≤20000)이 주어집니다.
높이는 모두 10,000 이하의 자연수입니다.
[출력]
각 테스트 케이스당 정수 하나를 한 줄에 출력합니다.
이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.
[예제 입력]
3
7
7 1 5 9 6 7 3
7
1 4 4 4 4 1 1
4
1 8 2 2
[예제 출력]
20
16
8
7.5 풀이 : 울타리 잘라내기
[풀이]
○가장 간단한 풀이 : 2중 for문
>> O(n^2)으로 최대 입력 20,000의 경우 시간 내에 해결이 어려움
○분할 정복 알고리즘 : n개의 판자를 절반으로 나누어 두 개의 부분 문제 만들기
>> 세 가지 경우의 수
1. 가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다
2. 가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다
2. 가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.
(1&2는 반으로 나누어 재귀 호출, 3번의 경우 빠르게 답을 구할 수 있으면 완성)
3번의 경우 답은 항상 부분 문제의 경계에 있는 두 판자를 포함한다.
여기서 확장해 나갈 때 오른쪽 / 왼쪽 중 판자의 높이가 더 높은 쪽을 선택하게 하면 된다.
[코드]
☆판자의 높이를 저장한 전역 배열은 다음 입력을 위해 사용 후 초기화 해주어야 한다.
[정당성 증명]
핵심 : 양쪽 부분 문제에 걸쳐 있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳음을 보이는 것
>> 귀류법으로 증명 가능
[시간 복잡도]
분할 : 문제를 항상 절반으로 나눔 O(lg n)
풀이 : 사각형 찾기 → 너비가 2인 사각형에서 n인 사각형까지 하나하나 검사 O(n)
∴ O(nlg n)
[선형 시간 알고리즘]
이 문제는 스위핑 기법과 스택을 결합한 선형 시간 알고리즘으로 풀 수 있다.
또한, 상호 배타적 집합을 사용하여 O(nlg n) 안에 풀 수 있다.
7.6 문제 : 팬미팅
[문제]
아이돌 그룹 멤버들과 팬들이 팬미팅에서 포옹을 한다.
이 때, 남자끼리는 포옹을 하지 않는다고 한다.
아이돌 그룹 멤버들의 성별과 팬들의 성별이 주어질 때 모든 멤버들이 팬과 동시에 포옹하는 경우의 수를 계산하는 프로그램을 작성하세요.
[시간 및 메모리 제한]
프로그램은 10초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
[입력]
첫 줄에 테스트 케이스의 개수 C(C≤20)가 주어집니다.
각 테스트 케이스는 멤버들의 성별과 팬들의 성별을 각각 나타내는 두 줄의 문자열로 구성되어 있습니다.
각 문자열은 왼쪽부터 오른쪽 순서대로 각 사람들의 성별을 나타냅니다.
M은 해당하는 사람이 남자, F는 해당하는 사람이 여자임을 나타냅니다.
멤버의 수와 팬의 수는 모두 1 이상 200,000 이하의 정수이며, 멤버의 수는 항상 팬의 수 이하입니다.
[출력]
각 테스트 케이스마다 한 줄에 모든 멤버들이 포옹을 하는 일이 몇 번이나 있는 지 출력합니다.
[예제 입력]
4
FFFMMM
MMMFFF
FFFFF
FFFFFFFFFF
FFFFM
FFFFFMMMMF
MFMFMFFFMMMFMF
MMFFFFFMFFFMFFFFFFMFFFMFFFFMFMMFFFFFFF
[예제 출력]
1
6
2
2
7.7 풀이 : 팬미팅
[풀이]
○가장 단순한 방법 : 과정을 하나하나 시뮬레이션
>> O(NM-M^2)으로 최대 입력 200,000의 경우 시간 내에 해결이 어려움
○분할 정복 알고리즘 : 곱셈으로 변형 (큰 수의 곱셈과 유사)
멤버들을 하나의 수로, 팬들을 하나의 수로 생각하고
각 자리의 수를 한 명의 사람에 대응시켜 생각한다.
이 때, 여성은 0으로, 남성은 1로 표현하여 남성끼리 만났을 때 1로, 나머지의 경우 전부 0으로 곱셈의 결과가 표현되게 한다.
실제로 숫자를 곱하는 것과 달리 자리 올림이 필요 없으므로
부분 카라츠바 함수의 결과를 그냥 다 더한 후 그 합이 0일 때 포옹을 한다고 생각하면 된다.
[코드]
(카라츠바 함수와 관련된 부분은 [2/19] 게시물에서 보였으므로 생략)
※자리수 생략이라는게 addTo와 subFrom에도 적용되는게 맞을까? subFrom에서 각 자리수에 해당하는 부분이 음수여도 상관 없는건가?
[시간 복잡도]
카라츠바 알고리즘을 사용했으므로 카라츠바 알고리즘의 시간 복잡도와 같다
∴ O(n^lg 3)
'Study > Algorithm Book' 카테고리의 다른 글
| [2/27] 08 동적 계획법 (3) (0) | 2019.02.27 |
|---|---|
| [2/25] 08 동적 계획법 (2) (0) | 2019.02.25 |
| [2/21] 08 동적 계획법 (1) (0) | 2019.02.21 |
| [2/19] 07 분할정복 (1) (0) | 2019.02.19 |
| [2/18] 06 무식하게 풀기 (0) | 2019.02.18 |
