[코딩 테스트 합격자 되기] 백트래킹– 3. 백트래킹 몸풀기 문제
이 글은 〈[되기] 코딩 테스트 합격자 되기(파이썬 편)〉에서 발췌했습니다.
골든래빗 출판사
박경록 지음
백트래킹의 개념을 이해하고, 전체 탐색(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보다 크면 백트래킹(유망 함수 조건)
유망 함수 조건만 잘 파악했다면 쉽게 구현할 수 있는 문제입니다. 코드로 구현해봅시다.
Use a different Browser
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이 있는지 확인합니다.
Use a different Browser
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 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
BFS DFS PYTHON 검색 그래프 깊이우선탐색 너비우선탐색 네이버 배달의민족 배민 버블정렬 빠른정렬 삼성 삼성전자 스택 알고리즘 알고리즘시험 우아한형제들 우형 이진트리 자료구조 자료구조시험 재귀호출 카카오 코딩테스트 코테 쿠팡 큐 탐색 트리 파이썬 프로그래머 프로그래머스 프로그래밍 프로그램
Related News
[Agent] AI 에이전트 프로토콜, 구글 A2A 개념부터 원리 실습하기
[Python] 파이썬으로 엑셀 다루기 | ❷ 엑셀 데이터 사용하기
[Python] 파이썬으로 엑셀 다루기 | ❶ 엑셀 데이터 사용하기
[Python] 아나콘다 설치하기 | Anaconda, 파이썬, 주피터 노트북, 단축키
골든래빗 2024-01-05