경일 메타버스 20220629 13주차 3일 수업내용. 자료구조와 알고리즘-트리, 이진 검색 트리, 오답노트

https://github.com/ChoiSeonMun/Solutions

다른 방식을 배워보자.

자료

https://docs.google.com/document/d/1wUms27Vj8si-jEjfRQJwSvsQ2CJNCv4IU6GOtesY4TE/edit

트리(Tree)

• 그래프의 일종으로 계층형 자료구조(Hierarchical Data Structure)다.

• 노드(Node)와 간선(Edge)으로 구성된다.

• 노드(Node) :
  데이터가 저장되어있다.

• 간선(Edge) :
  노드 간 관계를 표현한다.

• STL 상의 구현

  • std::set
    https://en.cppreference.com/w/cpp/container/set
  • std::map
    https://en.cppreference.com/w/cpp/container/map
  • std::multiset
    https://en.cppreference.com/w/cpp/container/multiset
  • std::multimap
    https://en.cppreference.com/w/cpp/container/multimap

용어

• 루트(Root) 노드 :
  트리의 시작 노드

• 리프(Leaf) 노드 :
  트리의 끝 노드, 가장 말단의 노드

• 부모(Parent) 노드 :
  상위 노드

• 자식(Child) 노드 :
  하위 노드

• 서브 트리(Sub-tree) :
  트리 내부의 작은 트리. 트리는 재귀적 구조를 가지고 있다. (프랙탈 구조)

• 레벨 :
  계층.

  • 레벨 0 :
    루트 노드가 있는 레벨, 여기서 아래로 내려갈수록 레벨은 올라간다.

• 트리의 높이 :
  트리의 깊은 정도, 레벨이 가장 깊은 순간

• 시블링(Sibling) 노드 :
  같은 레벨에 있는 노드

• 조상(Ancestor) 노드 :
  한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드

• 자손(Descendant) 노드 :
  조상 노드의 반대

• 차수(Degree) :
  한 노드가 가지는 서브 트리의 수. 노드의 차수 중 최댓값을 트리의 차수라 한다. 결국은 간선 수

• 내부(Internal) 노드 :
  단말 노드를 제외한 나머지 노드

• 포레스트(Forest) :
  트리의 집합

순회

1. 전위 순회(Pre-Order Traversal) :

   1. 나 자신을 가장 먼저 방문한다.

   2. 가능한 만큼 깊숙이 탐색을 하고, 끝에 다다르면 부모 노드로 돌아가 다음 자식 노드를 탐색한다.

   3. DFS와 흡사하다.

   4. 위 그림에서는,
      A - B - D - H - I - E - J - C - F - G

2. 중위 순회(In-Order Traversal) :

   1. 나 자신을 중간에 방문한다.

   2. 왼쪽을 먼저 방문하고, 그 다음 자신을 방문한 후에 오른쪽을 방문한다.

   3. 위 그림에서는,
      H - D - I - B - J - E - A - F - C - G

3. 후위 순회(Post-Order Traversal) :

   1. 나 자신을 가장 마지막에 방문한다.

   2. 먼저 자식 노드를 모두 탐색하고, 부모 노드로 올라가 탐색한다.

   3. 위 그림에서는,
      H - I - D - J - E - B - F - G - C - A

4. 레벨 순회(Level-Order Traversal) :

   1. 낮은 레벨부터 차례대로 노드를 방문한다.

   2. BFS와 흡사하다.

   3. 위 그림에서는,
      A - B - C - D - E - F - G - H - I - J

• B트리
  • 데이터 베이스, 혹은 파일 시스템이라는 프로그램에서 사용.

이진 검색 트리(Binary Search Tree)

• 한 노드를 기준으로
  왼쪽 서브 트리는 모두 그 노드보다 작은 값을 가지고 있으며,
  오른쪽 서브 트리는 모두 그 노드보다 큰 값을 가지고 있는
  이진 트리(Binary tree)이다.

  • 이진 트리(binary tree) :
    트리의 차수가 2 이하인 트리

• 왼쪽 자식 노드 값 <= 부모 노드 값 <= 오른쪽 자식 노드 값

• STL에 구현된 트리 컨테이너는 모두 이진 검색 트리다.

연산

• 이진 탐색 트리의 연산은 트리의 형태에 따라 시간 복잡도가 달라진다.

  • 균형 잡혀 있다면 모든 연산이 O(logN)이다.

  • 편향되어 있다면 O(N)에 가까워진다.

    • 편향 : 노드가 한 쪽으로만 삽입되어 있다.

• 이진 검색 트리를 중위 순회하면 수가 오름차순으로 정렬된다.

• AVL 트리
  자가 균형 이진 탐색 트리
  • 어떻게 데이터를 삽입해도 회전을 시켜 균형을 맞춘다.
    [코드라떼] 자바 자료구조 - AVL 트리 개념

• 레드-블랙 트리
  자가 균형 이진 탐색 트리. AVL 트리보다 발전되었다.
  • STL의 set, map, multiset, multimap 모두 레드-블랙 트리이다.

백준 풀이

2022. 06. 29 그래프 순회 예제 : 백준 2667번 단지번호붙이기 풀이

• 그래프의 가중치가 모두 동일한 경우,
  BFS로 최단 경로를 구할 수 있다.

오답노트 : 백준 15829 백준 7576 백준 1697 백준 18111

• 백준 15829 Hashing
  큰 수의 처리를 험하게 했다. 다른 사람들의 알고리즘을 참고하여 큰 수의 처리를 철저히 배우자.
• 백준 7576 토마토1
  map 등 기반적인 데이터를 1차원 배열로 도전하다가 실패하여 2차원 배열로 전환하였다. 그 과정에서 초기화를 memset으로 전환하였다. 더 세련된 방법은 없는지 다른 알고리즘을 찾아보자.
• 백준 1697 숨바꼭질
  BFS뿐만 아니라 재귀 함수 등 다양한 방법이 있다. 찾은 방법 말고도 다양한 방법을 찾고 시험해보자.
  제출번호 43178933 pean04 다른 풀이
  
• 백준 18111 마인크래프트
  정상적으로 작동하는 코드를 짰지만, 시간 초과로 실패. 시간 단축이 도통 안돼서 결국 다른 사람의 코드를 참고했다. 다시 내 스스로 해보고, 다른 알고리즘도 찾아보자.
  Inspired by
  https://codecollector.tistory.com/678