2022.09.23 금 - 그래프, 트리, 이진탐색트리, BFS/DFS

📄 학습내용

그래프(Graph)

• 여러 정점들을 간선으로 연결해서 관계를 표현한 자료구조
• 구조
  • 직접적인 관계 : 두 정점이 하나의 간선으로 연결된 관계
  • 간접적인 관계 : 두 정점이 여러 개의 간선으로 연결된 관계
• 표현 방식
  1. 인접 행렬
     • 정점의 인접한 상태를 표현한 2차원 배열
     • 사용 : 두 정점 사이의 인접 관계 확인, 가장 빠른 경로(shortest path) 구할 때
     • ex) int[][] edges = new int[][] { {0, 0, 1}, {1, 0, 1}, { 1, 0, 0 } };
  2. 인접 리스트
     • 정점의 인접한 상태를 리스트로 표현
     • 메모리를 효율적으로 사용하고 싶을 때
     • ex) int[][] edges = new int[][] { { 1, 2 }, { 3 }, { 0, 1 }, { } };
• 용어
  • 정점(vertex) : 데이터(= 노드)
  • 간선(edge) : 정점을 연결하는 선
  • 인접(adjacency) : 두 정점이 하나의 간선으로 연결된 경우
  • 인접 정점(adjacent vertex) : 직접적인 관계에 있는 정점들
  • 가중치 그래프(weighted graph) : 간선에 비중을 둔 그래프
  • 비가중치 그래프(unweighted graph) : 모든 간선이 동일한 비중을 가진 그래프
  • 무(방)향 그래프(undirected graph) : 간선에 방향이 없는 그래프(= 일시 무향, 무향, 무방향)
  • 단방향 그래프(directed graph) : 간선에 방향이 정해진 그래프(= 일시 방향, 방향)
  • 진입차수(in-degree) : 한 정점으로 들어오는 간선의 개수
  • 진출차수(out-degree) : 한 정점에서 나가는 간선의 개수
  • 자기 루프(self loop) : 정점 자신이 다른 정점을 거치지 않고 자신에게 되돌아 오는 경우
  • 사이클(cycle) : 한 정점이 다른 정점들을 거쳐서 다시 정점으로 돌아갈 수 있는 경우

 

트리(Tree)

• 사이클이 없는 그래프 구조(그래프의 일종)
• 비선형 구조, 무뱡항 계층적 자료구조
• 용어
  • 노드(Node) : 각각의 데이터
  • 루트(Root) : 트리 구조를 시작하는 노드
  • 부모 노드(Parent Node) : 상하관계에 있는 두 노드 중 상대적으로 루트에 가까운 노드
  • 자식 노드(Child Node) : 상하관계에 있는 두 노드 중 상대적으로 루트에 먼 노드
  • 형제 노드(Sibling Node) : 같은 레벨에 있는 노드
  • 리프 노드(Leaf Node) : 자식이 없는 노드
  • 간선(Edge) : 노드와 노드를 연결한 선
  • 깊이(Depth) : 루트를 기준으로 아래로 내려가는 깊이 표현
  • 레벨(Level) : 같은 깊이를 묶어서 레벨로 표현
  • 높이(Height) : 리프 노드를 기준으로 위로 올라가는 높이 표현
  • 서브 트리(Sub Tree) : 전체 트리 구조에서 트리 구조를 갖춘 작은 트리 구조

 

이진탐색트리(Binary Search Tree, BST)

• 이진트리(Binary Tree)
  • 자식 노드가 최대 두 개인 트리 구조
  • 종류
    • 정이진트리(full binary tree) : 각 노드는 자식 노드로 0개 또는 2개를 가지는 트리
    • 포화이진트리(perfect binary tree) : 모든 리프 노드의 레벨이 동일하고, 각 레벨이 전부 채워진 트리
    • 완전이진트리(Complete binary tree) : 마지막 레벨을 제외한 노드들으 전부 채워져있고, 마지막 레벨의 노드는 최소 왼쪽은 전부 채워진 상태의 트리
• 이진탐색트리(Binary Search Tree)
  • 왼쪽 자식들의 값은 루트보다 작고, 오른쪽 자식들의 값은 루트보다 큰 특징을 가지는 이진트리
  • 값 삽입/삭제 시 균형 틀어짐으로 인한 탐색 시간 증가 문제가 발생 가능 → 삭제/삽입 시 트리 구조 재조정하는 과정 필요

 

트리/그래프 순회

• 트리/그래프 순회 : 모든 노드를 한 번씩 방문하는 것
• 순회 방법 : DFS, BFS

 

• 깊이우선탐색(Depth-First Search, DFS)
• 탐색방법
  1. 전위 순회(pre-order traversal) : root → Left → Right
  2. 중위 순회(in-order traversal) : Left → root → Right
  3. 후위 순회(post-order traversal) : Left → Right → root
• 크기가 클수록 깊이우선탐색이 유리
• 구현 : stack 또는 재귀

 

• 너비우선탐색(Breadth-First Search, BFS)
• 탐색방법
  • 레벨 순회(level-order traversal) : 레벨 순으로 방문(level 1 → level 2 ... )
• 크기가 작을수록 너비우선탐색이 유리
• 구현 : queue

 

⭐ 공부 난이도

그래프, 트리, 이진탐색트리, BFS/DFS 이론 ☆☆☆☆★

그래프, 트리, 이진탐색트리, BFS/DFS 구현 ☆☆☆★★

 

🌕 느낀점

   오늘 이론도 예전에 자료구조를 공부해서 크게 어렵지는 않았다. 배운 내용을 이용해서 문제를 해결하려고 코드를 작성하는 것이 어려울 것으로 예상된다. 적합한 자료구조를 이용해서 문제를 해결하기 위해서 관련 문제를 자주 풀어봐야겠다. 어제 먹었던 것이 체해서 집중을 제대로 하지 못했다. 몸관리를 정말 잘해야겠다.