안녕하세요. 우당탕탕 개발 일지 입니다. 인공지능 과목을 수강하며 여러 알고리즘을 공부하고 있습니다. BFS,DFS등 그래프 탐색 알고리즘을 공부하기에 앞서 알아야 하는 트리,그래프의 용어와 개념을 간단하게 정리 하겠습니다. 개인적인 필기이고 codetree로만 개념을 익히고 문제 풀었습니다. 용어는 개인적으로 이해한 표현을 적었고 정의는 아닐 수 있습니다.!
https://www.codetree.ai/ko/trail-info
코딩 테스트 학습 안내 | 코드트리
막막한 코딩테스트 준비, 혼자 헤매지 말고 체계적인 코딩 학습과 단계별 가이드로 빠르게 실력을 쌓아 취업에 성공하세요.
www.codetree.ai
1. 트리
그래프의 노드, 간선과 같은 단어가 전부 트리에서 나와서 트리를 먼저 공부 했습니다.
- 노드 = 정점 : 각 지점을 의미.
- 루트 노드 : 가장 최상위의 노드를 의미.
- 리프 노드 : 자식이 없는 노드를 의미.
- 간선 : 노드를 잇는 선.
- 높이: 최대 길이 +1 = 가장 긴 노드가 몇개가 이어져 있나? 느낌.
- 길이: 인덱스로 센 노드 느낌.
- 이진 트리: 자식 수가 최대 2개 (즉, 하나 일 수도 있음. ) -> 자식이 2개가 아닌 경우 비워 두고 배열을 채우면 됨!
2. 그래프 (graph) 기본
: 트리의 확장된 관계 , 부모-자식 관계로 표현하지 못하는 더 많은 관계를 표현할 수 있음.
-방향 그래프 : 양방향, 단방향 표시
(A ->B 인 경우 ) A에서 B로 밖에 전달 안됨.
-무방향 그래프: 양뱡향으로 간주.
-가중그래프 : 간선에 가중치 표현 (거리,시간 등을 나타냄. 그래프 조건마다 다름.)
- A의 차수 : A 노드와 연결된 다른 노드의 수.(간선 갯수)
- 진입 차수: 들어오는 화살표.
- 진출 차수: 나가는 화살표.
※방향 그래프인 경우 진입 차수, 진출 차수를 구분 하지만, 무방향 그래프인 경우 진입 차수와 진출 차수가 같음!
3. 그래프 표현 방법
1) 인접 리스트: 각 노드를 기준으로 연결된 노드를 저장하는 방식. (2차원 배열 느낌)★
2) 인접 행렬: " 노드수 x 노드수 " 만큼의 행렬에 저장하는 방식. (테이블 느낌)★
3) 간선 리스트 : 간선에 대한 정보만 저장하는 방식.
3-1) 인접 리스트
노드의 갯수 만큼 세로로 배열모양 그려주기
→ 1번 노드의 진출 차수인 노드의 번호 : 3,5번 (1-> 3 -> 5)식으로 표현.
→ 나머지 노드도 동일하게 진행!
※ 간선이 양방향인 경우) 둘 다 표시 해줘야 함!
※ 노드 기준으로 진입 차수는 표시 하지 않음!
3-2) 인접 행렬
A -> B : A를 세로로 B를 가로로 씀.
3-3) 간선 리스트
: 간선에 대한 정보만 저장하는 방법.
- 단방향인 경우
0 → 1 ->3
↓
2-> 4
간선 리스트 : {0,1} {0,2} {1,3} {2,4}
- 양방형인 경우
0 - 1 -3
ㅣ
2 - 4
간선 리스트: {0,1} {0,2} {1,3} {2,4} {1,0} {2,0} {3,1} {4,2}
'[알고리즘]' 카테고리의 다른 글
| [알고리즘] 그래프 탐색 방법 _BFS 와 DFS 쉽게 이해하기. (0) | 2025.04.08 |
|---|