C++

트리

• 데이터를 계층적으로 조작,관리하는 비선형 자료 구조
• 부모-자식 계층 구조

트리의 순회

전위 순회

• 부모 -> 왼쪽자식 -> 오른쪽 자식으로 순회하는 것

중위 순회

• 왼쪽자식 -> 부모 -> 오른쪽 자식

후위 순회

• 왼쪽자식 -> 오른쪽 자식 -> 부모

부모를 언제 탐색하냐에 따라 이름이 다르다고 생각하면 됨

이진 탐색 트리

• 정말 자주 사용

• 현재 노드보다 값이 작으면 왼쪽, 같거나 크면 오른쪽으로 이동

• 배열의 균형이 중요하기 때문에 자기 균형 이진트리 특히 레드블랙 트리가 많이 사용됨

• 문제 28. 트리 순회 - 프로토타입

• 문제 30. 예상 대진표 - 프로토타입

• 문제 31. 다단계 칫솔 판매 - 프로토타입

그래프

• 유한한 수의 정점, 이들을 연결하는 간선으로 이루어진 비선형 자료구조
• 간선, 노드, 가중치가 있음
• 그래프는 간선의 방향 유무에 따라 방향, 무방향 그래프로 나뉨
• 간선에 가중치가 있는경우 가중치 그래프라고 한다.
• 시작노드에서 다시 시작노드로 돌아오는 경로가 있는경우 순환이 있다고 함

인접 행렬

• 배열을 활용해서 구현
• 배열의 인덱스는 노드를, 배열의 값은 가중치를 나타낸다.

인접 행렬의 단점

• 노드수에 비해 간선이 적은 그래프 생성 시 메모리 낭비가 심하다.
• 노드수가 V라면 V X V 크기의 인접 행렬이 필요하기 때문에

인접 행렬의 장점

• 특정 간선이 있는지 확인하는 연산이 O(1)로 빠름

인접 리스트

• 노드의 개수만큼 배열을 준비
• graph[0].push_back({1, 5})라고 한다면 0 -> 1로 가는 가중치 5의 간선을 뜻한다.

인접 리스트의 단점

• 최악의 경우 간선 개수가 E일때 특정 간선의 존재를 확인하는데 O(E)의 시간이 걸림

인접 리스트의 장점

• 실제 연결된 노드들에 대해서만 연결하면 되므로 메모리 낭비가 없다.

그래프의 탐색

• dfs, bfs
• bfs는 공간복잡도가 높다. 여기서 찾은 답이 최단경로임이 보장된다.

문제 37. 너비 우선 탐색 순회 - 프로토타입
문제 41. 게임 맵 최단 거리 - 프로토타입
문제 42. 네트워크 - 프로토타입