Today I learned
2022/01/24
회고록
1/24
항해 99, 알고리즘 2주차
교재 : 파이썬 알고리즘 인터뷰
12장 그래프
1. 이론
백트래킹(Backtracking)
해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.
즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.
이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.
일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.
정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것입니다.
즉 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 됩니다.
주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있습니다.
👍 백트래킹 기법의 유망성 판단
어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 갑니다.
해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 하는 것입니다.
2. 문제
https://www.acmicpc.net/problem/9095
3. MySol
- Back Tracking
def solution(pwLength, numOfChar):
result = []
visited = []
def dfs_stack(start):
for node in range(start, numOfChar):
visited.append(charList2[node])
if len(visited) == pwLength:
result.append(visited[:])
visited.pop()
continue
else:
dfs_stack(node+1)
visited.pop()
return
dfs_stack(0)
def pwCheck(lists):
for i in lists:
jaUm = 0
moUm = 0
for char in i:
if char in 'aeiou':
moUm+=1
else:
jaUm+=1
if jaUm>=2 and moUm>=1:
print(''.join(i))
pwCheck(result)
return
if __name__ == '__main__':
lists = input().split(" ")
pwLength = int(lists[0])
numOfChar = int(lists[1])
charList2 = list(input().split())
#charList = ['a','t','c','i','s','w']
charList2.sort()
solution(pwLength, numOfChar)
# for i in result:
# temp = ''.join(i)
# print(temp)
4. 배운 점
- 해당 문제는 이해하게 되면 DFS및 재귀함수에 대해 이해하는데 굉장히 큰 도움이 되는 문제이다.
5. 총평
재귀, DFS 훈련
