# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 이전글: 트리-이진트리 정의/성질/분류/표현법 순회 traversal 이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것 전위 순회(preorder traversal) 중위 순회(inorder traversal) 후위 순회(postorder traversal) 전위 순회 preorder traversal 루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 이때 서브트리도 하나의 트리이므로, 그 트리 안에서 위의 과정을 또 거치면 된다. 쉽게 생각하면 왼쪽으로 계속 가다가 막히면 오른쪽으로 가는 방법이다. 예를 들..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 이전글: 트리-개념/용어정리 이진트리 binary tree 모든 노드가 2개의 서브 트리를 가지고 있는 트리 ※ 단, 서브트리가 공집합일 수 있음. 모든 노드의 차수 ≤ 2 공집합도 이진트리 서브 트리간의 순서 존재: 왼쪽, 오른쪽 성질 n 개의 노드를 가진 이진트리는 (n - 1)개의 간선을 가진다. 트리의 높이 = h → h ≤ 노드의 개수 ≤ 2^h - 1 노드의 개수 = n → ⌈log(n+1)⌉ ≤ 트리의 높이 ≤n * ⌈x⌉ : x 보다 작지 않은 최소의 정수(올림 연산) ex. ⌈2.4⌉ = 3 분류 1. 포화이진트리 full binary tre..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 트리 Tree 계층적인 자료를 표현하기에 적합한 자료구조 용어 정리 노드의 차수 degree - 어떤 노드가 갖고 있는 자식 노드의 개수 트리의 차수 - 트리가 갖고 있는 노드의 차수 중, 가장 큰 값 레벨 level - 트리의 각 층에 번호를 매기는 것. 루트의 레벨 = 1 깊이 depth - 루트에서 어떤 노드까지를 잇는 간선의 개수 높이 height ① 트리의 최대 깊이 ② 트리의 최대 레벨 ※ 때에 따라 높이가 2가지로 달리 해석된다. 여기서는 높이를 트리의 최대 레벨이라고 생각하기로 한다.

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 위상 정렬 Topological Sort 각 정점들의 선행순서를 위반하지 않으면서 모든 정점을 나열하는 것 생각의 순서 1. 진입차수가 0인 정점을 선택한다. (정점이 여러 개인 경우, 임의로 하나를 고른다.) 2. 선택된 정점과 이 정점에 부착된 간선들을 모두 삭제한다. 3. 2번에서 선택된 정점과 인접했던 정점들의 진입차수를 -1 한다. 4. 모든 정점이 사라질 때까지 1~3 과정을 반복한다. 알고리즘 HTML 삽입 미리보기할 수 없는 소스 그림으로 이해하기 아래의 방향 그래프에 대해 위상정렬을 수행해보자. 단, 핵심 키워드가 진입차수라는 점을 유의한다...

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. Floyd 알고리즘 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾아주는 알고리즘 Dijkstra 알고리즘에서는 '하나의 정점'에서 '다른 모든 정점'으로의 최단 경로를 찾았다면, Floyd 알고리즘에서는 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구할 수 있다. 즉, 그래프의 모든 정점에 대한 최단 경로쌍을 구할 수 있다. 이 알고리즘의 핵심 원리는 '거쳐가는 정점'을 기준으로 최단 경로를 구한다. 알고리즘 HTML 삽입 미리보기할 수 없는 소스 생각의 순서 1. 하나의 정점에서 다른 정점으로 갈 때, 바로 갈 수 있으면 '기존 인접..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. Dijkstra의 최단 경로 알고리즘 하나의 시작 정점으로부터, 모든 다른 정점까지의 최단 경로를 찾는 알고리즘. ≫임의의 두 정점 간의 거리는 항상 최단거리가 된다. 생각의 순서 시작정점 = v 정점 v의 인접정점에 대해서, weight[v][*] 값으로 distance[*] 값 초기화 집합 S에 포함 안된 정점에 대해서, 최소 distance 정점 u를 찾는다. 정점 u를 집합 S에 추가한다. 정점 u의 인접 정점 && 집합 S에 없는 정점에 대해 기존의 거리보다 정점 u를 거쳐가는게 더 빠르면 distance[z] = distance[u] + weigh..