[알고리즘] 위상정렬

위상 정렬방향 그래프의 정점들을 "선후 관계(의존 관계)"에 따라 나열하는 정렬 방법이다.단, 위상 정렬은 비순환 방향 그래프(DAG : Directed Acyclic Graph)에서만 가능하다 만약 순환이 있다면, 어떤 노드도 “처리 순서를 앞에 둘 수 없기 때문에” 선형 정렬 자체가 불가하다.(진입 차수가 0이 될수 없는 구간이 존재하고, 그러면 각 정점은 우선순위가 없으며 위상 정렬을 통해 탐색 순서를 정의할 수 없다) 위상 정렬 예시 : 라면 끓이기DFS 기반 위상 정렬깊이 먼저 따라가서, 끝에서 역순으로 쌓는다사리 부수기 → 사리 넣기 → 물넣기스프넣기 → 물넣기끓이기 → 물넣기밥 준비하기 (독립)✔️ 결과 예시 (역후위 순회) :밥 준비하기 → 사리 넣기 → 사리 부수기 → 스프 넣기 → 끓이..

• format_list_bulleted 크래프톤정글 (2025.03-07)
• · 2025. 4. 3.

[알고리즘] 그래프

파이썬의 그래프그래프 관계(relationship)을 표현하는 자료 구조로, 파이썬에서는 어떤 관계를 표현할때 적합한 것은 사전(dictionary)이다. 그래프는 인접 행렬, 인접 리스트로도 나타낼 수 있다.  키(key) : 노드값(value) : 키와 연결된 노드 리스트#무방향 그래프graph1 = {1:[2, 3, 5], 2:[1, 3], 3:[1, 2, 4], 4:[3, 5], 5:[1, 4]}#방향 그래프graph2 = {1:[2, 3], 2:[3], 3:[4], 4:[], 5:[1, 4]}리스트를 이용하여 그래프를 나타내 보자. 리스트의 인덱스가 사전의 key에 해당하고, 인덱스의 값은 사전의 값과 똑같다.#무방향 그래프graph1 = [[], [2, 3, 5], [1, 3], [1, 2, ..

• format_list_bulleted 카테고리 없음
• · 2025. 4. 3.

[알고리즘] 트리 구조

트리 구조루트 : 트리의 가장 위쪽에 있는 노드. 루트는 트리에 1개만 존재리프 : 가장 아래쪽에 있는 노드. aka 단말 노드 (terminal node), 외부 노드 (external node). 가지를 더 이상 뻗을 수 없다비단말 노드 (non-terminal node) : 리프를 제외한 노드. aka 내부 노드자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식이라 한다.부모 : 어떤 노드와 가지가 연결되었을 때 위쪽 노드를 부모라 한다형제 : 부모가 같은 노드를 형제라 한다조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드를 조상이라 한다자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드를 자손이라 한다레벨 : 루트에서 얼마나 멀리 떨어져 있는지. 루트의 ..

• format_list_bulleted 크래프톤정글 (2025.03-07)
• · 2025. 4. 3.