컴공에서 살아남기

🎄신장 트리 (스패닝 트리) 최소 신장 트리에서 '신장 트리' 즉, 스패닝 트리는 노드 간의 경로가 오직 하나뿐인 트리를 말한다. 그래프 내의 모든 정점을 포함하며, 그래프의 최소 연결 부분 그래프라고 볼 수 있다. 최소 연결이란 간선의 수가 가장 적다는 뜻으로, n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)개이다. 따라서, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되며, 이것이 바로 스패닝 트리가 된다. 🎄최소 신장 트리 (MST, Minimum Spanning Tree) 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 최소 신장 트리는 이러한 신장 트리중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다. 즉, 가중치를 간선에 할당한 그래프에 있는 모든 정점들..

📖 플로이드 워셜 알고리즘 다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 그러나, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에는 "플로이드 워셜 알고리즘"을 사용해야 한다. 📌 플로이드-워셜 알고리즘 vs 다익스트라 알고리즘의 차이점 1. 플로이드 워셜 알고리즘은 다익스트라에 비해 소스코드가 매우 짧아 구현이 쉽다. 2. 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문에 2차원 테이블에 최단 거리 정보를 저장한다. (다익스트라 알고리즘은 한 지점에서 다른 지점까지의 최단 거리만을 구하므로 1차원 리스트에 저장하였다) 3. 플로이드 워셜 알고리즘은 DP 알고리즘에 속한다. 만약 노드의 개수가..

🎒배낭문제 (Knapsack Problem) 배낭문제는 조합 최적화 문제의 일종이다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분 집합을 찾는 문제이다. 분할 가능한 배낭 문제 0-1 배낭 문제 배낭 문제는 분할 가능한 배낭 문제와, 0-1 배낭 문제로 나뉘어 진다. 위 그림을 통해 보면, A박스를 열어 12kg의 금괴 중 일부만을 챙겨 갈 수 있는 문제가 '분할 가능한 배낭 문제'이고, 박스를 열지 못해 금괴 일부를 꺼내지 못하고 통째로만 취급하는 문제가 '0-1 배낭 문제'이다. 분할 가능한 배낭 문제는 그리디 알고리즘으로 풀 수 있다. 반면, 0-1..

브루트 포스 알고리즘은 단어 그대로 Brute (무식한), Force (힘) 를 해석하여 무식하게 모든 경우의 수를 비교하여 해답을 찾는 알고리즘이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 모든 경우를 계산하기 때문에 단순히 모든 경우의 수를 비교하는 알고리즘을 설계하고 구현하기에 비교적 쉽고, 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 또한 강력한 장점은 어떤 경우에도 예외 없이 100%의 확률로 정답만을 출력할 수 있는 점이다. 그러나, 모든 경우의 수를 연산하는 만큼 알고리즘 실행 시간이 매우 오래 걸리고, 메모리 효율면에서도 매우 비효율적이며 계산 비용이 높다. 따라서 문제를 파악할 때 브루트포스 알고리즘으로 풀이할 수 있는지를 판단해야 하는데, 이는 입력값(N)과 ..

피보나치 수 알고리즘에 대해선 일반 재귀함수/반복문 으로 푸는 방법만 알고 있었다. 이번에는 동적 프로그래밍(Dynamic Programming, DP)을 공부하면서 배열에 피보나치 수열의 값을 저장해두고 재사용하여 풀이하는 방법에 대해 공부해보았다. 💡 DP (Dynamic Programming) 동적 계획법 다이나믹 프로그래밍은 하나의 Problem이 두 개의 Sub Problem으로 나뉘고, 이러한 Sub Problem이 또 다른 Sub Problem으로 나뉜다고 할 때, 중복되는 Sub Problem이 존재하는 경우 효율적으로 문제를 해결할 수 있는 방법 중 하나이다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산하는 방식. 쉽..

그래프 알고리즘 중 최소비용을 구하는 데는 다익스트라 알고리즘, 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다. 그중 다익스트라 알고리즘은 시작 정점부터 다른 정점까지의 최단 경로를 구하기 위한 그래프 알고리즘이다. 이러한 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지의 최단 경로를 방문하여 각 정점까지의 최단 경로를 모두 찾는다. 즉, 매번 최단 경로의 정점을 선택하여 탐색을 반복하는 것이다. 다익스트라 알고리즘은 노드의 재방문을 허용하지 않기 때문에 어느 간선의 가중치라도 음수가 있으면 안된다는 특징이 있다. (음수 간선이 존재할 때는 벨만-포드 알고리즘, SPFA 알고리즘을 이용하여 최소비용을 구할 수 있다.) 다익스트라에서 노드 간의 연결은 weight (가중치)값으로 판단한다. 특..

"에라토스테네스의 체" 는 수학에서 소수를 찾는 방법이다. 문장으로 설명하는 방법은 아래와 같다. 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 3. 자기 자신을 제외한 2의 배수를 모두 지운다. 4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 5. 자기 자신을 제외한 3의 배수를 모두 지운다. 6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 7. 자기 자신을 제외한 5의 배수를 모두 지운다. 8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 9. 자기 자신을 제외한 7의 배수를 모두 지운다. 10. 위의 과..

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 단순 리스트를 이용하여 구현할 수 있고, 또는 힙(heap)을 이용하여 구현할 수 있다. 힙(Heap)은 완전 이진 트리 자료구조의 일종으로, 항상 루트노드를 제거한다. 완전 이진 트리: 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 트리 힙은 최소힙과 최대힙으로 나뉜다. 최소힙 : 루트 노드가 가장 작은 값을 가지므로, 값이 작은 데이터가 우선적으로 제거된다. 최대힙 : 루트 노드가 가장 큰 값을 가지므로, 값이 큰 데이터가 우선적으로 제거된다. 아래는 Cpp 클래스로 직접 우선순위 큐를 사용해 본 예제이다. #include #include #include #include using n..

void FindDivisor(vector& out, int num) { for (int i = 1; i