백트래킹
백트래킹의 개념
- 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로 시도의 횟수를 줄임.
- 깊이 우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단
- 깊이 우선 탐색을 가하기에는 경우의 수가 너무나 많음
백트래킹 기법
- 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감.
- 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.
절차
- 상태 공간 트리의 깊이 우선 검색 실시
- 각 노드가 유망한지 점검
- 만일 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색
def dfs(level):
if level == 3:
print(*path)
return
for i in range(len(arr)):
if arr[i] in path:
continue
path[level] = arr[i]
dfs(level + 1)
path[level] = 0
dfs(0)트리
트리의 개념
- 두 노드 사이에는 유일한 경로가 존재한다
- 각 노드는 최대 하나의 부모 노드가 존재할 수 있다
- 각 노드는 자신 노드가 없거나 하나 이상이 존재할 수 있다.
비선형구조
- 원소들 간에 1:n 관계를 가지는 자료구조
- 원소들 간에 계층 관계를 가지는 자료구조
- Node : 트리의 원소이고 정점(vertex)라고도 한다.
- Edge : 간선이라고도 불리며 노드를 연결하는 선
- subtree : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
- 차수(degree) = 트리의 높이 = degree
이진 트리
- 모든 노드들이 최대 2개의 서브 트리를 갖는 특별한 형태의 트리
- 각 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리
- 포화 이진 트리
- 모든 레벨에 노드가 포화상태로 채어져 있는 이진트리
- 높이가 h일 때, 최대의 노드 개수인 (2^(h+1) - 1)의 노드를 가진 이진 트리
- 높이가 3일 때 -> 15개의 노드
- 순회(traversal) : 트리의 각 노드를 중복되지 않게 전부 방문 하는 것을 말하는데 트리는 비 선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계 알수 없다.
def inorder(nodeNum):
# 갈 수 없다면 skip
if nodeNum == None:
return
# 왼쪽으로 갈 수 있다면 진행
inorder(nodes[nodeNum][0])
print(nodeNum, end=' ')
# 오른쪽으로 갈 수 있다면 진행
inorder(nodes[nodeNum][1])
inorder(1)이진 탐색 트리의 성능
- 탐색, 삽입, 삭제 시간은 트리의 높이만큼 시간이 걸린다
- O(h), h : BST의 깊이(height)
- 평균의 경우
- 이진트리가 균형적으로 생성되어있는 경구
- O(log n)
- 최악의 경우
- 한쪽으로 치우친 편향 이진트리의 경우
- O(n)
- 순차탐색과 시간 복잡도가 같다
힙(heap)
- 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
- 최대 힙(max heap)
- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 > 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 큰 노드
- 최소 힙(min heap)
- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 < 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 작은 노드
- 힙에서는 루트 노드의 원소만을 삭제할 수 있다
- 루트 노드의 원소를 삭제하여 반환한다
- 힙의 종류에 따라 최솟값 또는 최대 값을 구할 수 있다
데이터 분석에서 백엔드까지...