Divide And Conquer4 [C/C++] 백준 #2749 피보나치 수 3(분할정복) 피보나치 수에 대한 알고리즘은 점화식에서 출발해서 재귀함수(recursion)를 배울 때 자주 인용되는 것이죠. 재귀함수를 사용하는 방법이 매우 많은 중복이 발생한다는 문제를 거론하면서 동적계획법(Dynamic Programming)을 사용해야 하는 이유를 설명할 때에도 많이 쓰입니다. 재귀함수를 단순하게 이용하면, 시간 복잡도가 O(ϕ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(216)의 값을 흰종이로 두고서 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. 이전 1 다음 728x90
