⭐️ 난이도 Gold 3 ⭐️ 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ⭐️ Idea flow 위상 정렬에 대해 이해하고 있고, 언제 이용해야 하는지 알고 있으면 해결할 수 있는 문제였다. 왜 위상 정렬을 이용하여 해결해야 하는가? 이 문제는 일부 학생들의 키 순서가 주어졌을 때, 전체 학생을 키 순서대로 줄을 세운 결과를 반환해야 한다. 방법이 여러 가지인 경우 아무거나 출력하면 되므로,..
Baekjoon
⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net ⭐️ Idea flow 문제를 읽어보면 각각의 작업들에 대해 해당 작업에 걸리는 시간과 선행 관계에 있는 작업들의 번호들이 주어진다. 이는 곧 일에 따른 순서가 정해져 있다는 뜻이고, 이러한 경우에는 위상 정렬(Topology sort)이 적절하다. 하지만 이 문제는 기본적인 위상 정렬 문제 처럼 방문 순서를 구하는 것이 아니라, 제일 마지막 작업을 완..
⭐️ 난이도 Gold 2 ⭐️ 문제 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net ⭐️ Idea flow MST를 통해 풀 수 있는 문제였다. 그런데 왜 MST로 푸는 문제일까? 발전소(시작 지점)이 한 군데가 아니기 때문에 다른 알고리즘을 사용해야하나 고민했다. 하지만 목적지가 따로 없고, 모든 노드(도시)를 연결해야 하는 문제이므로 MST 문제라고 판단했다. 왜 prim 알고리즘을 사용해야 할까?..
⭐️ 난이도 Gold 3 ⭐️ 문제 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net ⭐️ Idea flow 문제를 읽으면서 이 문제에 MST의 일종인 Prim 알고리즘을 사용해야겠다고 생각했다. 그럼 먼저 이 문제가 왜 MST 관련 문제일까? → 모든 도시를 최소 비용으로 연결해야하기 때문이다. shortest path problem와는 달리, 특정 목적지가 정해져있지 않다. 그럼 두 번째로 왜 Prim 알고리즘을 사용해야 할까? → Kruskal..
⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net ⭐️ Idea flow 이 문제는 이름에서부터 알 수 있듯이 MST(Minimum Spanning Tree) 알고리즘을 이용해서 풀어야하는 문제였다. 처음에는 이 문제를 prim 알고리즘으로 풀어보려고 했는데, "MST를 이루는 간선 중 가중치가 제일 적은 간선"을 제거하기 위한 필요한 정보가 많다..
⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net ⭐️ Idea flow 봄, 여름, 가을, 겨울마다 어떤 일이 일어나는지 문제에서 주어지기 때문에 이를 잘 구현하면 되는 구현&시뮬레이션 문제였다. 주의할 점은 시간 제한이 0.3초인 것이었는데, 구현을 하는 과정에서 반복문과 정렬(소팅)이 필요해서 이를 적절히 배치해야했다. [처음 생각했던 풀이 - 시간 초과] 우선 나무의 나이, y 좌표, x..
