본문 바로가기

알고리즘 별 문제 정리/위상정렬

 (10)
[C++] 백준 2637: 장난감 조립 문제 이해- 완제품: 기본 부품 + 중간 부품 - 시간 제한: 1초- 메모리 제한: 128MB - N: 완제품의 번호 (3 ~ 100, 10^2)- M: 관계의 개수 (3 ~ 100, 10^2)- 관계(완제품, 중간 부품 or 기본 부품, 필요한 개수) - 하나의 완제품을 만들기 위하여 필요한 기본 부품의 종류별 개수  문제 풀이기본 부품과 중간 부품을 조합하여 완제품을 만든다는 점에서 선행 관계가 있다고 볼 수 있다.즉 위상 정렬을 사용하여 푸는 문제이다.  개수를 구해야 하므로 DP를 사용해야 할 거 같은데 시간을 구하는 여러 문제들과 달리 개수를 구하는 문제였다. 문제의 입력이 주어지는 것에서 힌트를 얻을 수 있는데,완제품에서 시작하여 위상정렬을 시작하면 문제를 쉽게 풀 수 있다.   1. dp[n..
[C++] 백준 1948: 임계경로 문제 이해- 모든 도로가 일방 통행인 도로이고, 싸이클이 없다 => 사이클이 아닌 방향 그래프(Directed Acyclic Graph)- 시작 도시부터 도착 도시까지 가능한 모든 경로를 탐색할 예정- 출발 도시: 들어오는 도로가 0개- 도착 도시: 나가는 도로가 0개 - 시간 제한: 2초- 메모리 제한: 512MB - n: 도시의 개수 (1 ~ 10,000, 10^4)- m: 도로의 개수( 1 ~ 100,000, 10^5)- 도로의 정보(출발 도시, 도착 도시, 걸리는 시간(1 ~ 10,000, 10^4))- 출발 도시, 도착 도시 - 임계 경로의 비용(마지막에 도착하는 사람이 도착하는 시간)- 이 시간까지 쉬지 않고 움직이는 사람들이 지나가는 도로의 개수더보기더보기임계경로위상 정렬을 진행하면 각 작업..
[C++] 백준 14567: 선수과목(Prerequisite) 문제 이해- 모든 전공 과목을 들어야 졸업할 수 있다.- 특정 과목은 선수과목을 모두 들어야만 들을 수 있다.- 한 학기에 들을 수 있는 과목 수에 제한은 없다.- 모든 과목은 매 학기 개설된다. - N: 과목의 수 (1 ~ 1,000, 10^3)- M: 선수 조건의 수(0 ~ 500,000, 10^5)- 시간 제한: 5초- 메모리 제한: 256MB - 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 출력하라.  문제 풀이각 과목에 대해 선수 과목이 있다는 지문은 선행 관계가 주어진 그래프라고 볼 수 있다.=> 위상 정렬을 사용해서 풀자!   이 문제의 특별한 점은 각 과목마다 이수하는 데 걸리는 학기의 수를 구해야 한다는 점이다.걸리는 학기의 수를 배열을 하나 설정해 DP를 써주면 쉽게..
[C++] 백준 3665: 최종 순위 문제 이해- 대회에 여러 팀이 참여했다.- 작년과 올해는 동일한 팀이 참여했으며, 작년의 전체 순위는 공개된다.- 올해는 전체 순위는 발표되지 않으며, 작년에 비해 상대 순위가 바뀐 팀만 발표된다. - n: 대회에 참가한 팀의 개수 (2 ~ 500, 10^2)- m: 상대적인 등수가 바뀐 쌍의 수(0 ~ 25,000, 10^4) 출력- 확실한 순위를 만들 수 없을경우: ? 출력- 일관성이 없는 잘못된 정보 : IMPOSSIBLE 출력- 확실한 전체 순위가 만들어질 경우: 1등 팀부터 차례대로 출력   문제 풀이작년에 비해 상대 순위가 바뀐 팀에 대해 알려주므로 순서쌍이 주어지는 것으로 볼 수 있다.즉, 위상 정렬을 사용하면 풀 수 있는 문제로 판단했다.  1. 선행 관계의 표현 하지만, 문제점이 있다.작..
[C++] 백준 2056: 작업 문제 이해- N: 수행해야 할 작업의 개수 (3 ~ 10,000, 10^4)- 각각의 작업마다 걸리는 시간 (1 ~100, 10 ^ 2) - 작업 간에는 선행 관계가 존재- 선행 관계가 없을경우, 동시에 수행이 가능하다. - 각 줄 처음: 각 작업을 하는데 걸리는 시간- 각 줄 두 번째: 선행 관계의 개수- 나머지: 선행 관계 작업들의 번호 모든 작업을 완료하기 위한 최소 시간을 출력한다.  문제 풀이선행 관계, 즉 순서가 주어진 그래프에서 전체 순서를 구하는 문제이다. 역시 위상 정렬을 사용하면 쉽게 풀 수 있을거 같다!  특징적인 점은 선행 관계가 없을경우 동시에 수행이 가능하다는 것이다.모든 작업을 완료하기 위한 최소 시간을 구하는데 동시에 수행이 가능하다?=> DP를 사용하면 해결할 수 있다. d..
[C++] 백준 2623: 음악프로그램 문제 이해- 음악 프로그램 PD인 남일이가 보조 PD에게 순서를 정해오게 한다.- 각 순서들을 모아서 전체 가수의 순서를 정해야 한다.- 만약 불가능 하다면 0을 출력한다.- 답이 여러 개인 경우 아무거나 하나를 출력한다. - N: 가수의 수 (1 ~ 1,000, 10^3)- M: 보조 PD의 수 (1 ~ 100, 10^2)  문제 풀이순서가 정해진 몇 쌍으로부터 전체 순서를 구하는 문제 --> 위상 정렬! 이 문제의 특징적인 점은 주어지는 순서들이 전체 순서를 정하는 것이 불가능한 경우도 있다는 것이다.즉, 순환 그래프가 만들어질 수 있다는 점이다.  그렇다면 순환 그래프는 어떻게 확인할 수 있을까?답은 바로, 위상정렬이 끝났을 때 정점으로 들어오는 간선이 남아있는 경우이다. while문이 끝난 뒤 정..
[C++] 백준 1766: 문제집 문제 이해- N: 문제의 개수 (1 ~ 32,000, 10^4)- M: 정보의 개수 (1 ~ 100,000, 10^5) - 문제는 난이도 순서로 출제- N개의 문제는 모두 풀어야 한다- 먼저 풀으면 좋은 문제는 먼저 풀어야 한다- 가능하면 쉬운 문제부터 풀어야 한다  문제 풀이먼저 풀면 좋은 문제가 주어진다는 것은특정 순서가 주어진 그래프의 전체 순서를 결정한다는 것과 같다. 즉, 위상 정렬을 사용해주면 쉽게 풀 수 있다.  다만, 이 문제에서 주의할 점은'가능하면 쉬운 문제부터 풀어야 한다'는 점이다. 보통의 위상 정렬은 여러 개의 경우의 수가 가능하지만위의 문구로 인해 이 문제는 한 가지 경우의 수만 나올 것이다. 가능하면 쉬운 문제를 풀기 위해각 정점으로 들어가는 간선의 개수를 체크할 때 1개의 정..
[C++] 백준 2252: 줄 세우기 문제 이해- N명의 학생들을 키 순서대로 줄을 세우려고 한다.- 단 키를 각각 재는 것이 아닌 비교하여 순서를 정한다.- M: 키를 비교한 횟수 (1 ~ 100,000, 10^5)- N: 학생 수 (1 ~ 32,000, 10^4)- 답이 여러가지일 경우 아무거나 출력한다.  문제 풀이학생들의 키의 순서를 비교한 값이 나와있는 이 문제는특정 조합의 순서가 정해져 있는 그래프의 전체 순서를 결정하는 문제이다. 즉, 위상 정렬을 사용하면 쉽게 풀 수 있는 문제이다.   전체 코드#include #include #include #include using namespace std;int n, m;vector v[32005];int inDegree[32005];queue q;int main() { ios_ba..

티스토리툴바