알고리즘/시작하기
2020. 4. 23.
분할 정복 (Divide and Conquer)
분할 정복은 큰 문제를 분할하여 단순한 부분 문제로 만든 다음, 각 부분 문제의 답으로부터 전체 문제의 답을 이끌어내는 방식의 알고리즘입니다. 역시 분할 정복 자체만으로 풀 수 있는 문제는 그렇게 많지 않지만, 분할 정복은 다른 많은 알고리즘들의 기본 아이디어가 됩니다. 분할 정복으로 풀 수 있는 문제들의 예를 몇가지 살펴보도록 합시다. https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어..
