개발일지

문제설명 입출력 예제 개념 최소 신장 트리 문제다. 주어진 그래프에서 가중치의 합이 최소가 되는 트리를 찾는 것이므로, MST 알고리즘 중 크루스칼 알고리즘을 이용해서 풀면 해결할 수 있다. 이때 Kruskal 알고리즘은 모든 간선들의 가중치를 오름차순으로 정렬하고, 가장 가중치가 작은 간선부터 연결해 나가면서 MST를 만들어 나가는 알고리즘이다. 풀이 #include #include #include using namespace std; int findParent(int parent[], int node) { while (parent[node] != node) node = parent[node]; return node; } void unionParent(int parent[], int a, int b) ..

문제설명 입출력 예제 개념 이 문제는 모든 국가가 연결되어 있고, 모든 비행기 티켓 가격이 동일하다는 특성 때문에 최소 신장 트리 문제처럼 보일 수 있다. 하지만 여기서 중요한 점은 상근이가 한 국가에서 다른 국가로 이동할 때, 필요에 따라 다른 국가를 거쳐갈 수 있다는 것이다. 이는 실질적으로 모든 비행기를 직접 타고 갈 필요가 없다는 것을 의미한다. 따라서 이 문제의 답은 MST 알고리즘을 사용하지 않고도 간단히 구현할 수 있다. 상근이가 모든 국가를 여행하기 위해서는 전체 국가의 수 - 1 만큼의 비행기를 타면 된다. 왜냐하면 한 국가에서 출발해 모든 다른 국가를 방문하려면, 국가의 수보다 비행기를 하나 적게 타면 되기 때문이다. 풀이 #include using namespace std; int m..

프림의 최소 신장 트리 알고리즘프림 알고리즘　프림 알고리즘(Prim's Algorithm)은 최소 신장 트리 문제를 해결하는 그리디 알고리즘 중 하나다. 그래프의 임의의 정점에서 시작하여, 그래프의 모든 정점을 포함하고 모든 간선의 가중치 합이 최소인 트리를 찾는 알고리즘으로서, BFS의 동작 방식과 유사하다. 동작 과정은 다음과 같다. 시작 노드를 선택하고, 선택한 정점을 트리에 추가선택한 노드에 인접하고 트리에 연결되지 않은 노드로 연결된 간선들 중, 가장 작은 가중치를 가진 간선을 추가그래프의 모든 노드가 트리에 추가될 때까지 반복예시 　다음과 같은 그래프가 있다고 가정하고, 이러한 그래프에 프림 알고리즘을 적용하여 최소 신장 트리를 구하는 과정을 살펴보자.   　먼저 시작 정점을 제외하고, 모든 ..

그래프 탐색개요　그래프 탐색(graph traversal problem), 또는 그래프 순회 문제(graph search problem)는 그래프의 일련의 정점을 체계적으로 방문하는 문제를 의미한다. 주어진 그래프 G = 에서 특정 정점 s를 시작점으로 하여, 모든 정점 v ∈ V를 한 번씩 방문하는 것이 이 문제의 목표다. 이 과정에서 방문된 정점의 순서는 탐색 알고리즘에 따라 달라진다. 탐색은 주로 그래프의 구조를 이해하거나, 특정 경로를 찾는 등의 목적으로 사용된다. 이를 통해 네트워크 연결 상태, 최단 경로, 사이클 등 그래프의 다양한 특성을 분석할 수 있다. 　그래프 탐색은 다양한 응용 분야에서 중요한 역할을 수행한다. 예를 들어, 네트워크 라우팅, SNS에서 친구 추천, 웹 크롤러 등에서 그래..

문제설명 입출력 예제 개념 이 문제는 각 숫자를 입력받을 때마다 중간값을 계산하고 출력하는 것이다. 단순하게 배열에 값을 추가하고, 매 반복마다 중앙값을 출력하려면 시간 복잡도가 O(N^2)이 되어 시간 초과가 발생할 수 있다. 이를 해결하기 위한 최적화된 알고리즘이 두 힙 알고리즘이다. 두 힙 알고리즘은 최대 힙과 최소 힙을 이용한다. 이 방식에서는 현재까지 입력받은 수 중 중간값 이하의 수를 최대 힙에, 중간값 초과의 수를 최소 힙에 저장한다. 따라서 중간값은 항상 최대 힙의 루트에 위치하게 된다. 이 알고리즘의 각 연산은 로그 시간 복잡도를 가지므로, 전체 시간 복잡도는 입력의 개수에 비례하는 선형 로그 시간 복잡도 O(N logN)를 가지게 된다. 이렇게 해서 큰 입력에 대해서도 효율적으로 문제를..

문제 설명 제한 사항 및 입출력 예제 개념 최소 공배수의 개념을 유클리드 호제법을 이용하여 구하는 문제다. 백준 최소 공배수 문제의 연장선으로서, 주어진 벡터의 모든 원소를 순회하며 최소 공배수를 구하면 된다. 풀이 (1) 유클리드 호제법 구현 #include using namespace std; int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y); } int lcm(int x, int y) { return x * y / gcd(x, y); } int solution(vector v) { int answer = 1; for (int i = 0; i < v.size(); ++i) answer = lcm(answer, v[i]); retur..

문제 설명 제한 사항 및 입출력 예제 개념 다음 그림처럼 토너먼트 브라켓 구조를 띄고 있는 대회에서 A참가자와 B참가자가 무조건 이긴다는 가정 하에 몇 번째 라운드에서 만날지 예측하는 문제다. 배열을 갱신하며 두 특정 참가자가 만나는 시점까지 반복하는 방법과, 두 참가자의 위치를 업데이트하고, 이들이 같아질 때까지 라운드를 증가시키는 방법이 존재한다. 풀이 (1) 배열 갱신 #include using namespace std; int solution(int n, int a, int b) { int cnt = 1; vector v(n, 0), tmp; v[a - 1] = true; v[b - 1] = true; for (int i = 0; i < n; i += 2) { if (v[i] && v[i + 1]..

문제설명 입출력 예제 개념 최소 비용을 통해 목표를 달성하는 그리드 알고리즘을 활용하는 문제다. 이 문제의 핵심 아이디어는 가장 낮은 기름값을 갖는 주유소를 찾아, 그곳에서 기름을 충전하는 것이다. 따라서 현재 위치에서 다음 도시로 이동하기 위해 필요한 기름을 충전하는데, 현재 주유소의 기름 가격과 다음 주유소의 기름 가격을 비교하여 최소 비용을 항상 유지하게 기름값을 갱신하면 된다. 풀이 #include #include using namespace std; int main() { long long N; cin >> N; vector station(N), road(N-1); for (int i = 0; i > road[i]; for (int i = 0; i < N; ++..

문제설명 입출력 예제 개념 각 사람이 돈을 인출하는 데 필요한 시간 합의 최솟값을 출력하는 문제다. 대표적인 그리디 알고리즘으로 효율적으로 해결할 수 있는 문제로서, 실행 시간이 가장 짧은 프로세스부터 우선적으로 처리하는 최단 작업 우선 스케줄링 방식을 이용하면 된다. 여기서 돈을 인출하는데 걸리는 시간을 작업으로 보고, 이 작업들을 가장 짧은 것부터 처리하면 모든 사람이 돈을 인출하는데 필요한 최소 시간을 구할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N; cin >> N; vector v(N); int* sum = new int[N]; for (int i = 0; i > v[i]; s..

문제설명 입출력 예제 개념 이 문제는 회의 시간이 겹치지 않도록 하면서 동시에 가능한 한 많은 수의 회의를 배정하는 문제다. 이를 해결하는 방법 중 하나는 먼저 회의들을 종료 시간 기준으로 오름차순 정렬하는 것이다. 그리고, 가장 먼저 끝나는 회의를 선택한 후, 이전에 선택한 회의와 시간이 겹치지 않는 회의 중 가장 빨리 끝나는 회의를 다음으로 선택하는 것이다. 이러한 방식을 반복함으로써 가능한 많은 수의 회의를 배정할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N, n, k, count = 1; cin >> N; vector v(N); 회의의 수 N, 그리고 회의의 시작과 끝에 대한 입력을 초기화할 변수 n, k,..