자료구조 기초

Chapter3. Tree와 Graph
 Chapter3-1. Tree
  1.트리의 개념과 특징, 용어에 대해 이해합니다.
  2.트리의 실사용 예제를 보고, 트리가 어떻게 이용이 되는지 이해합니다. 
  3.직접 구현한 트리가 어떤 식으로 동작하는지 이해하고, 해당 클래스 내의 로직을 이해합니다.
 Chapter3-2. Binary Search Tree
  4.이진 탐색 트리의 개념과 종류 특징에 대해 이해합니다.
  5.직접 구현한 이진 탐색 트리가 어떤 식으로 동작하는지 이해하고, 해당 클래스 내의 로직을 이해합니다.
 Chapter3-3. Tree Traversal
  6.전위 순회, 중위 순회, 후위 순회의 개념과 각 순회가 어떤 식으로 탐색하는지 이해합니다.
  7.전위 순회, 중위 순회, 후위 순회가 어느 상황에서 사용되는지 이해합니다.
 Chapter3-4. Graph
  8.그래프의 개념과 구조, 표현 방식에 대해 이해합니다.
  9.매트릭스(행렬)와 리스트의 장단점에 대해 이해합니다.
  10.그래프의 실제 사용 예제를 보고, 어떤 식으로 그래프가 사용되는지 이해합니다.
  11.직접 구현한 그래프를 구현하는 데 필요한 것이 무엇이었는지 이해하고, 로직을 파악합니다.
 Chapter3-5. BFS와 DFS
  12.너비 우선 탐색과 깊이 우선 탐색의 개념과 특징에 대해 이해합니다.
  13.너비 우선 탐색과 깊이 우선 탐색의 장단점에 대해 파악합니다.
  14.그래프가 굉장히 크다면 어떤 탐색 기법을 고려해야 하는지 이해합니다.
  15.그래프의 규모가 작고 depth가 얕다면 어떤 탐색 기법을 고려해야 하는지 이해합니다.

1.나무의 거꾸로 한 모습의 형태의 구조로 단방향의 특징을 가지고 있으며 시작점을 root, 형제를 Sivling, 부모와 자식 노드가 있으며 root의 반대개념인 자식이 없는 마지막 노드는 Leaf라고 부른다.

2.Tree는 컴퓨터의 디렉토리에서 대표적으로 이용되는데 모든 폴더는 루트폴더에서 시작되어 가지를 뻗어나간다.

3.트리를 구현할 때 메서드도 동작시키기 위해서 new Tree(value)를 사용해줘야한다. (여기서 Tree는 트리 클래스명)

4.이진 탐색 트리는 일정한 규칙을 가지고 최대 두개의 자식노드만 보유할 수 있는 노드로 작은 숫자는 왼쪽, 큰 숫자는 오른쪽에 위치시키는 것을 반복한다.

5.이진트리는 해당 값의 자리를 찾을 때 까지 재귀적으로 반복하는 특징이 있으며 10억개의 자료가 쌓여있어도 대략 30번의 계산으로 내려갈 수 있을만큼 효과적이다. 다만 중복되는 값이 없어야 한다.

6.전위, 중위, 후위에는 큰 차이는 없는데 전위는 재귀 시작 전 노드를 순회하며 중위는 재귀 중간(left, right 사이)에 들어가고 후위는 재귀 다음 순서에 들어간다. 이 차이는 노드를 좌측 완료 후 노드 방문 후 우측으로 가는지 또는 좌, 우가 끝난 후 마지막으로 시행되는지의 차이를 결정한다.

7.전위 순회는 부모 노드를 먼저 방문하는 특징이 있기 때문에 부모노드가 먼저 생성되어야 하는 복사등에 이용되고 중위 순회는 이진 탐색에서 작은 값인 좌측 -> 노드 -> 우측의 순서로 오름차순으로 값을 가져올 때 사용하며 후위순회는 부모 노드를 마지막에 조회하는 특징을 이용해 노드의 삭제에 이용한다.

8.그래프는 각각의 점(정점)을 이어준 선(간선)으로 구성되어있다. 간선은 단방향일 수 있고 양방향일 수 있으며 스스로가 스스로를 가리킬 수도 있다.

9.매트릭스는 가능한 모든 경우의 수를 저장하기 때문에 리스트에 비해 상대적으로 메모리를 많이 차지한다.

10.일반적으로는 길찾기에 사용되는데 각각의 경로마다 가중치를 부여해 최적의 경로를 찾는데 이용한다.

11.그래프를 구현하는 것에는 일반적으로 매트릭스가 필요한데 간선에 따라 값을 편하게 넣어줄 수 있었다.

12.너비 우선 탐색(BFS)는 일반적으로 최단, 최적 경로를 찾을 때 사용하며 깊이 우선 탐색(DFS)는 완전탐색(경로)을 위해 사용한다.

13.너비 우선 탐색은 위에 언급했던 최적경로를 찾을 수 있다는 장점이 있고 깊이 우선 탐색은 모든 경로를 완전하게 탐색하고 다음으로 넘어가는 특징이 있기 때문에 특정 목적지를 찾는 것은 더 빠를 수 있으며 더 느린 경우라도 모든 노드를 완전히 탐색할 수 있는 장점이 있다.

14.굉장히 크다고 해도 거리가 중요한데 모든 경로보다는 가까운 경로 대상으로 빠르게 훑어보고 싶은 경우는 BFS를 사용하며 일반적으로는 규모가 클 경우 DFS를 사용한다.

15.depth가 얕다면 굳이 DFS를 사용할 의미가 없기 때문에 BFS를 사용한다.

드디어 회고폭격에서 벗어날 수 있을 것 같다.
사실 회고를 하면서 여러가지로 가이드라인을 제공받아 편하게 복습할 수 있었지만
지나친 양으로 곤란스러울 때도 많았다.