SEB_BE 24일차 - 자료구조(Tree,Graph)

Daily coding

String[] word = str.split(" ") //공백 기준으로 문자열 나누어서 배열에 저장

💡 오늘의 학습목표

• Tree
• Graph
• BST
• BFS / DFS

📔 Tree

• 단방향 그래프 / 하나의 뿌리로부터 사방으로 가지가 뻗은 형태
• 계층적 자료구조 / 비선형 구조 (사이클이 없다)

  • 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
  • 루트(Root) : 트리 구조의 시작점이 되는 노드
  • 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
  • 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
  • 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

• 깊이(depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이 (루트는 0 )
• 레벨(Level) : 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현 / 같은 레벨은 형제노드
• 높이(Height) : 리트노드를 기준으로 루트까지의 높이로 표현
• 서브트리

📔 Graph

• 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조 / 복잡한 네트워크망
• 정점(Vertex), 간선(edge)
• 인접 행렬 ( 인접하면 1, 인접하지 않으면 0 ) 2차원 배열의 형태
• 인접 리스트 ( 각 정점마다 하나의 리스트(자신과 인접한 다른 정점을 담고있음)가짐)
• 가중치 그래프 : 연결의 강도가 적혀져있는 그래프
• 사이클 : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 것

📙 Binary Search Tree

• 이진 트리 : 자식노드가 최대 두 개인 노드들로 구성된 트리
• 이진 탐색 트리 : 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 부모보다 큰 값을 가짐.

Tree traversal 트리 순회

• 전위 순회
  루트 노드 - 왼쪽 노드 - 오른쪽 노드
• 중위 순회
  왼쪽 노드 - 루트 노드 - 오른쪽 노드
• 후위 순회
  왼쪽 노드 - 오른쪽 노드 - 루트 노드

---

📜 BFS (그래프)

• 가까운 정점부터 탐색 / 너비 우선 탐색

📜 DFS

• 하나의 경로를 끝까지 탐색한 후 다음 경로로 넘어가 탐색 / 깊이 우선 탐색

---

회고

페어분이랑 빡센 하루를 보냈다,,,그래도 혼자보단 둘이 같이 생각하니까 뭔가 진전이 있던 것 같다. 레퍼런스 코드가 아예 없었다면 어떻게 생각해서 구현해야 할지는 아직도 막막하다,,ㅠㅠ할 건 점점 많아지고 따라가기는 힘들어지고 걱정이다. 스프링 대비해서 인강도 먼저 좀 듣고 싶은데😂