[문제풀이] 분할정복 정복기

오늘날 우리들이 풀어야할 문제는 단순하지 않다.

어떠한 problem을 해결에 많은 자원과 시간이 들 때,
우리는 sub problem으로 나눠 문제의 크기를 줄일 수 있다. range를 줄이거나 division을 나눠 문제의 크기를 나누는 것 이 분할 정복이다.

개념적인 요소로 대표적인 백준 문제로 간단히 알아보자 관련 풀이 포스트

주어진 문제를 반으로 나눈다

값이 있을 범위로 줄여가며 찾을 값을 반복해서 찾는다.

BFS(Binary First Search) 이분탐색과 같이 problem 을 range를 줄어 시간 복잡도 O(nlogn)을 가진다.

import sys

def bfs_search(left,right,target):
    if left > right:
        return 0;
    mid = (left+right)//2   
    if arr1[mid] == target:
        return 1

    elif arr1[mid] > target:
        return bfs_search(left,mid-1,target)
    elif arr1[mid]  < target:
        return bfs_search(mid+1,right,target)
num1 = int(sys.stdin.readline())

arr1 = list(map(int,sys.stdin.readline().split(' ')))

arr1.sort()
#print(arr1)

num2 = int(sys.stdin.readline())
arr2 = list(map(int,sys.stdin.readline().split(' ')))
a_len = len(arr1)
for i in arr2:
    print(bfs_search(0,a_len-1,i))    

위 코드를 설계하는데도 3시간 언저리 걸렸다.

분할 정복의 문제를 해결할 때 핵심은
분할 조건과 sub division으로 나눌 때, 조건과 배열에 누락이나 겹치는 부분이 없어야 하는게 핵심으로 본다.

Brute Force에 문제에서 divide and conquer을 이용하면 많은 문제의 리소스 절약이 가능하다.