본문 바로가기

Divide And Conquer4

[C/C++] 백준 #2749 피보나치 수 3(분할정복) 피보나치 수에 대한 알고리즘은 점화식에서 출발해서 재귀함수(recursion)를 배울 때 자주 인용되는 것이죠.  재귀함수를 사용하는 방법이 매우 많은 중복이 발생한다는 문제를 거론하면서 동적계획법(Dynamic Programming)을 사용해야 하는 이유를 설명할 때에도 많이 쓰입니다.  재귀함수를 단순하게 이용하면, 시간 복잡도가 \(O(\phi^N)\)으로 기하급수로 늘어나지만, 이를 동적 계획법 또는 포워드 프로그래밍(Forward Programming)을 사용하면, 시간 복잡도가 \(O(N)\)으로 급격하게 줄어들 수 있습니다. 하지만 이번 문제는 N 자체가 \(O(N)\) 알고리즘으로 해결하기 어려운 문제입니다.  그래서 분할 정복을 사용해야 하고, 이를 이용하면 시간 복잡도를 \(O(\log.. 2024. 8. 12.
[C/C++] 백준 #2630 색종이 만들기(분할정복) 이번 문제는 분할정복을 이용해서 풀면 어렵지 않게 풀 수 있습니다.  C/C++을 사용하다보면, 반환값을 여러개를 두고 싶은데, 그것이 어렵거나 할 때가 많죠.  색종이 만들기 문제에서는 흰종이와 파란종이를 나누어서 출력을 해주어야 하는데, 그것이 잘 안 되죠. https://www.acmicpc.net/problem/2630 반환값을 여러개가 안 되니까, 제 경우에는 65536(\(2^{16}\))의 값을 흰종이로 두고서 4바이트 정수 1개를 가지고 2바이트 정수 2개를 만들어서 사용했습니다. 분할정복한 결과가 4개의 구역이 모두 같은 색인 경우에는 1개의 종이로 대치하는 부분을 작성했습니다. int s = rec(r, c, v, n); s += rec(r+n, c, v, n); s +.. 2024. 5. 10.
[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++] 백준 #2086 피보나치 수의 합(분할정복) 이번 문제는 피보나치 수열들의 합을 계산하는 것입니다. 언뜻, 피보나치 수열을 구해서 그 합을 구해야 할 것으로 생각할 수 있습니다. 수학식을 유도하는 것이 어려워서인지, 문제의 난이도는 Gold I 단계입니다. https://www.acmicpc.net/problem/2086 2086번: 피보나치 수의 합 제 1항과 제 2항을 1이라 하고, 제 3항부터는 앞의 두 항의 합을 취하는 수열을 피보나치(fibonacci) 수열이라고 한다. 예를 들어 제 3항은 2이며, 제 4항은 3이다. 피보나치 수열의 a번째 항부터 b번째 www.acmicpc.net 조금 생각해보면, 이 수열도 피보나치 수열과 다르지 않다는 것을 알 수 있습니다. 수학적으로 점화식을 이용해서 풀이를 하는 것이라서, 다소 생소할 수가 있습.. 2023. 3. 28.

티스토리툴바