TIL: 2022-11-18

⚙️ 오늘 배운 주제

자료구조 - 트리, 그래프

🐹 오늘의 기분

트리와 그래프는 독학으로 찍먹을 해봤어서 이번에도 개념 자체는 크게 낯설지가 않았다. 하지만 막상 이걸 이용한 문제를 풀어보려 했을 때 막힌 적이 많았어서 이 기회에 제대로 배워보고자 오늘은 눈에 불을 켜고 공부했다. 아무리 생각해도 하루만에 개념 학습과 코플릿까지 푸는 건 무리였던 것 같다. 구현 부분은 어제보다 살짝 더 까다롭게 느껴졌고 다른 문제는 진짜 어려워서 결국 레퍼런스를 참고했다. 그래도 10번 문제는 페어분이랑 고민한 끝에 스스로 풀어내서 이것만으로도 꽤 뿌듯하다. 이제 못 풀었던 문제들 풀이 분석해보고 스스로 풀어봐야겠다. 맨 마지막 바코드 문제는 문제도 못 읽어보고 끝나서 찬찬히 봐봐야겠음! 아 오늘치 코플릿도 이해 못해서 그것도 다시 봐야한다ㅎㅠ🥹

🗝 키워드

트리, 그래프, 이진 트리, 이진 탐색 트리, 인접 행렬, 인접 리스트, DFS, BFS

🗣 스스로에게 설명

Tree

비선형 구조의 계층적 자료구조
계층적으로 표현되고, 아래로만 뻗어나가기 때문에 cycle이 없다.
*cycle = 시작 노드에서 출발해 다른 노드를 거쳐 다른 노드로 돌아올 수 있다.
*self loop = 시작 노드와 목표 노드가 같다. (다른 노드를 아예 거치지 않고 바로 자기 자신으로 돌아옴)

 

트리는 하나의 연결 그래프

루트, 형제, 부모, 자식, 리프 노드가 존재

하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결

 

깊이, 레벨, 높이

깊이: 0부터 시작
레벨: 1부터 시작 (같은 깊이를 가지고 있는 노드를 묶어서 표현)
높이: 리프 노드를 기준으로 루트까지의 높이
--> 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가짐, 각 리프 노드의 높이를 0으로 놓음.

트리 실사용 예제

컴퓨터의 디렉토리 구조
- 루트 폴더 /에서 시작하는 트리 구조이다.

월드컵 토너먼트 대진표, 가계도, 조직도 등

Binary Tree

자식 노드가 최대 두 개인 노드들로 구성된 트리

정 이진 트리, 완전 이진 트리, 포화 이진 트리로 나뉨

정 이진 트리: 각 노드가 0개 혹은 2개의 자식 노드를 가짐 (1개 X)
포화 이진 트리: 모든 레벨이 가득 채워져 있는 트리
완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 함.

Binary Search Tree

이진 탐색 + 연결 리스트
빈번한 자료 입력과 삭제 가능하게끔

왼쪽에는 자신보다 작은 key를 갖는 노드들로, 오른쪽에는 자신보다 큰 key를 갖는 노드들로
서브트리들도 전부 이진 탐색 트리의 조건을 만족해야 함.

장점

• 기존 이진 트리보다 탐색 속도가 빠르다.
• 탐색 과정
  1. 루트 노드의 키와 찾고자 하는 값을 비교, 찾고자 하는 값이라면 탐색 종료
  2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브트리로 탐색 이동
  3. 반대로 크다면 오른쪽 서브트리로 이동
     최대 시간복잡도: O(h)

트리 순회 (부모 노드 탐색 순서 기준)

전위 순회 (preorder traverse)

MLR
부모 노드를 제일 먼저 방문
부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용

중위 순회 (inorder traverse)

LMR
부모 노드를 중간에 방문
이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰임.

후위 순회 (postorder traverse)

LRM
부모 노드를 나중에 방문
트리를 삭제할 때 쓰임 (자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문)

Graph

여러 개의 정점(vertex)들이 간선(edge)으로 복잡하게 연결된 관계를 표현한 자료구조

표현 방식

1. 인접 행렬

정점 A가 정점 B와 연결되어 있다면 1, 아니라면 0으로 표시한 표 (가중치가 있다면 1이 아닌 다른 값으로 저장)

 

언제 쓸까?
- 두 정점 사이에 관계가 있는지 없는지 확인할 때.
- 가장 빠른 경로를 찾을 때.

2. 인접 리스트

각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
각 정점마다 하나의 리스트를 가짐.

메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용함.

탐색

그래프의 데이터는 배열처럼 정렬되어 있지 않음. (비선형구조)
원하는 자료를 찾으려면 하나씩 모두 방문해야 한다.

BFS는 주로 두 정점 사이의 최단 거리를 찾을 때 사용
DFS는 해당 경로를 완벽하게 탐색할 때 사용, 모든 노드를 완전히 탐색할 수 있음

모든 정점을 한 번만 방문한다는 공통점
서로의 장단점이 분명함.

 

Q. 그래프의 규모가 작고 depth가 얕다면 어떤 탐색 기법을 써야 할까?
- DFS

 

Q. 그래프가 굉장히 크다면 어떤 탐색 기법을 써야 할까?
- BFS
DFS는 무한대에 가까운 깊이를 가지는 트리나 그래프의 경우에는 정답을 찾을 수 있다는 보장을 할 수 없다.

이런 경우에는 BFS를 쓰는 것이 적절하다. 

 

참고

생물정보 전문위키, 인코덤

🔍 공부가 더 필요한 부분

인접 리스트 구조 이해하기