반응형 전체 글282 백준 2623번 음악프로그램 - 스위프트(Swift) 풀이 1. 각 출연자를 정점으로 생각하고, 보조 PD들이 만든 순서가 A B C D라면 A→B, B→C, C→D로 가는 간선을 추가한다. 2. 완성된 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 결과에 포함된 정점 개수가 N개가 아니라면 순서를 정하는 것이 불가능한 경우이다. 1. 각 출연자를 정점으로 생각하고, 보조 PD들이 만든 순서가 A B C D라면 A→B, B→C, C→D로 가는 간선을 추가한다. 선행 관계가 주어진 작업들의 순서 정하기 문제이다. 위상 정렬 알고리즘을 사용하여 해결할 수 있다. 현재 상황을 그래프로 변환한다. 보조 PD들이 만든 X명의 순서를 차례로 쪼개면 X-1개의 선행 관계가 나오게 된다. 위와 같이 선행 관계로 쪼개 간선을 추가해준다. 2. 완성된 그래프에 대해 위상 정렬.. 2022. 1. 28. 백준 1202번 보석 도둑 - C++(cpp) 풀이 + 그림 설명 1. 용량이 적은 가방부터 채운다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 3. 남은 가방에 대해 1-2를 반복한다. 1. 용량이 작은 가방부터 채운다. 한 가방에는 한 개의 보석만 담을 수 있으므로 그리디 하게 풀 수 있는 상황이다. 용량이 적은 가방에 들어가지 못한 보석이 용량이 큰 가방에는 들어갈 수도 있다. 반대로 용량이 큰 가방에 들어가지 못한 보석이 용량이 적은 가방에는 들어갈 일은 없다. 따라서 용량이 작은 가방부터 최선으로 채워나가면 최선의 결과를 얻을 수 있음이 보장된다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 먼저 용량이 C인 가방에 담을 수 있는 보석들을 걸러내기 위해 보석을 무게 순으로 정렬한다. 아래와 같은 상황이고, 가방의.. 2022. 1. 28. 백준 2056번 작업 - C++(cpp) 풀이 1. 각 작업을 정점으로, 작업 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 작업에 걸리는 시간을 구한다. 4. max(totalCost[i])를 출력한다. 1516번 게임 개발 문제와 똑같으니 1,2,3번 풀이는 아래에서 확인! 백준 1516번 게임 개발 - C++(cpp) 풀이 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다. 1 please-amend.tistory.com 4. max(t.. 2022. 1. 28. 백준 1516번 게임 개발 - C++(cpp) 풀이 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다. 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 이렇게 선행 관계가 정해져있는 작업들을 순서대로 수행하는 상황은 그래프 위상 정렬 알고리즘으로 해결할 수 있다. 먼저 주어진 상황을 그래프로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 위상 정렬을 해준다. 아래 코드에서는 큐를 사용하였고, 선행 작업들이 모두 완료된 작업들만 큐에 들어가게 된다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물.. 2022. 1. 28. 백준 2252번 줄 세우기 - C++(cpp) 풀이 1. 각 학생을 그래프의 정점으로 생각한다. 2. A가 B의 앞에 서야 한다면, A에서 B로 가는 방향 간선을 추가한다. 3. 위상 정렬한 결과를 출력한다. 1. 각 학생을 그래프의 정점으로 생각한다. 각 학생을 그래프의 노드로 생각할 것이다. X번 학생은 X번 노드로. 2. A가 B의 앞에 서야 한다면, A에서 B로 가는 방향 간선을 추가한다. A가 B의 앞에 서야 한다면, A가 있은 뒤에 B가 와야 한다. 이것을 그래프에 표현하기 위해 A → B인 방향 간선을 추가한다. 3. 위상 정렬한 결과를 출력한다. 이제 완성된 그래프를 위상 정렬한 결과를 출력하면 된다. 주어진 상황이 위상 정렬 상황이기 때문. #include #include #include #include using namespace std.. 2022. 1. 28. 이전 1 ··· 40 41 42 43 44 45 46 ··· 57 다음 반응형
