새싹프로그래머의 이야기

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

문제: 루트가 없는 트리가 주어졌을 때, 루트를 1로 하여 각 노드의 부모 노드를 출력하는 문제 입니다.

풀이 방법: bfs 

풀이 코드:

import sys
import heapq

n = int(input())

graph = [[] for _ in range(n+1)]

for _ in range(n-1):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

data = []
visited = [False] * (n+1)

def bfs():
    q = [1]
    visited[1] = True
    while q:
        parent = heapq.heappop(q)
        for node in graph[parent]:
            if not visited[node]:
                visited[node] = True
                heapq.heappush(data,(node,parent))
                heapq.heappush(q,node)

bfs()

while data:
    print(heapq.heappop(data)[1])

풀이 설명:

for _ in range(n-1):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

먼저 방향성이 없는 노드의 2개가 주어지므로, 다음과 같이 graph에 양방향으로 저장해주었습니다.

data = []
visited = [False] * (n+1)

최종적으로 값을 출력하기 위한 data를 담기 위해서 data라는 Array를 선언해주었습니다.

그리고 bfs 탐색에서 방문 여부를 저장하기 위한 visited Array를 선언했습니다.

 bfs 동작하는 방식을 보면 다음과 같습니다.

def bfs():
    q = [1]
    visited[1] = True
    while q:
        parent = heapq.heappop(q)
        for node in graph[parent]:
            if not visited[node]:
                visited[node] = True
                heapq.heappush(data,(node,parent))
                heapq.heappush(q,node)

bfs를 통해 노드를 탐색했는데, 제일 핵심되는 부분은 탐색을 하면서 (현재 노드, 현재 노드의 부모 노드) 정보를 data라는 배열에 heapq 모듈을 통해 담은 것입니다.

최종 출력 값의 요구하는 점이 2번째 노드부터 순서대로 출력하는 것입니다.

따라서, heapq 모듈의 heapq.heappush()는 (현재 노드, 현재 노드의 부모 노드) 의 형식으로 저장하게 되면 현재 노드 기준 오름차순 정렬을 해서 저장을 해주므로 heapq 모듈을 활용하였습니다. (또한 log의 시간복잡도를 가지므로, 시간복잡도 측면에서도 우수하다는 이점도 있습니다.)

저희는 1을 루트로 하기로 했으므로, 큐의 역할을 하는 배열에 1을 넣고 탐색을 시작합니다.

for node in graph[parent]:
    if not visited[node]:
        visited[node] = True
        heapq.heappush(data,(node,parent))
        heapq.heappush(q,node)

1부터 노드를 탐색하며 방문하지 않은 노드에 대해서 처리를 진행해주는데 graph의 index로 들어가는 값이 부모 노드, graph[index] 안에 담긴 값이 index의 자식 노드 라고 볼 수 있습니다.

이를 바탕으로 앞서 말씀드린 것과 같이, 이와 같이 탐색과 데이터 저장을 동시에 진행하였습니다.

while data:
    print(heapq.heappop(data)[1])

마지막으로 다음과 같이 최종 값들을 출력해주었습니다.

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

문제: 가장 긴 바이토닉 부분 수열을 출력하는 문제

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys

n = int(input())
array = list(map(int,sys.stdin.readline().rstrip().split()))

dp = [1]*(n+1)
af = [1] *(n+1)

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j] >= dp[i]:
            dp[i] = dp[j] + 1

for i in range(n-1,-1,-1):
    for k in range(n-1,i-1,-1):
        if array[i] > array[k] and af[k] >= af[i]:
            af[i] = af[k] + 1

for i in range(n+1):
    dp[i] += af[i]

print(max(dp)-1)

풀이 설명:

결국은 바이토닉 수열이란 1 < k < n 을 만족하는 숫자 k,n 이 있을 때   1 ~ k번째 수까지 오름차순, k ~ n번째 수까지는 내림차순이 되는 수열을 말합니다.

따라서 저는 k번째 수가 있을 때,

k번째 수까지 구할 수 있는 오름차순 수열의 최대 길이를 구하고

수열 끝에서부터 k번째 수 까지 역순으로 보았을 때 만들 수 있는 오름차순 수열의 최대 길이를 구한 다음 두 값을 더하는 방식으로 코드를 구현하였습니다.

dp = [1]*(n+1)
af = [1] *(n+1)

먼저, k번째 수로 만들 수 있는 수열의 길이를 저장하기 위해 1로 초기화한 array를 만듭니다.

1로 초기화한 이유는 1개의 수로 길이가 1인 수열을 만들 수 있기 때문입니다.

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j] >= dp[i]:
            dp[i] = dp[j] + 1

array[ i ]로 만들 수 있는 최대 길이의 오름차순 길이는 array[ i ] 보다 작은 수 중 제일 큰 수로 만들 수 있는 길이의 + 1 입니다.

따라서, i 번째 수로 만들 수 있는 수열의 값을 구하기 위해 0 ~ i -1 번째 까지 탐색하여 array[ i ] 보다 작은 수를 찾고 그 작은 수로 만들 수 있는 수열의 길이가 array[ i ] 번째 수로 만들 수 있는 수열의 같거나 길 경우 +1 을 하여 dp에 저장해줍니다.

이렇게 되면, 다음과 같이 동작되게 됩니다.

i = 0 일 때, 제일 앞 노드이므로 아무런 동작이 일어나지 않습니다.

i = 1 일 때, 앞에 10인 노드가 있으므로 [10, 20]인 길이가 2짜리 수열을 만들 수 있습니다.

따라서 array[1] > array[0] 가 성립하고, dp[0] >= dp[1]이 성립하므로 dp[1] = dp[0] + 1  = 2도 성립합니다.

i = 2일 때는 다음과 같습니다.

먼저 j = 0일 때, 10을 만나게 되면 30 > 10이고 , dp[0]  > = dp[2] 이므로  dp[2] = 2가 됩니다.

[ 10, 30 ]인 수열을 만들 수 있으므로 맞죠.

j = 1일 때, 20을 만나게 되면 30 > 20이고, dp[1] >= dp[2] 이므로 dp[2] = 3이 됩니다.

즉, 최종적으로 [10,20,30] 인 수열로 만들 수 있는 오름차순 수열의 최대 길이를 구하게 됩니다.

for i in range(n-1,-1,-1):
    for k in range(n-1,i-1,-1):
        if array[i] > array[k] and af[k] >= af[i]:
            af[i] = af[k] + 1

수열 [30,20,10] 이 있으면 10 -> 30 으로 가는 방향으로 오름차순 수열 길이를 계산하는 코드입니다.

역순으로 탐색했을 뿐 원리는 위와 같습니다.

for i in range(n+1):
    dp[i] += af[i]

print(max(dp)-1)

10 20 30 20 10 이란 수열이 있을 때,

dp에는 10 20 30을 의미하는 값인 3이 저장되어있을 것이고

마찬가지로 af에도 30 20 10을 의미하는 값인 3이 저장되어 있을 것입니다.

그럼 30이 이중으로 세어진 것이므로 최대 값에 -1을 더해준 값을 출력해줍니다.

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

DP.. 정복까진 아니더라도 어느정도 풀 수 있는 정도로까지 올리기도 만만치 않네요..

아직 알고리즘 개념에 대한 이해가 부족한 것인지 컴퓨팅적 사고력이 부족한 것인지 조금 더 스스로 되돌아보고 부족한 부분을 찾아봐야겠습니다.

문제: 주어진 수열에서 가장 길게 증가하는 부분 수열의 길이를 구하는 문제입니다.

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys

n = int(input())
array = list(map(int,sys.stdin.readline().rstrip().split()))

dp = [1]*(n+1)

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j]+1 > dp[i]:
            dp[i] = dp[j]+1

print(max(dp))

풀이 설명:

dp = [1]*(n+1)

첫번째로 모든 수열의 길이는 자기 자신만 해도 길이가 1이 되므로 길이를 저장할 배열 dp를 1로 초기화 해주었습니다.

그럼 수열의 길이는 어떻게 구할까요? 

예를 들어, 10 20 30 40 50 인 수열이 있다고 해보겠습니다.

10으로 만들 수 있는 수열은 1이 되겠죠.

그럼 20으로 만들 수 있는 수열은 자신보다 작은 수인 10을 통해 {10, 20} 을 만드는 것입니다.

30으로 만들 수 있는 수열은 자신 보다 작은 수인 [10,20]을 통해 {10, 20, 30}을 만든 것이구요.

그럼 다음과 같은 결론을 얻을 수 있습니다.현재 수로 만들 수 있는 제일 긴 수열의 길이는 자신보다 작은 수 중에서 제일 큰 수 (현재 값이 30인 경우, 20을 의미함.)로 만들 수 있는 수열의 길이 + 1이라는 것을요.

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j]+1 > dp[i]:
            dp[i] = dp[j]+1

따라서, 코드를 다음과 같이 구현하였습니다.

현재 값( array[ i ] )보다  작은 값 ( array [ j ] )이 있을 경우, dp[i] = dp[j] + 1로 해주었습니다.

다만 조건문에 dp[ j ] + 1 > dp[ i ]라는 조건을 담아, dp[ j ] 에 해당되는 수열의 길이 중 제일 큰 값이 dp [ i ]에 담기도록 하였습니다.

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

문제: 이진 트리가 주어졌을 때, 전위 순회 / 중위 순회 / 후위 순회 결과를 출력하는 문제 입니다.

풀이 방법: 3가지 트리 순회

풀이 코드:

import sys

n = int(input())
binaryTree = dict()

for _ in range(n):
    root,left,right = sys.stdin.readline().rstrip().split()
    binaryTree[root] = [left,right]

def preorderTraversal(node):
    if node != '.':
        print(node,end='')
        for newNode in binaryTree[node]:
            preorderTraversal(newNode)

def inorderTraversal(node):
    if node != '.':
        newNode1, newNode2 = binaryTree[node]
        inorderTraversal(newNode1)
        print(node,end='')
        inorderTraversal(newNode2)

def postorderTraversal(node):
    if node != '.':
        for newNode in binaryTree[node]:
            postorderTraversal(newNode)
        print(node,end='')

preorderTraversal('A')
print()
inorderTraversal('A')
print()
postorderTraversal('A')

풀이 설명:

binaryTree = dict()

for _ in range(n):
    root,left,right = sys.stdin.readline().rstrip().split()
    binaryTree[root] = [left,right]

해당 노드를 직접 방문하여 어떠한 처리를 해주는 것이 아닌 노드의 위치만 구분 할 수 있으면 되므로 dictionary를 사용해주었습니다.

A의 왼쪽 노드가 B, 오른쪽 노드가 C라고 했을 때 A,B,C를 입력하게 되면

binaryTree[A] = [ B , C ]가 되어  binaryTree[A][0]는 왼쪽 노드를 binaryTree[A][1]은 오른쪽 노드를 의미하게 됩니다.

문제에서 주어진 트리는 다음과 같습니다.

def preorderTraversal(node):
    if node != '.':
        print(node,end='')
        for newNode in binaryTree[node]:
            preorderTraversal(newNode)

전위 순회는 현재 노드 - 왼쪽 서브 트리 - 오른쪽 서브 트리 순으로 순회하는 방식을 말합니다.

따라서, node에 대한 출력을 먼저 해준 후, 왼쪽 트리부터 순회를 시작합니다.

다음과 같이 탐색을 하게 된다면, binaryTree[node][0]가 왼쪽 노드를 의미하므로 왼쪽 먼저 탐색을 진행한 후, 오른쪽 노드를 탐색하게 됩니다.

문제에서 주어진 트리를 예시로 보자면,  A - B -D - C - E - F -G 순으로 탐색하게 됩니다.

def inorderTraversal(node):
    if node != '.':
        newNode1, newNode2 = binaryTree[node]
        inorderTraversal(newNode1)
        print(node,end='')
        inorderTraversal(newNode2)

다음은 중위 순회입니다. 중위 순회는 왼쪽 서브트리 - 현재 노드 - 오른쪽 서브트리 순으로 순회하는 방식입니다.

다음과 같이 코드를 구성해 왼쪽 서브 트리 순회 후 현재 노드를 출력되게 한 후, 오른쪽 서브트리를 순회 하도록 코드를 구성하였습니다.

def postorderTraversal(node):
    if node != '.':
        for newNode in binaryTree[node]:
            postorderTraversal(newNode)
        print(node,end='')

마지막으로 후위 순회 입니다. 후위 순회는 왼쪽 서브트리 - 오른쪽 서브 트리 - 현재 노드 순으로 순회하는 방식입니다.

따라서 다음과 같이 왼쪽 - 오른쪽 서브 트리를 모두 순회한 후 현재노드를 출력하는 방식으로 코드를 구현하였습니다.

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

문제: 임의의 수열에서 몇 개의 수를 선택하여 구할 수 있는 수 중  가장 큰 값을 구하는 문제 입니다.

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys

n = int(sys.stdin.readline())
array = list(map(int,sys.stdin.readline().rstrip().split()))

dp = [0] * n

dp[0] = array[0]

for i in range(1,n):
    dp[i] = max(dp[i-1]+array[i],array[i])

print(max(dp))

임의의 몇개를 구해서 최대가 되는 값을 구하는 문제 이므로, 이전까지의 연속 합 + 현재 값  / 현재 값을 비교해서 더 큰 값을 dp에 저장해 줍니다.

<문제 예시> 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 를 들어 설명해보겠습니다.

10 -4 3 1 5 6을 거치면서

dp = [10,6,9,10,15,21]이 저장됩니다.

이후 -35를 만나게 되면

dp[6]에는 -14가 저장되게 됩니다.

여기에서 저 연산이 빛을 발휘하게 됩니다.

12을 만났을 경우, dp[7]에는 -14 + 12 = -2가 아닌 12가 저장되게 됩니다.

즉, 이전까지 선택된 연속된 값이 현재 값보다 작으므로 12부터 다시 선택하게 되는 효과를 발휘하는 것입니다.

최종 dp에는 [10, 6, 9, 10, 15, 21, -14, 12, 33, 32] 값이 담겨서 

제일 큰 값을 출력해주게 되면 선택할 수 있는 연속된 수 중 제일 큰 합을 구할 수 있습니다.

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

문제: 정수 삼각형이 주어졌을 때, 맨 위층부터 맨 아래층 까지 도달할 수 있는 경로 중 경로에 있는 값의 합이 최대가 되는 값을 구하는 문제입니다.

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys
input = sys.stdin.readline

n = int(input())

triangle = []

for _ in range(n):
    triangle.append(list(map(int,input().rstrip().split())))
if n == 1:
    print(triangle[0][0])
    sys.exit(0)

for i in range(2):
    triangle[1][i] += triangle[0][0]


for i in range(2,n):
    for j in range(len(triangle[i])):
        triangle[i][j] += triangle[i-1][j] if j == 0 else triangle[i-1][j-1] if j ==(len(triangle[i])-1) else max(triangle[i-1][j-1],triangle[i-1][j])

print(max(triangle[n-1]))

풀이 설명:

풀이 코드에서 핵심 코드인 다음 코드를 설명하고 넘어가겠습니다.

for i in range(2,n):
    for j in range(len(triangle[i])):
        triangle[i][j] += triangle[i-1][j] if j == 0 else triangle[i-1][j-1] if j ==(len(triangle[i])-1) else max(triangle[i-1][j-1],triangle[i-1][j])

각 줄의 양 끝 값은 이 전줄의 하나의 값이랑만 연결이 되기 때문에,

j == 0 일 경우, triangle[i - 1][j] 가 더해지게 했고

j == len(triangle[i]) - 1 일 경우, triangle[i - 1][j - 1]이 더해지게 하였습니다. 이때 인덱스가 (i - 1, j - 1)인 이유는 이전 줄은 현재 줄보다 길이가 1 작기 때문입니다.

마지막으로, 양 끝 값이 아닌 경우에는 이 전줄의 2개의 값과 연결이 되기 때문에

이어지는 두개의 값중 큰 값을 더하도록 하였습니다.

이 코드를 한줄로 표현하면 다음과 같이 나옵니다.

triangle[i-1][j] if j == 0 else triangle[i-1][j-1] if j ==(len(triangle[i])-1) else max(triangle[i-1][j-1],triangle[i-1][j])

 이 코드를 풀어 쓴다면 다음과 같이 나옵니다.

if j == 0 :
    triangle[i][j] += triangle[i - 1][j]
    
elif j ==(len(triangle[i])-1):
    triangle[i][j] += triangle[i-1][j-1]

elif 0 < j < (len(triangle[i])-1):
    triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j])

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

저번주 부터 다이나믹 프로그래밍 문제를 계속해서 못풀어서 한참 고생했습니다..

기초도 중요하지만 문제를 봤을 때, 사고하는 능력 또한 기를 필요가 있다고 느꼈습니다.

문제: 집의 색이 연속되지 않으면서, 집을 색칠 하는 비용 중 최소인 비용 찾는 문제 입니다.

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys

n = int(sys.stdin.readline())

rgb = []

for _ in range(n):
    rgb.append(list(map(int,sys.stdin.readline().rstrip().split())))

for i in range(1,n):
    rgb[i][0] = min(rgb[i-1][1],rgb[i-1][2]) + rgb[i][0]
    rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + rgb[i][1]
    rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + rgb[i][2]

print(min(rgb[n-1]))

풀이 설명:

rgb의 비용을 연산하는 for문을 보면 다음과 같습니다.

for i in range(1,n):
    rgb[i][0] = min(rgb[i-1][1],rgb[i-1][2]) + rgb[i][0]
    rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + rgb[i][1]
    rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + rgb[i][2]

빨간색일 때, 현재 집의 비용에 이전 순서의 초록&파랑색 집의 비용중 최소 값을 더해줍니다.

초록색일 경우, 현재 집의 비용에 이전 순서의 빨강&파랑색 집의 최소 비용을 더해주고

파랑색일 경우, 현재 집의 비용에 이전 순서의 빨강&초록색 집의 최소 비용을 더해줍니다.

이렇게 되면 마지막 집의 비용이 담긴 배열에는 마지막 집의 색상 별로 전체 비용이 담기게 됩니다.

이를 다음과 같이 min 함수를 이용하게 되면 전체 비용중 최소 값이 출력되게 됩니다.

print(min(rgb[n-1]))

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

이번주 내내 solved.ac의 클래스 4에서 다이나믹 프로그래밍 문제를 3문제를 연달아 못풀었다..

그래서 당분간은 다이나믹 프로그래밍 문제를 풀어가며 해당 알고리즘을 공부해볼 생각이다.

문제:  2xn 타일이 주어졌을 때, 1x2 와 2x1 타일로 채울 수 있는 경우의 수를 구하는 문제입니다.

풀이 방법: 다이나믹 프로그래밍으로 풀었습니다.

풀이 코드:

n = int(input())
dp = [0,1,2,3]



if n <= 3:
    print(dp[n])
else:
    for i in range(4,n+1):
        dp.append(dp[i-1] + dp[i-2])

    print(dp[n] % 10007)

풀이 설명:

n = 1일 때, 만들 수 있는 경우의 수는 1개 입니다.

n = 2일 때는, 2x1 타일로만 구성할 수도 있고 1x2 타일로만 구성할 수 있으므로 2개 입니다.

n = 3일 때는 3가지

n= 4일 때는 5가지

n = 5일 때는 8가지가 나오는 것을 알 수 있었습니다.

이를 바탕으로, 점화식 f(n) = f(n-1) + f(n-2)  ( n >= 3 ) 을 구할 수 있었고

이 점화식을 위 코드로 구현하여 문제를 해결하였습니다.

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

처음 다익스트라 문제를 풀었을 때는, 코드를 짜는데 시간이 되게 오래 걸렸었습니다.

근데, 골드 4 난이도임에도 빠른 시간 내에 코드를 짜서 살짝 울컥했습니다.

공부해왔던게 효과가 있구나 라는 생각과 동시에 저도 모르게 살짝 울컥하더라구요.. 너무 뿌듯했습니다.

이런 기분때문에 공부를 계속할 수 있는 것 같습니다.

코딩 공부하는 모든 분들도 성취감을 느껴가며 즐겁게 공부하셨으면 좋겠습니다!

문제: 방향그래프가 주어졌을 때, 모든 정점으로의 최단거리를 구하는 문제입니다.

풀이 방법: 다익스트라 알고리즘을 활용하였습니다.

풀이 코드:

import sys
import heapq

INF =1e9

v,e = map(int,sys.stdin.readline().split())

k = int(input())

graph = [[]for _ in range(v+1)]

dist = [INF] * (v+1)
dist[k] = 0

for _ in range(e):
    start, end, cost= map(int,sys.stdin.readline().split())
    graph[start].append((cost,end))

def dijkstra(k):
    queue = []
    heapq.heappush(queue,(0,k))

    while queue:
        cost,node = heapq.heappop(queue)

        for nextCost,nextNode in graph[node]:
            distance = dist[node] + nextCost
            if distance < dist[nextNode]:
                dist[nextNode] = distance
                heapq.heappush(queue,(distance,nextNode))

dijkstra(k)

for i in range(1,v+1):
    if dist[i] == INF:
        print('INF')
    else:
        print(dist[i])

풀이 설명:

핵심은 다익스트라 알고리즘 이므로, 다익스트라 알고리즘을 보고 가겠습니다.

def dijkstra(k):
    queue = []
    heapq.heappush(queue,(0,k))

초기 값은 다익스트라 함수에 주어진 시작 노드 입니다.

이때 cost는 0으로 설정하여 heapq에 넣어줬습니다.

while queue:
    cost,node = heapq.heappop(queue)

    for nextCost,nextNode in graph[node]:
        distance = dist[node] + nextCost
        if distance < dist[nextNode]:
            dist[nextNode] = distance
            heapq.heappush(queue,(distance,nextNode))

이후 비용을 계산하는 반복문 입니다.

heapq에서 순차적으로 값을 꺼내옵니다.

cost와 node가 꺼내지는데요.  다음과 같이 heapq에서 꺼내진 node로 부터 연결된 노드들을 탐색합니다.

for nextCost,nextNode in graph[node]:
    distance = dist[node] + nextCost
    if distance < dist[nextNode]:
        dist[nextNode] = distance
        heapq.heappush(queue,(distance,nextNode))

node - newNode까지의 거리를 계산하고, 거리를 저장하는 배열인 dist에 저장된 값과 비교해줍니다.

현재 계산된 거리의 Cost가 더 낮을 경우, dist배열에 갱신해주고 갱신된 Cost와 함께 heapq에 넣어주는 과정을 반복시킵니다.

이를 통해, 시작 노드로 부터 연결된 모든 노드들을 탐색하게 됩니다.

다익스트라처럼 다른 알고리즘들도 잘 활용할 수 있도록 공부하자는 마음을 다잡는 문제였습니다.

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

문제: 숫자 A,B,C 가 주어졌을 때, A를 B번 곱했을 때 C로 나눈 나머지를 구하는 문제입니다.

풀이 방법: 분할 정복 방식으로 풀었습니다.

풀이 코드:

import sys

a,b,c = map(int,sys.stdin.readline().split())

def DivideAndConquer(num1,num2):
    if num2 == 1:
        return num1 % c

    tmp = DivideAndConquer(num1,num2//2)
    if num2 % 2 == 0:
        return tmp ** 2 % c
    else:
        return tmp**2 * num1 % c
print(DivideAndConquer(a,b))

풀이 설명:

나누는 수인 b가 짝수일 경우와 홀수일 경우를 나누어 생각했습니다.

입력 예제인 10,11,12로 예시를 들어보겠습니다.

b가 짝수 일 경우(a= 10, b = 10 ,c =12), 10^5 * 10^5로 나눌 수 있습니다.

b가 홀수 일 경우에는 (a=10, b=11, c=12), 10^5 * 10^5 * 10으로 나눌 수 있죠.

위와 같은 분할에다가, 나머지연산에 다음과 같이 분배 법칙을 적용할 수 있습니다.

(a*b)%c = ((a%c) * (b%c)) % c 로 분배법칙이 성립하죠.

분할과 분배법칙을 적용하여, 문제가 풀리도록 코드를 구성해주었습니다.