백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 백트래킹을 파이썬으로 풀어보았다. 코드는 8문제 통째로 깃허브에 올려놓았으며 각 문제마다 주석으로 표시해놨다.
백트래킹 단계
조금 더 복잡한 백트래킹 문제 1
www.acmicpc.net
원본 코드는 깃허브에!
tomy9729/Algorithm
🐺 내가 직접 작성한 내 코드 🐺. Contribute to tomy9729/Algorithm development by creating an account on GitHub.
github.com
0. 백트래킹
백트래킹은 어떻게 보면 브루트 포스와 비슷해보이지만 훨씬 효율적인 알고리즘 기법이다. 백트래킹이란 해를 찾는 도중 더이상 해가 될 수 없는 상태가 되면, 해가 가능한 지점으로 돌아가서 다른 해를 찾아가는 기법이다. 이렇게만 말하면 이해하기 어렵다.
가상의 트리가 있다고 상상해보자. 정답을 찾기 위해 부모노드에서부터 자식노드까지 뻗어나간다. 그리고 각 노드들은 정답 유망성을 검토한다. 만약 해당 노드에서 유망하지 않다고 판단되면, 즉 정답이 될 수 없다고 판단되며 다시 부모 노드로 돌아간다. 부모노드는 정답을 찾기 위해 또 다른 자식 노드로 뻗어나간다. 유망하지 않은 노드의 경우 자손 노드로 진행하지 않고 아예 배제하기 때문에 풀이시간을 단출 시킬 수 있다. 유망한지 아닌지를 판단하는 함수를 promising라고 한다. 나도 처음에는 개념을 이해하기 조금 어려웠는데 문제를 풀다 보니 백트래킹은 조건(promising)이 달린 브루트 포스라는 느낌을 강하게 받았다.
앞서 "가상의" 트리를 언급했다. 백트래킹을 통해 문제를 풀어나가는 과정은 트리를 생각하면 이해하기 편하다. 그러나 실제로 트리보다는 큐나 재귀함수를 통해 구현한다. 그래서 구현할 때 또 한 번 헷갈릴 수 있다. 부모노드에서 자식노드로, 자식노드에서 부모노드로 어떻게 이동할지만 고민해보면 큐나 재귀함수를 통해 가상의 트리를 만들 수 있을 것이다. 백준에서 단계별로 문제풀기 순서를 보면 큐나 트리는 백트래킹보다 높은 단계이기 때문에 의도했다고 판단되어 최대한 재귀함수로 풀었다.
백트래킹 문제의 코드는 대부분 다음과 같은 구조를 갖는다.
def 재귀함수(x) :
if 정답이라면? :
정답 출력 또는 저장 등
else : 정답이 아니라면?
for 뻗을 수 있는 모든 자식 노드에 대해서 :
if 정답에 유망하다면 :
자식노드로 이동
재귀함수(x+1)
부모노드로 이동다른 강의나 글을 보면 구조가 조금 다른데 내가 이해하고 받아들이기에 좀 더 쉽도록 살짝 변형하였다. 그렇다고 틀린 구조는 아니다. 백트래킹의 모든 문제를 이 구조로 풀었다.
백트래킹은 문제 풀이 시간을 단축 시킬 수 있는 알고리즘이지만 파이썬이라서 그런지 이번에는 특히나 시간 초과를 회피하기 힘들었다. 대부분 pypy3로 컴파일하여 시간 초과를 회피하였는데 python3로도 통과하고 싶어 최적화에 오랜 시간 투자했지만 결국 pypy3로만 성공한 문제들이 몇 있다. 그동안 항상 문제를 분리하여 객체지향적으로 코딩하는데 노력하였는데 그에 비해 최적화에는 별로 신경 쓰지 않았던 것 같다. 나중에 기회가 되면 최적화에 대해서도 공부해보고 싶다고 생각했다. 추가로 pypy3는 python3보다 컴파일 속도가 빠르다는 장점이 있지만 메모리를 더 많이 사용한다는 단점이 있다.
1. 15649번 N과 M(1)
순열에 관한 문제이다. 영어로는 permutation이면 기호 P를 사용한다. 숫자 n과 m에 대하여 nPm을 구하는게 이번 문제이다. 그리고 파이썬에는 순열 함수를 제공하는 라이브러리가 존재한다. 이 라이브러리를 통해서 문제를 해결할 수도 있지만 그러면 백트래킹을 공부하는 의미가 없어서 직접 구현했다.
백트래킹은 항상 promising을 어떻게 구현할 것인지가 핵심이라고 생각한다. 이번 문제의 경우 숫자끼리 중복되지 않는 것이 핵심이다. 중복을 방지하기 위해 이미 사용된 숫자를 표시하기위해 배열 visit을 선언했으며 어떤 숫자가 사용되면 visit에서 해당 숫자를 index로 가지는 배열에 1을 저장했다. visit을 통해 어떤 숫자가 사용되었는지 안되었는지 확인했고 이미 사용된 숫자라면 다시 부모 노드로 돌아간다.
#15649번 N과 M(1)
n,m = input().split()
n = int(n)
m = int(m)
visit = [0]*(n+1)
arr = [0]*(m+1)
def is_not_duplicate(num) :
if visit[num] == 0 :
return True
else :
return False
def check(x) :
if x == m+1 :
for i in range(1,m+1) :
print(arr[i], end=' ')
print()
else :
for i in range(1,n+1) :
if is_not_duplicate(i) :
visit[i] = 1
arr[x] = i
check(x+1)
arr[x] = 0
visit[i] = 0
check(1)
2. 15650번 N과 M(2)
1번과 비슷한 문제지만 이번에는 오름차순이다. 개인적으로 1번보다 구현하기 편했다. 순열의 경우 중복 여부를 확인해야 했지만 오름차순은 기존 배열에서의 최댓값과 새로 입력할 숫자의 크기 비교만 하면 됐다.
#15650번 N과 M(2)
n,m = input().split()
n = int(n)
m = int(m)
arr = [0]*(m+1)
def check(x) :
if x == m+1 :
for i in range(1,m+1) :
print(arr[i], end=' ')
print()
else :
for i in range(1,n+1) :
if max(arr) < i :
arr[x] = i
check(x+1)
arr[x] = 0
check(1)
3. 15651번 N과 M(3)
1번문제에서 중복이 허용되게 변형됐다. 1번문제에서 promising만 제거하면 문제를 해결할 수 있다.
#15651번 N과 M(3)
n,m = input().split()
n = int(n)
m = int(m)
arr = [0]*(m+1)
def check(x) :
if x == m+1 :
for i in range(1,m+1) :
print(arr[i], end=' ')
print()
else :
for i in range(1,n+1) :
arr[x] = i
check(x+1)
arr[x] = 0
check(1)
4. 15652번 N과 M(4)
이번에는 숫자들을 비내림차순으로 구해야한다. 비내림차순이란 숫자가 내려가지만 않으면 되는 순열을 말한다. 즉 숫자는 계속 같은 값을 보이거나 올라가면 된다. 2번 문제에서 가장 밑에 있는 if문에 등호 하나만 추가하여 문제를 해결했다.
#15652번 N과 M(4)
n,m = input().split()
n = int(n)
m = int(m)
arr = [0]*(m+1)
def check(x) :
if x == m+1 :
for i in range(1,m+1) :
print(arr[i], end=' ')
print()
else :
for i in range(1,n+1) :
if max(arr) <= i :
arr[x] = i
check(x+1)
arr[x] = 0
5. 9663번 N-Queen
백트래킹에서 가장 유명한 N-Queen 문제이다. 예전에도 풀어본적이 있는 문제인데 이번에 다시 풀면서 그 때 내가 얼마나 비효율적이고 멍청하게 풀었는지 되돌아 보게 됐다. N-Queen문제는 크기가 NxN인 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다. promising으로 새로 놓게 되는 퀸이 이미 놓여진 퀸가 서로 공격되는 위치에 놓아질 경우 배제하도록 하면 된다.
백트래킹을 잘 이해하면 문제를 해결하는 것 자체는 어렵지 않다. 문제는 시간초과를 회피하는 일이다. 코드를 짜는데는 그렇게 오랜 시간이 걸리지 않았는데 최적화를 하는데 시간이 꽤 걸렸다. 그렇게 하고서도 pypy3로 컴파일하여 겨우겨우 통과할 수 있었다. 짜잘한 최적화를 제외하고 내가 생각한 최적화는 두 가지이다. 첫 번째는 체스판 위에 가장 먼저 놓아지는 퀸은 promising을 거치지 않아도 된다. 두 번째는 N이 짝수 일 때 체스판은 대칭되기 때문에 첫 퀸을 절반까지만 이동하여 N-Queen을 구하고 출력할 때 2배하는 방법이다. 이를 통해 pypy3로 통과할 수 있었다. 다른 사람들 후기를 봐도 python3로는 통과하기 매우 어렵다는데 개인적으로 python3으로 통과하지 못한 것이 굉장히 분했다. 다음에 기회가 되면 꼭 최적화에 대해 공부해볼 생각이다.
#9663번 N-Queen
n = int(input())
count = 0
arr = [0]*(n+1)
arr[0] = 100
def is_queen_no_die(arr, i) : # 새로 들어오는 퀸의 위치가 죽으면 False를 반환
new_queen = arr.index(0)
j = 1
while arr[j] : #퀸이 존재하는 배열까지만 진행
if arr[j] == i or abs(j - new_queen) == abs(arr[j] - i) : #퀸이 죽는 경우
return False
j += 1
return True
def check(x) :
if x == n+1 :
global count
count += 1
else :
for i in range(1,n+1) :
if x == 1 : #첫 번째 퀸은 검사할 필요가 없음
if n%2 == 0 and i > n//2 : # n이 짝수일때는 첫 번째 퀸을 반까지만 진행하고 나온 count값에 두배한다.
break
arr[x] = i
check(x+1)
arr[x] = 0
elif is_queen_no_die(arr,i) : #퀸이 죽을 경우 수행하지 않음
arr[x] = i
check(x+1)
arr[x] = 0
check(1)
if n%2 == 0 :
print(count*2)
else : print(count)
6. 2580번 스도쿠
개인적으로 N-Queen보다는 쉬웠다. 그러나 이 문제도 pypy3로만 해결했다...
빈칸에 숫자를 하나씩 넣기 위해 빈칸들의 좌표로만 이루어진 배열을 하나 만들었다. promising은 can_fill_empty함수로 스도쿠의 룰 세가지를 적용하여 빈칸을 채울 수 있는지 확인했다. 코드는 쉽게 작성했는데 이상한데서 시간을 할애했다. 항상 문제를 잘 읽어야한다. 답이 2개 이상일 경우 처음 답 하나만 출력하도록 해야한다. 근데 이 조건을 설정해주지 않아 여러번 실패했다. 답을 한 번만 출력하기 위해 sys.exit()를 사용했다.
#2580번 스도쿠
import sys
#input = sys.stdin.readline
board = [[0]*9 for i in range(9)]
for i in range(9) :
board[i][0],board[i][1],board[i][2],board[i][3],board[i][4],board[i][5],board[i][6],board[i][7],board[i][8] = map(int,input().split())
empty = [] #빈칸 좌표를 저장
for i in range(9) :
for j in range(9) :
if board[i][j] == 0 :
empty.append([i,j])
def can_fill_empty(point, i) : #point는 빈칸의 좌표, i는 빈칸에 들어갈 숫자
if i in board[point[0]] : #행에 같은 숫자가 있으면 false
return False
for x in range(9) :
if board[x][point[1]] == i : #열에 같은 숫자가 있으면 false
return False
start_x = point[0]-(point[0]%3)
start_y = point[1]-(point[1]%3)
for x in range(start_x,start_x+3) : #정사각형에 같은 숫자가 있으면 false
for y in range(start_y,start_y+3) :
if board[x][y] == i :
return False
return True
def check(x) :
if x == len(empty) : #답 출력
for i in range(9) :
for j in range(9) :
print(board[i][j],end=' ')
print()
sys.exit() #답을 한번만 출력하기위해 프로그램 강제 종료
else :
for i in range(1,10) :
if can_fill_empty(empty[x],i): #빈칸을 채우는 조건에 만족하면.
board[empty[x][0]][empty[x][1]] = i
check(x+1)
board[empty[x][0]][empty[x][1]] = 0
check(0)
7. 14888번 연산자 끼워넣기
n개의 숫자와 n-1개의 연산자가 주어지며 숫자 사이마다 연산자를 끼워 넣고 나온 결과에 대해서 최댓값과 최솟값을 출력하는 문제이다. 각 연산자의 개수를 입력받고 2개 이상 입력된 연산자들도 빠짐없이 사용하기 위해 all_operator 배열에 연산자들을 모두 저장했다. 최적화를 위해 일단 모든 계산된 결과를 배열 answers에 저장하고 answers에서 최댓값과 최솟값을 출력하도록 했다.
#14888번 연산자 끼워넣기
import sys
input = sys.stdin.readline
n = int(input())
num = []
num = input().split()
for i in range(n) :
num[i] = int(num[i])
arr = [-1] * (n-1) # 연산자 기호들의 경우의 수를 그때그때 저장할 배열
operator = [0]*4
operator[0],operator[1],operator[2],operator[3] = map(int,input().split()) #순서대로 + - * /
all_operator = [] # 모든 연산자 기호들의 집합(중복 포함)
for i in range(4) :
for j in range(operator[i]) :
all_operator.append(i)
visit = [0]*len(all_operator) # 이미 사용된 기호를 구분하기 위함
def calculate(n1,n2,x) : # 연산자 계산기
if x == 0 :
return n1+n2
elif x == 1:
return n1-n2
elif x == 2 :
return n1*n2
elif x == 3 :
if n1 < 0 :
return -1*(-1*n1//n2)
return n1//n2
def answer(num,arr) : # 완성된 식을 계산
temp = num[0]
for i in range(len(arr)) :
temp = calculate(temp,num[i+1],arr[i])
return temp
answers = []
def check(x) :
if x == n-1: # 끼워넣을 연산자 구성 완료
answers.append(answer(num,arr))
else :
for i in range(len(all_operator)) :
if visit[i] == 0 : # 중복 사용시 수행 x
visit[i] = 1
arr[x] = all_operator[i]
check(x+1)
arr[x] = -1
visit[i] = 0
check(0)
print(max(answers))
print(min(answers))
8. 14889번 스타트와 링크
순열로 푸는 문제인데 1번 문제에서 이미 순열 코드를 작성해봤기 때문에 이번에는 파이썬 라이브러리인 combinations를 사용해보았다. (백트래킹으로 풀지 않았다.ㅎㅎ)풀면서 알게 된 내용인데 어떤 숫자 집합 A에 대해서 가능한 모든 순열의 개수가 n개라고 한다면 i번째 순열과 n-i-1번째 순열의 합집합은 어떤 숫자 집합 A와 같다. 이를 통해 반복문을 n/2번만 돌려서 최적화를 할 수 있었다.
#14889번 스타트와 링크
from itertools import combinations
n = int(input())
s = [[0]*n for i in range(n)]
for i in range(n) :
s[i] = list(map(int,input().split()))
team1 = [0]*n
team2 = [0]*n
answers = [] #정답들의 집합
all = list(combinations(range(1,n+1),n//2)) #가능한 모든 조합
def team_point(team) :
point = 0
for i in team :
for j in team :
point += s[i-1][j-1]
return point
for i in range(len(all)//2) : # 조합들의 반까지만 진행하여 한팀에, 나머지 반은 남은 팀으로 배정
team1 = all[i]
team2 = all[len(all)-1-i]
answers.append((abs(team_point(team1)-team_point(team2)))) # 정답들에 추가
print(min(answers)) # 가능한 정답 중 최솟값 출력'Problem Solving > 백준BOJ' 카테고리의 다른 글
| [백준BOJ] 단계별로 문제풀기 - 동적 계획법1 정답 및 후기[2](파이썬, python) (0) | 2021.02.05 |
|---|---|
| [백준BOJ] 단계별로 문제풀기 - 동적 계획법1 정답 및 후기[1](파이썬, python) (0) | 2021.02.02 |
| [백준BOJ] 단계별로 문제풀기 - 정렬 정답 및 후기(파이썬, python) (0) | 2021.01.27 |
| [백준BOJ] 단계별로 문제풀기 - 브루트 포스 정답 및 후기(파이썬, python) (0) | 2021.01.25 |
| [백준BOJ] 단계별로 문제풀기 - 재귀 정답 및 후기(파이썬, python) (0) | 2021.01.25 |
