알면 도움되는 코딩 테스트 유형: 9) #Divide_and_Conquer

• 이번에는 코딩 테스트에서 자주 등장하는 유형인 "분할 정복(Divide and Conquer)"에 대해 알아보려고 합니다. 

 

분할 정복의 개념

 

• 분할 정복은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 주어진 문제를 해결하기 위해서는 세 가지 단계로 나눌 수 있습니다.

 

• 분할(Divide): 주어진 문제를 작은 부분 문제로 분할합니다.
• 정복(Conquer): 각각의 작은 부분 문제를 재귀적으로 해결합니다.
• 통합(Combine): 작은 부분 문제들의 결과를 결합하여 원래의 큰 문제에 대한 최종 해답을 얻습니다.

• 이러한 단계들을 반복하여 원래의 큰 문제를 점차적으로 해결해 나갑니다.

 

코딩 테스트에서의 분할 정복 문제 접근 방법

 

1. 기저 조건(Base Case) 설정: 재귀적인 호출을 멈추기 위한 기저 조건을 설정합니다. 예를 들어, 주어진 배열이 비어있거나 원소가 하나인 경우 등입니다.
2. 분할: 문제를 작은 부분으로 나눕니다. 일반적으로 입력 데이터 크기가 반으로 줄거나 균등하게 나뉘도록 합니다.
3. 재귀 호출: 작은 부분 문제들을 재귀적으로 호출하여 해결합니다.
4. 결과 통합: 작은 부분문제들의 결과를 결합하여 최종 결과값을 도출합니다.

• 위와 같이 단계별로 접근하면 보다 구체적인 문제 해결 방법을 파악하고 코드 작성 시에도 명확하게 로직 구현이 가능합니다.

 

5904번: Moo 게임

 

  문제  

 

• Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.
• Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. 

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o

• Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

• 위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다.
• N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

 

  해결 방법  

 

• 이 문제는 Moo 시퀀스라는 특별한 문자열에서 N번째 위치에 있는 문자를 찾는 것입니다.
• 주어진 인덱스에 위치한 문자를 찾기 위해 분할 정복 알고리즘을 사용합니다.
• 재귀적으로 주어진 인덱스와 현재 시퀀스의 중앙 값을 비교하여 왼쪽 반 또는 오른쪽 반에 속하는지 확인하고, 해당 범위 내에서 다시 재귀 호출을 수행합니다.
• 이를 통해 입력 범위를 절반씩 줄여가며 문제를 해결합니다. 초기 호출에서는 시작 길이와 추가된 길이(result)를 계산하여 최소한의 "moo" 시퀀스 길이(length)를 찾습니다.

def solve(n, length, result):
    half = (length - result) // 2
    if n <= half: return solve(n, half, result-1)
    elif n > half + result: return solve(n - half - result, half, result-1)
    else: return 'o' if n - half - 1 else 'm'

n = int(input())
length, answer = 3, 0

while n > length:
    answer += 1
    length = length * 2 + answer + 3

print(solve(n, length, answer+3))

 

 

4256번: 트리

 

  문제  

 

• 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다.
• 아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다.

• BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 아래에 C 스타일의 의사 코드로 나와 있다. BT의 노드 v에 대해서, v.left는 왼쪽 자식, v.right는 오른쪽 자식을 나타낸다. v가 왼쪽 자식이 없으면 v.left는 ∅와 같고, 오른쪽 자식이 없으면 v.right는 ∅와 같다.

• BT를 전위 순회, 중위 순회한 결과가 주어진다. 즉, 위의 함수 중 preorder(root node of BT)와 inorder(root node of BT)를 호출해서 만든 리스트가 주어진다. 두 순회한 결과를 가지고 다시 BT를 만들 수 있다. BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.
• 예를 들어, 위의 그림을 전위 순회하면 3,6,5,4,8,7,1,2, 중위 순회하면 5,6,8,4,3,1,2,7이 된다. 이를 이용해 후위 순회하면 5,8,4,6,2,1,7,3이 된다.

 

  해결 방법  

 

• 이 문제는 전위 순회(preorder)와 중위 순회(inorder) 결과가 주어졌을 때 후위 순회(postorder)를 구하는 문제입니다. 트리의 특성과 분할 정복(divide and conquer) 알고리즘을 이용하여 해결할 수 있습니다.
• 전체적인 알고리즘은 다음과 같습니다.

1. 전위 순회의 첫 번째 노드는 항상 트리의 루트입니다.
2. 이 루트를 중위 순회에서 찾으면, 그 위치를 기준으로 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리가 됩니다.
3. 각각의 서브트리에 대해 동일한 작업을 반복합니다(재귀).
4. 모든 노드를 방문한 후에는 해당 노드를 출력합니다.

import sys; sys.setrecursionlimit(10**6); input=sys.stdin.readline

def solve(start, end):
    if start > end: return
    root = preorder.pop(0)
    idx = inorder.index(root)
    
    solve(start, idx-1)
    solve(idx+1, end)

    print(root, end=' ')

for _ in range(int(input())):
    n = int(input())
    preorder = list(map(int,input().split()))
    inorder = list(map(int,input().split()))
    solve(0, n-1)
    print()

 

• 분할 정복은 코딩 테스트에서 매우 유용한 알고리즘 패러다임입니다. 큰 문제를 작은 부분으로 나누어 해결함으로써 효율적인 알고리즘을 구현할 수 있습니다. 분할 정복은 문제를 해결하는 방법론이므로, 주어진 문제에 따라 적절한 분할과 재귀 호출, 결과 통합을 수행해야 합니다.
• 분할 정복은 다양한 유형의 문제에 적용될 수 있습니다. 예를 들어, 이진 탐색, 병합 정렬, 퀵 정렬 등 많은 알고리즘이 분할 정복 기법을 사용합니다. 따라서 코딩 테스트를 준비하는 과정에서는 분할 정복 유형의 문제에 대한 이해와 구현 능력을 갖추는 것이 중요합니다.