백트래킹의 개념을 이해하고, 전체 탐색(brute force, 브루트 포스)과 차이점을 설명할 수 있습니다. 유망 함수를 활용해서 더 효율적인 트리 탐색 알고리즘을 구현할 수 있습니다.
총 3편으로 준비했습니다. 3편은 백트래킹 몸풀기 문제입니다.
1. 백트래킹과 백트래킹 알고리즘 개념
2. 백트래킹 알고리즘 문제에 적용해보기
3. 백트래킹 몸풀기 문제
문제 01 1부터 N까지 숫자 중 합이 10이 되는 조합 구하기 ⭐️
- 저자 권장 시간: 60분
- 권장 시간 복잡조: O(N!)
- 출제: 완전 탐색
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/47.py
정수 N을 입력받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환하는 solution( ) 함수를 작성하세요.
제약 조건
- 백트래킹을 활용해야 합니다.
- 숫자 조합은 오름차순으로 정렬되어야 합니다.
- 같은 숫자는 한 번만 선택할 수 있습니다.
- N은 1 이상 10 이하인 정수입니다.
입출력의 예
문제 분석하고 풀기
앞서 살펴본 문제를 코드로 풀 때가 된 것 같네요. 자세한 설명은 이미 했으므로 문제에 접근하는 방법만 이야기하겠습니다.
- 조합한 숫자의 합이 10이 되면 해당 조합을 결과 리스트에 추가하기
- 조합한 숫자의 합이 10보다 크면 백트래킹(유망 함수 조건)
유망 함수 조건만 잘 파악했다면 쉽게 구현할 수 있는 문제입니다. 코드로 구현해봅시다.
def solution(N):
results = [] # ➊ 조합 결과를 담을 리스트
def backtrack(sum, selected_nums, start):
if sum == 10: # ❷ 합이 10이 되면 결과 리스트에 추가
results.append(selected_nums)
return
for i in range(start, N + 1): # ❸ 다음에 선택할 수 있는 숫자들을 하나씩 선택하면서
if sum + i <= 10: # ❹ 선택한 숫자의 합이 10보다 작거나 같으면
backtrack(
sum + i, selected_nums + [i], i + 1
) # ❺ 백트래킹 함수를 재귀적으로 호출합니다.
backtrack(0, [], 1) # ❻ 백트래킹 함수 호출
return results # ❼ 조합 결과 반환
solution( ) 함수는 정수 N을 인수로 받습니다. 이 N은 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 구하는 데 사용합니다.
➊ 함수 내부에서는 1부터 N까지의 숫자 중 합이 10이 되는 모든 조합을 담을 빈 리스트 results를 초기화합니다. results는 최종 반환값입니다. ➋ 백트래킹 함수 backtrack( )가 있습니다. 3개의 인자 sum, selected_nums, start를 하나씩 설명하면, sum은 현재까지 선택한 숫자들의 합, selected_nums는 현재까지 선택된 숫자들을 담고 있는 리스트, start는 조합에 포함 여부를 확인할 숫자입니다. ➌ 현재까지의 숫자 조합으로 합이 10이 되면 results에 현재 숫자들의 조합이 있는 리스트 selected_nums를 추가합니다. 이렇게 한 다음에는 더 숫자를 추가할 필요가 없으므로 백트래킹합니다. ➍ 현재 숫자 start부터 N까지 범위에 대해 반복문을 수행합니다.
backtrack( ) 함수는 1부터 N까지 차례대로 조합을 하면서 특정값 K가 되는 부분합을 찾고 있으므로 현재 숫자 이전의 숫자는 체크할 필요가 없습니다. ➎ 유망한 경우에만 backtrack( ) 함수를 호출하여 숫자 조합을 계속 확인합니다. 여기까지 backtrack( ) 함수에 대한 설명입니다.
이제 solution( ) 함수의 나머지 부분을 설명하겠습니다. ➏ 현재까지 구한 부분합 sum은 0, 해당 합의 조합인 selected_nums는 빈 리스트로, start는 1로 하여 backtrack( ) 함수를 호출합니다. ➐ 모든 부분합의 조합인 results를 반환합니다.
시간 복잡도 분석하기
N은 선택할 수 있는 숫자의 최대 개수입니다. 비복원 방식으로 숫자의 조합을 구하고 있으므로 처음 선택지는 N개 그다음 선택지는 (N – 1)… 이런 식으로 1씩 줄어듭니다. 이를 곱하면 최종 시간 복잡도는 O(N!)입니다. 다만 실제 연산은 유망 함수에 의해 훨씬 적습니다.
문제 02 스도쿠 퍼즐 ⭐️⭐️⭐️
- 저자 권장 시간: 60분
- 권장 시간 복잡조: O(9N)
- 출제: 완전 탐색
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/48.py
9 × 9 스도쿠 보드를 다 채워 완성된 스도쿠 보드를 반환하는 solution( ) 함수를 작성하세요. 해는 유일하지 않을 수 있습니다. 스도쿠의 조건에 맞다면 맞는 해라고 생각하시면 됩니다. 스도쿠의 규칙은 아래와 같습니다.
- 가로줄, 세로줄에는 1부터 9까지의 숫자가 한 번씩 나타나야 합니다.
- 9 × 9 보드를 채울 9개의 작은 박스(3 × 3 크기)에도 1부터 9까지의 숫자가 한 번씩 나타나야 합니다.
제약 조건
- 문제에 주어지는 board 중 스도쿠를 완성하지 못하는 board는 없다고 가정합니다. 예를 들어 특정 행이나 열에 같은 숫자가 있는 경우는 없습니다.
입출력의 예
문제 분석하고 풀기
스도쿠 보드의 빈칸에 적절한 숫자를 채우는 과정에 백트래킹을 사용해봅시다. num이라는 숫자를 특정 위치에 넣어도 되는지 여부는 아래와 같이 판단할 수 있습니다. 아래 조건에 해당된다면 백트래킹합니다.
- 조건 1 : 해당 행에 넣으려는 숫자 num이 있는지 확인합니다.
- 조건 2 : 해당 열에 넣으려는 숫자 num이 있는지 확인합니다.
- 조건 3 : 해당 위치를 포함하는 3 × 3박스에 num이 있는지 확인합니다.
def solution(board):
def is_valid(num, row, col):
# ❶ 현재 위치에 num이 들어갈 수 있는지 검사
return not (in_row(num, row) or in_col(num, col) or in_box(num, row, col))
def in_row(num, row):
# ❷ 해당 행에 num이 있는지 확인
return num in board[row]
def in_col(num, col):
# ❸ 해당 열에 num이 있는지 확인하는 함수
return num in (board[i][col] for i in range(9))
def in_box(num, row, col):
# ❹ 현재 위치의 3x3 박스에 num이 있는지 확인
box_row = (row // 3) * 3
box_col = (col // 3) * 3
for i in range(box_row, box_row + 3):
for j in range(box_col, box_col + 3):
if board[i][j] == num:
return True
return False
def find_empty_position():
# ❺ 스도쿠 보드에서 비어 있는 위치 반환
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return i, j
return None
def find_solution():
# ❻ 비어 있는 위치에 가능한 숫자를 넣어가며 스도쿠 해결
empty_pos = find_empty_position()
# ❼ 빈 칸이 없으면 스도쿠가 해결된 것으로 간주
if not empty_pos:
return True
row, col = empty_pos
for num in range(1, 10):
if is_valid(num, row, col):
board[row][col] = num
if find_solution(): # ❽ 다음 빈 칸으로 재귀적으로 탐색
return True
board[row][col] = 0 # ❾ 가능한 숫자가 없으면 원래의 0으로 되돌림
return False
find_solution()
return board
➊ is_valid( ) 함수는 칸의 위치, 즉, 행과 열, 그리고 스도쿠 보드에 넣을 값을 매개변수로 받습니다. 백트래킹의 유망 함수가 이 함수입니다. 해당 위치에 넣을 값을 넣을 수 있는지 in_row, in_cow, in_box를 활용하여 확인합니다. ➋ in_row( ) 함수는 넣을 수가 같은 행에 있는지 확인하고, ➌ 마찬가지로 in_col( ) 함수는 열을 확인합니다. ➍ 현재 위치를 포함한 3 × 3 박스에 같은 숫자가 있는지 확인합니다.
➎ find_empty_position( ) 함수는 현재 스도쿠 보드에 비어 있는 위치를 반환합니다. 스도쿠 보드를 순회하면서 값이 0인 칸이 있는지 확인하고, 값이 0인 칸이 있다면 해당 칸의 행, 열을 반환합니다. 빈칸이 없으면 None을 반환합니다.
➏ find_solution( )은 스도쿠를 푸는 메인 함수입니다. 스도쿠 보드에서 빈 위치를 확인하고 알맞은 숫자를 넣습니다. 여기서 ‘알맞은’이란 is_valid( ) 함수가 True를 반환하는 경우입니다. ➐ 스도쿠 보드에 숫자가 전부 채워져 있다면 더 탐색을 진행하지 않습니다. 백트래킹은 다음과 같이 진행합니다.
➑~➒ row, col은 find_empty_poisition( ) 함수를 통해 찾은 빈칸의 행과 열 값입니다.
- 해당 위치에 숫자를 1~10까지 하나씩 넣으며 is_valid( ) 함수로 체크합니다.
- 유망하다면 스도쿠 보드에 해당 값을 넣고 find_solution( ) 함수를 호출하여 빈칸을 체크합니다.
- find_solution( ) 함수가 True를 반환하면, 즉, 스도쿠 보드에 빈칸이 없다면 더 탐색하지 않습니다. False를 반환하면 row, col에 num을 넣었을 때 해가 없는 경우입니다. 반복문을 다 돌았는데도 해를 찾지 못하면 False를 반환합니다.
시간 복잡도 분석하기
N은 스도쿠에서 빈 칸의 개수입니다. 빈 칸당 1~9의 수가 들어가므로 최종 시간 복잡도는 O(9N)입니다. 다만 실제 연산은 유망 함수에 의해 훨씬 적습니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
