레야몬
7장: 분할 정복 - 3 (195p ~ 205p) 본문
<문제: 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중)>
1. 정당성 증명
- 알고리즘에서 선택한 최댓값보다 더 최댓값이 존재한다고 가정하자(귀류법). 이 때 만약 이 값이 최댓값이라면 알고리즘이 이 최댓값을 선택하지 않았을 수가 없었음을 증명하면 됨.
2. 시간 복잡도 분석
- 두 가지로 나눔과 동시 나눈 것을 선형 탐색하므로 O(nlgn)이다.
- https://www.acmicpc.net/blog/view/12 (이 글에 더 자세하게 나와있다.)
히스토그램에서 가장 큰 직사각형
6549번 문제: 히스토그램에서 가장 큰 직사각형 히스토그램에서 가장 큰 직사각형을 찾는 방법을 알아보겠습니다. 문제 히스토그램에서 모든 막대의 너비는 1이고, 높이는 hi일 때, 가장 넓이가
www.acmicpc.net
<문제: 팬미팅 (문제 ID: FANMEETING, 난이도:상)> - *
'알고리즘 > Algorithmic Problem Solving Strategies' 카테고리의 다른 글
| 7장: 분할 정복 - 2 (180p ~ 194p) (0) | 2022.11.03 |
|---|---|
| 7장: 분할 정복 - 1 (175p ~180p) (0) | 2022.11.01 |
| 6장: 무식하게 풀기 - 2 (165p ~ 173p) (0) | 2022.10.31 |
| 6장: 무식하게 풀기 - 1 (145p ~ 162p) (0) | 2022.10.27 |
| 5장: 알고리즘의 정당성 증명 - 1 (127p ~ 142p) (0) | 2022.10.26 |
Comments