분할정복

● 분할정복(Divide and Conquer) 한번에 해결하기에 불가능하거나 매우 오래걸리는 문제를 작은 문제로 나눠서(분할) 해결하고 다시 결합하여(정복) 문제를 해결하는 방식 **앞서 포스팅 했던 이분탐색 또한 분할정복을 사용한 알고리즘 Merge sort(병합정렬) 분할정복을 이용한 정렬방법으로 O(NlogN)의 시간복잡도를 가지며 버블정렬, 삽입정렬, 선택정렬 보다 실행시간이 빠르다. (파이썬에 내장되있는 sort함수도 병합정렬) 병합정렬을 통해서 분할정복이 어떤식으로 이루어지는지 알아보자. 정렬을 하기 위해 임의의 무작위 배열 arr = [3, 25, 1, 75, 42, 100, 63, 38] 이 있다고 하자. 이 배열의 Divide 과정은 아래그림과 같다. 배열의 중간을 기준으로 더 이상 나..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 분할정복 알고리즘으로 Z(2X2)모양이 나올때까지 좌표를 분할하여 Z가 되면 탐색을 하였다. 처음에는 좌표를 2차원 배열로 만들어서 직접 분할하였다. 숫자를 다 쓰면서 해당 좌표가 (r,c)이면 프로그램을 종료하게 했지만 시간초과가 떴다. 그래서 좌표를 분할할때 분할한 범위 안에 (r,c)가 없으면 탐색을 아에 하지 않도록 return을 추가해주었다. 하지만 그래도 시간초과가 떠서...다..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 정사각형안에 1만 존재하거나, 0만 존재하면 색종이를 카운트 하는 문제이다. 알고리즘은 분할정복이라고 나와있긴하지만, 문제를 분할한 다음에 다시 합치는 과정이 없기 때문에 그냥 재귀라고 생각해도 충분히 풀수 있는 문제이다. 분할정복을 더 알아보고 싶다면 파이썬의 정렬모듈로 사용되고 있는 병합정렬을 공부해보면 좋다. 풀이는 처음 시작점의 숫자를 저장해두고 탐색하다가 처음 ..