본문 바로가기

분할 정복2

[C/C++] 백준 #2261 가장 가까운 두 점(분할 정복) #2261 문제는 분할 정복의 대표격인, 병합정렬, 퀵정렬, 히스토그램과 함께 자주 나옵니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 분할 정복과 관련한 게시글은 다음과 같습니다. https://sdev.tistory.com/904 [C/C++] 백준 #1780 종이의 개수(분할정복) 이번 문제는 무조건 분할을 한 후에, 그 결과를 토대로 결정을 하게 하는 문제입니다. 결국 분할 정복.. 2023. 4. 19.
[C/C++] 백준 #1725 히스토그램(분할 정복) 히스토그램 문제는, 히스토그램 그래프에서 x축의 빈도의 너비와, y축의 값의 높이 단위 크기가 같을때, 히스토그램 그래프 안에 직사각형의 넓이가 최대가 되는 것을 구하는 문제입니다. 분할정복 문제의 전형적인 경우입니다. 예를 들어서 히스토그램의 값이 [ 3, 2, 3, 4, 2, 3, 4, 1 ]의 값을 가진다고 하면, 이를 히스토그램으로 표현하면 아래와 같습니다. 사람이 본다면 인지적으로 높이 2인 직사각형이 가장 넓을 것이라 할 수 있습니다. 하지만, 히스토그램의 x축 개수가 매우 많다면 사람이 인지적으로 판단하는 것도 힘듭니다. 컴퓨터가 푼다면, 높이 1인 것부터 차례로 찾아볼 수도 있습니다. 히스토그램의 1보다 큰 수가 얼마나 연속되었는지 찾으면 됩니다. 이것이 \(O(N)\) 알고리즘이니, 높이.. 2022. 10. 5.

티스토리툴바