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

• 이번에는 코딩 테스트에서 알면 유용한 유형 중 하나인 백트래킹에 대해 이야기해보려고 합니다. 백트래킹은 문제의 해를 찾는 과정에서 가능한 모든 후보들을 탐색하면서 해를 찾아가는 알고리즘 기법입니다. 이 글에서는 백트래킹의 개념과 코딩 테스트에서 백트래킹 문제를 접했을 때 어떻게 접근해야 하는지에 대해 자세히 알아보겠습니다.

 

백트래킹의 개념

 

• 백트래킹은 "역추적"이라는 뜻을 가지고 있으며, 주어진 문제의 조건을 만족하는 해를 찾기 위해 탐색하다가 조건을 만족하지 않으면 되돌아가서 다른 경우를 탐색하는 방법입니다. 이러한 방식으로 가능한 모든 경우를 조사함으로써 최적의 해를 찾아낼 수 있습니다.
• 백트래킹은 대부분 재귀 함수로 구현되며, 일반적으로 다음과 같은 단계로 진행됩니다.

 

1. 문제의 조건과 제약 사항을 정의합니다.
2. 현재 상태에서 가능한 모든 선택지(다음 단계로 진행할 수 있는 후보들)를 생성합니다.
3. 각 선택지에 대해 조건과 제약 사항을 검사합니다.
4. 조건과 제약 사항을 만족하는 선택지를 따라 나아갑니다(재귀 호출).
5. 선택지가 없거나, 목적 상태에 도달하면 탐색을 종료합니다.
6. 결과를 출력하거나 저장합니다.

 

코딩 테스트에서의 백트래킹 문제 접근 방법

 

• 코딩 테스트에서 백트래킹 문제는 주어진 제약 사항 내에서 가능한 모든 경우를 확인해야 할 때 자주 등장합니다. 이런 종류의 문제들은 일반적으로 DFS(깊이 우선 탐색)와 함께 사용됩니다.
• 문제 해결을 위해 다음과 같은 단계로 접근할 수 있습니다.

 

1. 문제 요구사항 파악: 주어진 문제의 요구사항과 제약 사항을 정확하게 파악하는 것이 매우 중요합니다.
2. 후보군 생성: 현재 상태에서 가능한 선택지(다음 단계로 진행할 수 있는 후보들)를 생성합니다.
3. 유효성 검사: 각 후보군이 주어진 조건과 제약 사항을 만족시키는지 확인합니다.
4. 재귀 호출: 조건과 제약 사항을 만족하는 후보군에 대해서 재귀 호출하여 다음 단계로 넘어갑니다.
5. 종료 조건 확인: 목적 상태에 도달하거나 더 이상 진행할 수 있는 선택지가 없으면 탐색 종료합니다.

• 위와 같은 과정으로 백트래킹 알고리즘 구현 시, 가장 중요한 부분은 "유효성 검사"입니다. 유효성 검사 함수는 현재 상태와 선택된 값을 받아 해당 값이 주어진 제약조건에 부합하는 지 판단하여 True 또는 False 값을 반환해야 합니다.
• 또한, 백트래킹 알고리즘이 비교적 시간 복잡도가 크기 때문에 여러 가지 최적화 기법도 활용될 수 있습니다. 예를 들면 가지치기(pruning), 메모이제이션(memoization), 오프라인 객관식 처리 등이 있습니다.

 

어떤 경우에 백트래킹 알고리즘이 DFS보다 유리할까?

 

• 백트래킹 알고리즘은 DFS와 비슷한 방식으로 탐색을 진행하지만, 더 많은 정보를 저장하고 사용합니다. 따라서 DFS보다 더 많은 경우를 고려할 수 있고, 더 빠르게 탐색을 종료할 수 있습니다. 백트래킹 알고리즘은 다음과 같은 경우에 유리합니다.

1. 탐색 범위가 넓은 경우
2. 조건이 복잡한 경우
3. 탐색을 중간에 종료해야 하는 경우

1. 백트래킹 알고리즘은 탐색 범위가 넓은 경우에 유리합니다. DFS는 탐색 범위가 넓을수록 더 많은 노드를 방문해야 하기 때문에 시간이 오래 걸립니다. 반면, 백트래킹 알고리즘은 탐색 범위가 넓더라도 더 적은 노드를 방문하기 때문에 더 빠르게 탐색을 종료할 수 있습니다.
2. DFS는 조건이 복잡할 경우 조건을 만족하는 노드를 찾기 어렵기 때문에 시간이 오래 걸립니다. 반면, 백트래킹 알고리즘은 조건을 만족하는 노드를 찾기 쉽기 때문에 더 빠르게 탐색을 종료할 수 있습니다.
3. DFS는 탐색을 중간에 종료할 수 없기 때문에, 탐색 범위가 넓거나 조건이 복잡한 경우 탐색을 종료하기 어렵습니다. 반면, 백트래킹 알고리즘은 탐색을 중간에 종료할 수 있기 때문에, 탐색 범위가 넓거나 조건이 복잡한 경우에도 탐색을 빠르게 종료할 수 있습니다.

 

14888번: 연산자 끼워넣기

 

  문제  

 

• N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
• 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
• 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6

• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7

• N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 
  해결 방법  

 

• 이 문제는 주어진 수열과 연산자들을 활용하여 만들 수 있는 식의 결과가 최대인 경우와 최소인 경우를 찾는 문제입니다. 이때 모든 연산은 왼쪽에서부터 순서대로 이루어집니다.
• 백트래킹을 사용하여 각각의 연산자 별로 남아있는 개수를 확인하며 모든 가능한 조합을 탐색합니다.

n = int(input())
numbers = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

min_v, max_v = 1e9, -1e9

def dfs(i, result, add, sub, mul, div):
    global min_v, max_v
    if i == n:
        min_v = min(result, min_v)
        max_v = max(result, max_v)
        return
    
    else:
        if add:
            dfs(i+1, result+numbers[i], add-1, sub, mul, div)
        if sub:
            dfs(i+1, result-numbers[i], add, sub-1, mul, div)
        if mul:
            dfs(i+1, result*numbers[i], add, sub, mul-1, div)
        if div:
            if result < 0:
                dfs(i+1, -(-result//numbers[i]), add, sub, mul, div-1) 
            else:
                dfs(i+1, result//numbers[i], add, sub, mul, div-1)

dfs(1, numbers[0], add, sub, mul, div)

print(max_v)
print(min_v)

• 위 코드에서 dfs 함수가 바로 백트래킹을 수행하는 함수입니다. 각 단계에서 가능한 모든 선택지(연산자 사용)에 대해 재귀적으로 호출하며 탐색합니다.

 

13023번: ABCDE

 

  문제  

 

• BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
• 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.

• 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

 

  해결 방법  

 

• 이 문제는 주어진 친구 관계 내에서 A-B-C-D-E의 관계를 가지는 그룹이 존재하는지 찾는 문제입니다. 이 문제 역시 백트래킹을 활용하여 해결할 수 있습니다.

import sys; input=sys.stdin.readline

N, M = map(int, input().split())
arr = [[False] * N for _ in range(N)]
graph = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    arr[a][b] = arr[a][b] = True
    graph[a].append(b)
    graph[b].append(a)

def dfs(x, depth):
    if depth == 4:
        print(1)
        exit(0)
    
    for nx in graph[x]:
        if not check[nx]:
            check[nx] = True
            dfs(nx, depth+1)
            check[nx] = False

check = [False] * N

for i in range(N):
    check[i] = True
    dfs(i, 0)
    check[i] = False

print(0)

• 위 코드에서 dfs 함수가 바로 백트래킹을 수행하는 함수입니다. 각 단계에서 가능한 모든 선택지(A-B-C-D-E 관계를 만족하는 친구)에 대해 재귀적으로 호출하며 탐색합니다.
  
  

• 두 문제 모두 백트래킹의 기본적인 원리를 따르고 있습니다. 가능한 모든 선택지를 고려하되, 조건에 맞지 않는 경우 더 이상 진행하지 않고 다른 선택지를 고려합니다. 이런 방식으로 탐색 범위를 효율적으로 줄이면서도 문제의 해결책을 찾아낼 수 있습니다.