[SW정글] 분할정복(🔥), 이진 탐색

 

분할 정복이란

devide & conquer로, 큰 문제를 작은 문제로 나눠 정복하여 큰문제를 해결하는 것이다.

 

나는 이 방식을 모든 알고릐듬 문제에 다 적용시켜 문제를 풀려고 노력한다.

 

예를 들어 백준의 10830 문제를 보자

 

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

문제를 보고 답을 구하기 위해 내가 해야할 것들을 정리한다.

 

위 문제의 경우

 

1. 제곱을 분할 정복으로 빠르게 구하기

2. 행렬의 곱셈

3. 행렬에 1000 나눠주기

 

로 작은문제들로 분할하여 정.복하고 문제를 푼다.

 

import sys

input = sys.stdin.readline

N, B = map(int, input().split())

matrix = [[int(x) for x in input().split()] for _ in range(N)]


# 2 행렬 곱하기
def multi(arr1, arr2):
    squared = [[0] * N for _ in range(N)]
    for x in range(N):
        for y in range(N):
            for i in range(N):
                squared[x][y] += arr1[x][i] * arr2[i][y]
    return squared

# 1 제곱 분할정복으로 풀기
def dc(arr, divide):
    if divide == 1:
        return remain(arr)
    else:
        tmp = dc(arr, divide//2)
        if divide % 2 == 0:
            return remain(multi(tmp, tmp))
        else:
            return remain(multi(multi(tmp, tmp), arr))

# 3 행렬 나머지 연산
def remain(arr):
    for x in range(N):
        for y in range(N):
            arr[x][y] %= 1000
    return arr

answer = dc(matrix, B)


for i in answer:
    for j in i:
        print(j, end=' ')
    print()

 

요런식으로 푼다.

 

 

이진 탐색이란

 

탐색 알고리즘 중에서 빠른 속도를 자랑한다.

 

중간 값을 찾고 찾을 값이 그것보다 크다면 중간을 기준으로 오른쪽을 탐색하고 반대라면 왼쪽을 탐색한다.

정렬되어있는 수, 배열에서 사용가능하다!

 

이진 탐색 문제를 풀면서 느낀점은 찾을 값과 중간값의 유형을 올바르게 매치 시켜야한다는 것이다.(Ex, 값 또는 인덱스, 횟수 등)

 

또한, 다른 사람들의 코드를 보면서 느낀것은 어떤 사람은

 

while left<right :

어떤 사람은 

while left<=right :

를 쓴다.

 

나는 헷갈리지 않기 위해 이런 부분을 통일해야할 필요성을 느꼈다. (사실 팀의 기둥인 0규형이 가르쳐줬다.)

 

그래서 나는 아래와 같이 코드를 통일하여 func부분만 고쳐서 다른 문제에도 적용하려고 한다.

 

아래 문제는 백준의 2110 정답 코드다

 

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

import sys

input = sys.stdin.readline

N, C = map(int, input().split())

homes = [int(input()) for i in range(N)]

homes.sort()


def func(x):
    count = 1
    start = homes[0]
    for i in range(1, len(homes)):
        if homes[i] - start >= x:
            count += 1
            start = homes[i]
    return count

## 주의할 점 ! 초기 값 left는 최소값-1 right는 최대값 +1으로 설정해줘야한다.
left, right = -1, 10**9+1

### !!!!!
while left < right:
    mid = (left + right)//2
    ### !!!!
    # func 증가함수면 < OR <=
	# func 감소함수면 > OR >=
    if func(mid) >= C:
        left = mid + 1
    else:
    	# 위에 while left <= right를 할거면 아래는 right = mid-1을 해줘야 한다.
        right = mid

# return 은 left값 !!
print(left-1)

 

while left<= right보다  left < right를 선택한 이유는

 

left = right일 경우를 안도는 장점이 있지 않을까? 라는 생각으로 선택하게 되었다.

 

또한 python bisect source 또한 위처럼 쓰고 있기 때문에 권위있는 자의 코드를 따라가려고 했따.

 

아래는 python bisect 모듈 소스이다.

 

def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

def bisect_left(a, x, lo=0, hi=None, *, key=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

 

 

어렵다. 그래도 열심히 해보쟈

 

모두들 열코다 ~!🔥🔥🔥🔥