분할정복 문제 및 풀이 (Python)

 

코테 준비를 위한 알고리즘 공부 순서 

 위 링크에서 분할정복 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 

 

 

11. 분할정복

• 분할정복 알고리즘 (Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 
• 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과  이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다.

설명 출처

 

문제

(❌ 표시는 혼자 못푼 문제)

 

 

1. 2630번 색종이 만들기 (실버2)  문제링크

문제 해석

전체 종이의 크기는 NxN 

종이를 자르는 규칙은

- 모두 같은 색으로 칠해져 있지 않으면 가로와 세로 부분을 잘라서 N/2 x N/2로 나눈다.

- 나누어진 종이에 대해서도 모두 같은색이 아니면 똑같은 크기의 네개의 종이로 나눈다.

이 과정으로 잘라진 종이가 모두 하얀색 or 모두 파란색 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

잘라진 하안색 종이와 파란색 종이의 개수를 구하여

제한: 1초 128MB

 

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

 

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

 

코드

56ms

def f(x, y, k):

    if k == 1:
        colorCount[arr[x][y]] += 1
        return

    color = arr[x][y]
    sameColor = True
    for i in range(x, x + k):
        for j in range(y, y + k):
            if arr[i][j] != color:
                sameColor = False
                break

    if sameColor:
        colorCount[color] += 1
        return

    k = k // 2
    f(x, y, k)
    f(x, y + k, k)
    f(x + k, y, k)
    f(x + k, y + k, k)


colorCount = [0, 0]
N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

f(0, 0, N)

print(colorCount[0])
print(colorCount[1])

 

2. 1992번 쿼드트리 (실버1)  문제링크

문제 해석

0,1 압축

모두 0이면 압축결과는 0, 모두 1이면 압축결과는 1

왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래 (0011) ->

0 0

1 1

N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

제한: 2초 128MB

 

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

 

출력

영상을 압축한 결과를 출력한다.

 

코드

52ms

def f(x, y, k):

    if k == 1:
        print(arr[x][y], end='')
        return

    color = arr[x][y]
    sameColor = True
    for i in range(x, x + k):
        for j in range(y, y + k):
            if arr[i][j] != color:
                sameColor = False
                break

    if sameColor:
        print(color, end='')
        return

    k = k // 2

    print("(", end='')
    f(x, y, k)
    f(x, y + k, k)
    f(x + k, y, k)
    f(x + k, y + k, k)
    print(")", end='')


N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input())))

f(0, 0, N)

 

3. 1780번 종이의 개수 (실버2)  문제링크

문제 해석

NxN 행렬 종이

-1,0,1 중하나가 저장되어있다.

모두 같은 수가 아니면 9등분하자. 각 잘린종이에 대해서도 앞의 규칙을 반복하자.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

제한: 2초 256MB

 

입력

첫째 줄에 N(1 ≤ N ≤ 3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

 

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

 

코드

2808ms

def f(x, y, k):

    if k == 1:
        colorCount[arr[x][y]] += 1
        return

    color = arr[x][y]
    sameColor = True
    for i in range(x, x + k):
        for j in range(y, y + k):
            if arr[i][j] != color:
                sameColor = False
                break

    if sameColor:
        colorCount[color] += 1
        return

    k = k // 3
    f(x, y, k)
    f(x, y + k, k)
    f(x, y + k + k, k)

    f(x + k, y, k)
    f(x + k, y + k, k)
    f(x + k, y + k + k, k)

    f(x + k + k, y, k)
    f(x + k + k, y + k, k)
    f(x + k + k, y + k + k, k)


colorCount = [0, 0, 0]
N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

f(0, 0, N)

print(colorCount[-1])
print(colorCount[0])
print(colorCount[1])

 

❌ 4. 1629번 곱셈 (실버1)  문제링크

1시간 반, 풀이 본 문제. 참고링크

https://velog.io/@grace0st/%EA%B3%B1%EC%85%88-%EB%B0%B1%EC%A4%80-1629%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC

문제 해석

자연수 A를 B번 곱한 수를 알고싶다.

구하려는 수가 매우 커질 수 있으므로 C로 나눈 나머지를 구하자.

제한: 0.5초 128MB

 

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

코드

236ms

def f(M):
    global A, C

    if M == 1:
        return A % C
    
    tmp = f(M//2) % C
    if M % 2 ==0:
        return tmp * tmp % C
    else:
        return tmp * tmp * A % C


A, B, C = map(int,input().split())

dp = {}

print(f(B))

 

DP를 쓸려고 했던 코드

굳이 아래처럼 dp에 저장해두지 않아도 된다. 위 코드처럼 값이 한번만 계산해서 반환한값으로 풀수 있는 문제이기 때문

def f(M):
    global A, C

    if M in dp:
        return dp[M]
    
    dp[M//2] = f(M//2) % C
    if M % 2 ==0:
        dp[M] = dp[M//2] * dp[M//2] % C
    else:
        dp[M] = dp[M//2] * dp[M//2] * A % C

    return dp[M]


A, B, C = map(int,input().split())

dp = {}

dp[0] = 0
dp[1] = A % C
print(f(B))

 

DP썼다가 시간초과난 코드

f(M//2)호출을 한번만해서 받은값으로 다 사용하면되는데,

뒤에 같은값을 호출했기때문에 시간초과가났다.

그리고 M =M-1을 하지 않아도 홀수라도 M//2하면 원하는 결과가 나올 수 있었기에 M  = M-1연산이 없어도 된다.

def f(M):
    global A, C

    if M in dp:
        return dp[M]

    if M % 2 ==0:
        dp[M] = f(M//2) * f(M//2) % C
    else:
        M = M-1
        dp[M] = f(M//2) * f(M//2) * A  % C

    return dp[M]


A, B, C = map(int,input().split())

dp = {}

dp[0] = 0
dp[1] = A
print(f(B))

 

 

5. 11401번 이항계수3 (실버1)  문제링크

- 페르마의 소정리 알아야하는 거라서 패스