★Divide & Conquer Upper-Intermediate I - 9 Solved★

★ 2630 색종이 만들기 ★

import sys
input=sys.stdin.readline

N=int(input())
W,B=0,0
confetti=[]

def is_check(arr):
    side=len(arr)
    if all(arr[i][j] == 0 for i in range(side) for j in range(side)):
        return 'W'
    elif all(arr[i][j] == 1 for i in range(side) for j in range(side)):
        return 'B'
    else: return 0

def get_confetti(arr,l,W,B):
    if l == 1:
        if arr[0][0] == 0:
            W+=1
            return (W,B)
        else:
            B+=1
            return (W,B)
    else:    
        if is_check(arr) == 'W':
            W+=1
            return (W,B)
        elif is_check(arr) == 'B':
            B+=1
            return (W,B)
        else:
            border = l//2
            arr1,arr2,arr3,arr4=[],[],[],[]
            
            for i in arr[:border]:
                arr1.append(i[:border])
                arr2.append(i[border:])
            for j in arr[border:]:
                arr3.append(j[:border])
                arr4.append(j[border:])
            W,B = get_confetti(arr1,border,W,B)
            W,B = get_confetti(arr2,border,W,B)
            W,B = get_confetti(arr3,border,W,B)
            W,B = get_confetti(arr4,border,W,B)
    return (W,B)


    
for _ in range(N):
    confetti.append(list(map(int,input().split())))

l = len(confetti)

W,B = get_confetti(confetti,l,0,0)
print(W,B,sep='\n')

 

🍴 주어진 정사각형이 모두 1로 이루어져 있는지, 0으로 이루어져 있는지 확인하는 sub-problem으로 분할할 수 있으며, 한 번 확인된, 즉 한 번 해결된 sub-problem은 이후 다시 풀게 되는 경우가 없으므로 분할정복 DAC 알고리즘이라 할 수 있다.

 

🍴 재귀를 사용 시 주의점 - 동일 함수를 재귀적으로 여러 번 쓸 때마다, 변수 W, B가 계속 초기화되므로 새롭게 생기는 sub-problem을 해결할 때마다 W,B 변수에 계속 update해줘야 한다.

---

★ 1780 종이의 개수 ★

import sys
input=sys.stdin.readline

N=int(input().rstrip())
papers=[list(map(int,input().split())) for _ in range(N)]

cnt_dic={'-1':0, '0':0, '1':0}
l=len(papers)

def check_the_same(arr):
    cmp=arr[0][0]
    l=len(arr)
    flag=True
    for i in range(l):
        for j in range(l):
            if arr[i][j] != cmp:
                flag = False
                return (False,2)
    if flag:
        return (True,cmp)

def cut_paper(arr,l):
    if l == 0:
        res,val=True,arr[0]
    else:
        res,val = check_the_same(arr)

    if res:
        if val == -1: cnt_dic['-1']+=1
        elif val == 0: cnt_dic['0']+=1
        else: cnt_dic['1']+=1
        return
    
    else: #if False, recursion
        #divide into 9 pieces
        l=len(arr)
        if l > 0:
            arrays=[[] for _ in range(9)]
            for i in arr[:l//3]:
                arrays[0].append(i[:l//3])
                arrays[1].append(i[l//3:(2*l)//3])
                arrays[2].append(i[(2*l)//3:l])
            
            for i in arr[l//3:(2*l)//3]:
                arrays[3].append(i[:l//3])
                arrays[4].append(i[l//3:(2*l)//3])
                arrays[5].append(i[(2*l)//3:l])

            for i in arr[(2*l)//3:l]:
                arrays[6].append(i[:l//3])
                arrays[7].append(i[l//3:(2*l)//3])
                arrays[8].append(i[(2*l)//3:l])

            for subarr in arrays:
                cut_paper(subarr,l//3)

        return
    
cut_paper(papers,len(papers))

print(cnt_dic['-1'])
print(cnt_dic['0'])
print(cnt_dic['1'])

 

🍴 위와 동일한 전형적인 분할정복 문제로, 분할하고, recursion을 반복해 정복 유형으로 해결한다.

 

🍴 다만, arr의 개수가 1개일 경우, 바로 값을 출력하게 하였고, 전체 -1의 개수, 0의 개수, 1의 개수를 매번 업데이트하며 재귀함수의 매개변수로 넣지 않은 대신, 각 종류의 개수를 딕셔너리 자료형으로 만들어 개수를 업데이트하는 형식으로 코드 진행 / 전체 arr 자체를 쪼개기 보다는, indexing으로 arr의 간격 size를 조절하는 방식으로 진행한다면 더 효율적으로 짤 수 있다.

(for문에서 arr자체를 반복하기 보다, length 사이즈 자체를 반복하는 것이 더 효율적인 것 처럼)

---

★ 1074 Z ★

import sys
N,r,c=map(int,input().split())
size = 2**N
global n
n = 0
i,j=0,0

def if_size_two(i,j):
    if (i,j) == (r,c):
        print(n)
        sys.exit()
    elif (i,j+1) == (r,c):
        print(n+1)
        sys.exit()
    elif (i+1,j) == (r,c):
        print(n+2)
        sys.exit()
    else:
        print(n+3)
        sys.exit()

def divide_into_four(i,j,size):
    global n
    if size == 2:
        if_size_two(i,j)
    else:
        #1
        if i<=r<(i+size//2) and j<=c<(j+size//2):
            divide_into_four(i,j,size//2)
        else:
            n+=((size//2)*(size//2))
		
        #2
        if i<=r<(i+size//2) and j+size//2<=c<(j+size):
            divide_into_four(i,j+size//2,size//2)
        else:
            n+=((size//2)*(size//2))
        
        #3
        if i+size//2<=r<(i+size) and j<=c<(j+size//2):
            divide_into_four(i+size//2,j,size//2)
        else:
            n+=((size//2)*(size//2))
        
        #4
        if i+size//2<=r<(i+size) and j+size//2<=c<(j+size):
            
            divide_into_four(i+size//2,j+size//2,size//2)
        else:
            n+=((size//2)*(size//2))

divide_into_four(i,j,size)

 

🍴 Z 탐색 흐름

→ 위 왼쪽 → 위 오른쪽 → 아래 왼쪽 → 아래 오른쪽 방향 순서로 탐색이 진행된다.

 

🍴 pseudo-code 흐름

① size(정사각형 한 변의 길이)가 2이면 위 Z 순서로 일치하는 (r,c) 파악하고 바로 sys.exit()으로 종료!

② size가 2가 아니라면 4등분 → Z 순서로 위 왼쪽부터 차례대로 target이 있는 지 확인

≫ (1) 있다면 ①부터 다시 재귀 → 있는 곳만 계속 팜 (depth-first search)

≫ (2) 없다면 전역변수 n 그만큼 size를 2로 나눈 값의 제곱을 더하고, 그 다음 방향 탐색 (반드시 target이 4등분한 곳 중 한 군데에 있음)

 

※ 주의점! 4등분할 때 마다 시작점 (i,j)가 계속 바뀌므로 update한 (i,j)를 재귀함수 인자에 넣어주어야 한다

※ 반드시 pseudo-code 흐름을 먼저 그린 다음 코딩 진행하기

 

🍴 시간초과 코드

import sys
N,r,c=map(int,input().split())
size = 2**N
global n
n = 0
i,j=0,0
flag=False

def draw_Z(i,j,size):
    if size==2:
        global n
        if i<=r<=(i+1) and j<=c<=(j+1):
            if (i,j) == (r,c):
                flag = True
                print(n)
                sys.exit()
            elif (i,j+1) == (r,c):
                flag = True 
                print(n+1)
                sys.exit()
            elif (i+1,j) == (r,c):
                flag = True 
                print(n+2)
                sys.exit()
            else:
                flag = True
                print(n+3)
                sys.exit()
        n += 4
        return
    else:
        draw_Z(i,j,size//2)
        draw_Z(i,j+size//2,size//2)
        draw_Z(i+size//2,j,size//2)
        draw_Z(i+size//2,j+size//2,size//2)

draw_Z(i,j,size)

 

→ 너무 많이 깊게 들어간다. 쓸데없이 깊게 들어간다.

 

→ 원하는 target이 예를 들어 35라면, 시간초과 코드는 길이가 2인 정사각형을 차례대로 일일이 다 알아보고 일명 노가다성으로 계속 탐색한다.

→ 하지만 맞힌 코드는 target이 들어간 가장 큰 정사각형 먼저 들어가고, target이 들어간 그 다음 큰 정사각형만 들어가는 등 재귀 호출의 횟수가 현저히 적다(분할 정복을 쓰는 이유)

---

★ 1629 곱셈 ★

import sys
input=sys.stdin.readline
A,B,C=map(int,input().split())

def get_power(a,b,c):
    if b == 1:
        return a%c
    x = get_power(a,b//2,c)

    if b % 2 == 0:
        return ((x%c) * (x%c)) % c
    else:
        return ((x%c) * (x%c) * a)%c

print(get_power((A%C),B,C))

 

🍴 전형적인 '분할 정복을 이용한 거듭제곱' 알고리즘. 별도 포스팅 참조

---

★ 11819 The Shortest does not Mean the Simplest ★

def get_power_by_divisor(a,b,c):
    if b == 1:
        return a%c
    else:
        x = get_power_by_divisor(a,b//2,c)
        if b%2 == 0:
            return ((x%c) * (x%c))%c
        else:
            return ((x%c) * (x%c) * (a%c))%c 
        

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

print(get_power_by_divisor(A,B,C))

 

🍴 1629와 동일

---

★ 13171 A ★

import sys
input=sys.stdin.readline

def get_power_by_divisor(a,b,c):
    if b == 1:
        return a%c
    else:
        x = get_power_by_divisor(a,b//2,c)
        if b%2 == 0:
            return ((x%c) * (x%c))%c
        else:
            return ((x%c) * (x%c) * (a%c))%c 



A=int(input())
X=int(input())
divisor = 1_000_000_007

print(get_power_by_divisor(A,X,divisor))

 

🍴 역시 동일

---

★ 17829 222-풀링 ★

import sys
input=sys.stdin.readline
N=int(input())
arr=[]
for _ in range(N):
    arr.append(list(map(int,input().split())))

def pooling(arr, length):
    if length == 1:
        print(*arr[0])
        sys.exit()
    new_arr = [[10_001]*(length//2) for _ in range(length//2)]
    num = length//2
    for i in range(num):
        start_x,start_y = 0+2*i,-2
        for j in range(num):
            start_y += 2
            a = arr[start_x][start_y]
            b = arr[start_x+1][start_y]
            c = arr[start_x][start_y+1]
            d = arr[start_x+1][start_y+1]
            new_arr[i][j] = sorted([a,b,c,d])[-2]
    pooling(new_arr, num)

pooling(arr,N)

 

🍴 전형적인 분할정복 알고리즘. 분할정복 재귀 코드 쓸 때, 함수 작성 후 (1) 먼저 종료 조건 활용한 코드 → (2) 동일 함수 이름 써서 재귀로 들어가는 코드

 

🍴 분할정복 재귀 코드 작성할 때, 재귀 함수의 인자에 알맞게 들어가게끔 규칙을 찾는 것이 중요! 위 문제는 점점 크기가 작아지므로, 2로 나눈 길이와 문제에 맞는 풀링 연산의 결과를 인자로 넣는 것이 중요하다

---

★ 1992 쿼드트리 ★

import sys
input=sys.stdin.readline

def is_zero_or_one(arr):
    l=len(arr)
    cmp=arr[0][0]

    for i in range(l):
        for j in range(l):
            if cmp != arr[i][j]:
                return False
        
    return str(cmp)


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

def compress(arr,l,ans):
    if l>=2:
        
        res = is_zero_or_one(arr)
        if res:
            ans.append(int(res))
        else:
            ans.append('(')
            if l!=2:
                a,b,c,d=[],[],[],[]
                for i in arr[:l//2]:
                    a.append(i[:l//2])
                    b.append(i[l//2:])
                
                for j in arr[l//2:]:
                    c.append(j[:l//2])
                    d.append(j[l//2:])
                
                compress(a,l//2,ans)
                compress(b,l//2,ans)
                compress(c,l//2,ans)
                compress(d,l//2,ans)
            else:
                ans.extend([arr[0][0],arr[0][1],arr[1][0],arr[1][1]])
            ans.append(')')
        
if N != 1:
    compress(quad_tree,len(quad_tree),ans)
    print(*ans,sep='')
else:
    print(quad_tree[0][0])

 

🍴 정사각형의 한 변의 길이가 2의 제곱수이므로 절반씩 분할해가며 상황에 따라 모두 같으면 숫자를 붙이거나 모두 같지 않으면 (를 붙이고 더 분할해가며 정복하면서 도중에 업데이트 되는 ans list 결과를 출력해주면 된다. (정답 결과를 잘 분석하면 된다)

---

★ 21854 Monsters ★

import sys
input = sys.stdin.readline
MOD = 10**9+7

def get_power(a,b,c):
    if b == 1:
        return a%c
        
    x = get_power(a,b//2,c)

    if b % 2 == 0:
        return ((x%c) * (x%c)) % c
    else:
        return ((x%c) * (x%c) * (a%c))%c

n=int(input())
ks=list(map(int,input().split()))

ans=0
for k in ks:
    if k == 0:
        ans += 1
    else:
        ans+=get_power(2,k,MOD)
print(ans%MOD)

 

🍴 2^k을 분할정복거듭제곱으로 구해서 누적으로 더한 결과를 출력해주면 된다. 이 때 2^k을 MOD로 나눈 나머지를 구하므로, 재귀로 구하는 도중 곱셈의 성질에 따라 도중도중 %MOD 연산을 진행해 구한다.

---