분할정복 2

정글사관학교 18일차 TIL: MOO 게임(#5904), 문자열 폭발(#9935), 스카이라인(#1933)

오늘 2주차 시험에서는 1시간 반 동안 겨우 1문제 풀었다. 공부할 때도 엄청 빡셌지만 어찌어찌 익혔다는 느낌이 없잖았는데 결과가 이러니 참담하다 싶지만..! 그래도 한 문제 푼 게 어딘가! 아자자! 잘했다! 한 걸음씩 가는 거지! 1. MOO 게임(#5904) 문제 링크는 여기. 도저히 어떻게 접근해야 좋을지 몰라, 맨 처음에는 아예 수열 자체를 구해버리려고 했다. 10^9를 넘는 가장 작은 수열을 뽑으려고 해봤는데 대략 n이 10~20 사이에서 될 것 같더라! 문제는 n=12를 넣을 때부터 연산이 뻗는다는 느낌이 들기 시작하더니 n=15쯤 가니 허송세월하고 있더라. 이렇게는 도저히 못 풀겠다 확신만 하고 끝남..^_^ 지훈이의 풀이를 공부한 내용을 정리하자면, 이 문제는 재귀로 이루어진 점화식을 길이..

정글사관학교 15일차 TIL: 분할 정복 - 곱셈, 히스토그램, 행렬 제곱, 가장 가까운 두 점

0. 목차 1. 분할 정복 정리 2. 곱셈 3. 히스토그램에서 가장 큰 직사각형 4. 행렬 제곱 5. 가장 가까운 두 점 1. 분할 정복 정리 분할 정복 알고리즘은 그 자체로 해결할 수 없는 문제를 작은 문제로 쪼개서 해결하는 방법이다. 예시로는 정렬 알고리즘 중에서 퀵 정렬이나병합 정렬(merge sort), 이진 탐색 등이 있다. 방식은 아래와 같다. 1. Divide 주어진 문제를 잘 쪼개서 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때까지 나눈다. 2. Conquer 각 하위 문제를 재귀적으로 해결한다. 이때, 하위 문제를 더 이상 나눌 수 없는 상황이 되면 종료 조건을 설정하고 해결. 3. Combine Conquer한 문제를 통합해서 원래 문제의 답을 구한다. 대략 재귀랑 비슷한 방식인..