[Algorithm] Graph & Tree

Tree와 Graph에 대해 알아보고 실무에서는 거의 쓰이지 않는 알고리즘 문제들을 풀어보고자 한다.

사실 개념만 이해하고 기 구현된 라이브러리들을 사용하면 된다. ( 있는걸 알아야 찾아서 쓰지 )

 

Tree

• What is this?
  • 방향을 가지는 비순환 구조 
  • Node와 Edge로 구성
• Searching
  • Preorder
    • 왼쪽 자식노드부터 오른쪽 자식 노드까지 탐색
    • recursive하게 간단 구현
  • Inorder
    • 맨 왼쪽이 노드부터 탐색 시작
    • 탐색이 끝나면 루트를 거처 오른쪽 노드로 이동
    • 탐색 계속
  • postorder
    • 맨 왼쪽 노드부터 탐색시작
    • 탐색이 끝나면 루트를 거치지 않고 노드로 이동
    • 모든 하위노드 탐색이 끝나면 루트 탐색
• Binary Searching Tree
  • 각 노드가 유일키를 가질때
  • 루트노드의 왼쪽 서브 트리는 루트보다 작은값으로 이루어짐
  • 루트노드의 오른쪽 서브 트리는 투트보다 큰 값으로 이루어짐
  • 시간복잡도는 O(N)으로 빠른 서치가 가능
  • Building과 Searching이 동시에 이루어져 빠름
  • 규형잡힌 구조가 아닐때는 비효율적

Graph

• What is this?
  • Vertical (node)와 Edge로 구성
  • 순환 구조
  • 방향없음
• Searching
  • DFS ( 깊이 우선 탐색 )
    • 하위 노드들을 먼저 탐색하는 구조
    • 하위 노드들을 추상화하여 recursive가 가능한 구조
    • stack (recursive)를 이용하여 구현이 간단!
  • BFS ( 넓이 우선 탐색 )
    • 인접한 노드들을 먼저 탐색하는 구조
    • 미지의 하위탐색 노드들일 존재하므로 queue를 이용하여 기록 및 탐색 
    • 완전탐색