devbelly

문제 https://www.acmicpc.net/problem/1493 알고리즘 분할정복, 그리디 풀이 박스를 큐브로 채워나갈 때, 필요로 하는 큐브의 갯수를 최소화 하는 문제입니다. 단 큐브의 사이즈는 2의 제곱형태로만 주어지는 제약이 있습니다. 큐브길이가 2의 제곱형태로만 주어지는 점부터 살펴봅시다. 만약 이렇지 않았다면, 모든 큐브를 일일히 넣어보는 완전탐색을 해야합니다. 하지만 모든 길이가 배수와 약수 관계를 유지할 때, 무조건 큰 길이부터 넣는 그리디한 전략을 사용할 수 있습니다. 큰 길이의 큐브를 넣어야만 갯수를 최소화 할 수 있고, 예를들어 4x4x4큐브를 사용했다면 굳이 2x2x2큐브들로 그 자리를 대체할 이유가 없죠. 살펴보아야 할 점 중 또 한가지는 큐브길이는 제곱형태로 주어지지만 박스..

문제 https://www.acmicpc.net/problem/2104 알고리즘 분할정복 풀이 유명한 분할정복 문제입니다. $N$제한을 고려하지 않은 채 문제를 풀어보도록 합시다. 이중 포문을 통해 모든 i, j에 대하여 문제에서 요구하는 값을 $N^2$에 해결할 수 있습니다. 하지만 이 문제의 $N$제한은 100000이므로 제곱을 하게 되면 시간초과를 면할 수 없습니다. 문제 제한을 통해 log임을 느낄 수 있습니다. $O(NlogN)$은 시간제한 1초 안에 들어올 수 있는 복잡도입니다. 분할정복으로 해결해보도록 합시다. 분할정복을 처음 접할 때 가장 어려운 부분 중 하나는 재귀를 다루는 부분입니다. 재귀함수를 작성할 시 아직 함수를 다 작성하지 않았음에도 불구하고 작동할 것이라는 믿음을 갖고 작성해야..