✔️ 중위 표기법(infix notation): 연산자를 피연산자의 가운데 표기하는 방법 e.g.) A + B ✔️ 후위 표기법(postfix notation): 연산자를 피연산자 뒤에 표기하는 방법 e.g.) AB +
✅ 중위표기법 → 후위표기법 변환 방법 1
괄호를 사용하여 우선순위에 따라 수식의 연산자를 다시 표현함
각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동시킴
괄호를 제거함
<예제> A * B - C / D
a단계. ((A * B) - (C / D))
b단계. ((A B) * (C D) / ) -
c단계. A B * C D / -
✅ 중위표기법 → 후위표기법 변환 방법 2 (Stack 이용)
입력 받은 중위 표기식에서 토큰을 읽음
✔️ 토큰 : 퀵 정렬에서의 pivot과 같이, 주어진 입력에서 문자 하나하나를 '대상으로 함'을 의미하는 별칭(?))
토큰이 피연산자이면 토큰을 출력함
토큰이 연산자(괄호 포함)일 때, 이 토큰이 스택의 top 에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 push() 하고, 그렇지 않다면 스택 top 의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop() 한 후 토큰의 연산자를 push() 함 (만약, top 에 연산자가 없다면 push() 함)
토큰이 오른쪽 괄호’)’이면 스택 top 에 왼쪽 괄호 ‘(’가 올 때까지 스택에 pop() 연산을 수행하고 pop() 한 연산자를 출력함 (단, 왼쪽 괄호를 만나면 pop() 만 하고 출력하지는 않음)
2. 중위 표기식에 더 읽을 것이 없다면 중지하고, 더 읽을 것이 있다면 a번부터 다시 반복함
3. 스택에 남아 있는 연산자를 모두 pop() 하여 출력함
(스택 밖의 왼쪽 괄호는 우선 순위가 가장 높으며, 스택 안의 왼쪽 괄호는 우선 순위가 가장 낮음)
백트래킹이 가지치기(Prunning)할 때 왔던 길을 되돌아간다는 점에서 재귀 호출 방식이 유용하게 작용하는데, 이를 DFS 방식을 혼용하여 적용함으로써 탐색 효율을 높일 수 있다.
백트래킹 기법은 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있음
💡결정 문제란? 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes/no로 답하는 문제
- 미로 찾기 - n-Queen 문제 - Map coloring - 부분 집합의 합(Subset Sum) 문제 등
✅ 백트래킹 개념
⭐ 상태 공간 트리의 DFS(깊이 우선 탐색)을 실시하고, 각 노드의 유망성(promising)을 점검하여 결정함. 그리고 만약 유망하지 않다고 결정되면, 그 노드의 부모 노드로 되돌아가(backtracking) 다음 자식 노드로 이동함
여러 선택지(옵션)가 존재하는 상황에서 한가지를 선택
선택이 이루어지면 새로운 선택지들의 집합이 생성
위 선택 과정을 반복하면서 최종 상태에 도달
올바른 선택을 계속하다보면 목표 상태(goal state)에 도달함
📌 유망성(promising) 어떤 노드를 방문하였을 때, 그 노드를 포함한 경로가 해답이 될 수 없다면 해당 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 '유망하다'고 한다.
📌 가지치기(prunning) 유망하지 않은 노드가 포함된 경로는 더이상 고려하지 않는다.
# 백트래킹 알고리즘 의사 코드
checknode (node v):
if promising(v):
if solution in v:
write the solution
else:
for child of v:
checknode(child)
✅ 백트래킹을 이용한 알고리즘
상태 공간 트리의 깊이 우선 검색을 실시
각 노드의 유망성을 점검
만일 해당 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속함
✅ 미로 찾기 (with Stack)
입구와 출구가 주어진 미로에서 4방향으로 이동하며 입구부터 출구까지의 경로를 찾는 문제
예시는 백트래킹의 대표적 예시인 N-Queen
# 일반 백트래킹 알고리즘
def checknode (v): # node
if promising(v):
if there is a solution at v:
write the solution
else:
for u in each child of v:
checknode(u)
✅ 상태 공간 트리(state-space tree)로 표현한 미로 찾기
→ 깊이 우선 검색(DFS)으로 탐색하는 경우 155 노드를 거쳐가지만, 백트래킹(backtracking)을 적용하면 27 노드만을 탐색하게 된다.
# 상태 공간 트리 - 백트래킹
bool backtrack(선택 집합, 선택한 수, 모든 선택 수){
// 더이상 탐색할 노드가 없을 때
if(선택한 수 == 모든 선택 수){
찾는 솔루션인지 체크;
return 결과;
}
현재 선택한 상태집합에 포함되지 않는 후보 선택들(노드) 생성;
모든 후보 선택들에 대해{
선택 집합에 하나의 후보 선택을 추가;
선택한 수 += 1;
결과 = backtrack(선택 집합, 선택한 수, 모든 선택 수);
if(결과 == 성공){
return 성공; // 성공한 경우 상위로 전달함
}
}
return 실패;
}
✅ Backtracking과 깊이 우선 탐색(DFS)의 차이
백트래킹(Backtracking)은 어떤 노드에서 출발하는 경로가 해가 아닌 것 같으면 더 이상 그 경로를 따라가지 않으므로 시도의 횟수를 줄임 e.g.가지치기(Prunning)
깊이우선탐색(DFS, Depth First Search)은 모든 경로를 추적하므로 N!과 같이 경우의 수가 많은 경우, 문제 처리에 어려움이 발생함
But, 백트래킹(Backtracking) 알고리즘 역시 최악의 경우에는 지수함수 시간(Exponential Time) 을 요하므로 문제 해결에 어려움이 발생할 수 있음
앞선 미로찾기 문제의 경우, 깊이 우선 검색은 155 노드, 백트래킹은 27노드의 트리를 탐색함
🌿가지치기(Prunning) 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는 것을 의미 (즉, 더이상 탐색할 필요가 없는 상태를 제외함)
✅ N-Queen 문제
대표적인 백트래킹(backtracking) 문제로, nxn의 서양 장기판에 배치한 Queen들이 서로를 위협하지 않도록 n개의 Queen을 배치하는 문제이다.
📌 8 - Queens 문제 퀸 8개를 8x8 크기의 체스판 안에 서로를 공격하지 않도록 배치하는 모든 경우의 수를 구하는 문제
▷ 후보 해의 수
▷ 실제 해의 수는 92개뿐이다.
▶4 - Queens 문제로 축소해서 생각해보자. - 같은 행에 위치할 수 없으며, 모든 경우의 수는 4x4x4x4 = 256가지이다.
어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합을 powerset이라고 하며, 구하고자 하는 어떤 집합의 원소 개수가 n인 경우 부분집합의 개수는 $2^n$개이다.
✅ 비트맵을 활용한 부분집합 생성 및 부분집합의 합 구하기
# 1. 다중 for문으로 구현하는 방법
bit = [0, 0, 0, 0]
for i in range(2):
bit[0] = i # 0번째 원소
for j in range(2):
bit[1] = k # 1번째 원소
for k in range(2):
bit[2] = k # 2번째 원소
for l in range(2):
bit[3] = l # 3번째 원소
print(bit) # 생성된 부분집합 출력
# 2. 재귀함수로 구현하는 방법
def powerset(bit_arr, idx):
if idx == N:
print(bit_arr)
return
for i in range(2):
bit_arr[idx] = i
powerset(bit_arr, idx + 1)
arr = [1, 2, 3, 4, 5]
N = len(arr)
powerset([None] * N ,0)
✅ 부분집합을 구하는 백트래킹(backtracking) 알고리즘
# a: 주어진 배열, k: 결정할 원소, n: 원소 개수
def backtrack(a, k, n):
c = [0] * MAXCANDIDATES
if k == n:
process_solution(a, k) # 답이면 원하는 작업을 실행
for i in range(k):
if a[i]:
print(num[i], end = ' ')
print()
else:
ncandidates = construct_candidates(a, k, n, c)
for i in range(ncandidates):
a[k] = c[i]
backtrack(a, k + 1, n)
MAXCANDIDATES = 2
NMAX = 4
a = [0] * NMAX
num = [1, 2, 3, 4]
backtrack(a, 0, 3)
# 동일한 숫자가 포함되지 않았을 떄, 각 자리 수별로 loop문을 이용하여 구현
for i1 in range(1, 4):
for i2 in range(1, 4):
if i2 ! = i1:
for i3 in range(1, 4):
if i3 ! = i1 and i3 ! = i2:
print(i1, i2, i3)
✅ 백트래킹(Backtracking)을 이용하여 {1, 2, 3, 4}에 대한 순열과 조합 생성
# 순열
def backtracking_perm(arr, k):
if len(arr) == k:
print(arr, end = ' ')
return arr
for i in range(len(array)):
if used[i] == False:
used[i] = True
backtracking(arr + [array[i]], k)
used[i] = False
# 조합
def backtracking_comb(arr, k, idx):
if len(arr) == k:
print(arr, end = ' ')
return arr
for i in range(idx + 1, len(array)):
if used[i] == False:
used[i] = True
backtracking_comb(arr + [array[i]], k, i)
used[i] = False
array = [1, 2, 3, 4]
k = 2
used = [False for i in range(len(array))]
backtracking([], k)
print()
backtracking_comb([], k, -1)
"""
# 출력
[1, 2] [1, 3] [1, 4] [2, 1] [2, 3] [2, 4] [3, 1] [3, 2] [3, 4] [4, 1] [4, 2] [4, 3]
[1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4]
"""
