💻 computer science/🤔 알고리즘
-
📒 위상정렬💻 computer science/🤔 알고리즘 2024. 6. 17. 15:46
💡 위상 정렬(Topological Sort)이란?유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것 그래프와 관련된 알고리즘 중 하나방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬 ❗선후 관계가 정의된 그래프 구조에서 정렬을 하는데 사용할 수 있다. ⚠️ 그래프내에 사이클이 존재하는 경우에는 올바른 위상 정렬이 존재할 수 없다.선후 관계에 모순이 생기기 때문 따라서, 위상 정렬은 사이클이 존재하지 않는 방향 그래프에서만 잘 정의가 된다. 사이클이 존재하지 않는 방향 그래프 = DAG(Directed Acyclic Graph) 🧑🏻💻 구현 🏃 구현 순서 1️⃣ 먼저, 위상 정렬상에서 제일 앞에 오는 정점(A, C, G)로 가능..
-
🎒 Knapsack 알고리즘 (배낭 알고리즘)💻 computer science/🤔 알고리즘 2024. 5. 9. 15:21
🎒 배낭 알고리즘DP 알고리즘 중 하나주어진 공간(배낭)에 최대 가치를 가지는 물건들을 넣도록 물건들을 선택하는 것이다. 배낭 알고리즘에는 2가지 유형이 존재한다. 1️⃣ Fraction Knapsack물건을 쪼갤 수 있는 경우이 경우는 그리디 알고리즘이 사용될 수 있다.단위 무게당 가치가 높은 물건을 차례대로 배낭에 넣는 방식 2️⃣ 0-1 Knapsack물건을 배낭에 넣을지 (1) 또는 넣지 않을지(0)을 결정하는 경우 🤔 왜 배낭 알고리즘이 Dynamic Programming 일까? 결국 최대 이익을 구하기 위해서는 물건을 배낭에 넣어야 한다.이때, 배낭에 물건을 넣는냐 마느냐 가 중요한 선택이다.2가지 선택지가 존재 만약, 배낭에 넣을 수 있는 양이 N 이고, 넣고자 하는 물건의 무게가 M 이..