알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/31854 어떤 알고리즘을 사용해야 되는지 파악하는 하는게 중요한 문제입니다. 각 좌표들의 부등호가 주어질 때, 이를 통해서 올바른 퍼즐을 구하는 문제입니다. (X, Y)  좌표와 (X, Y + 1), (X + 1, Y)의 관계가 주어지는데, 이때 어느 쪽이 큰지, 작은지를 알 수 있기에 이는 방향성이 있는 그래프로 생각할 수 있습니다. 또한, 가장 작은 곳부터 순서대로 채워나가면 되기에, 자기보다 큰 좌표가 있다면 해당 좌표의 값을 하나씩 증가시키면서 나중에 채워나가면 된다는 생각을 할 수 있습니다. 위의 2개를 합치면 위상 정렬이 되기에 위상 정렬의 조건에 맞춰서 구현해주시면 됩니다.  자세한 것은 코드를 참고해주세요.#def..

문제 링크입니다. https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬과 우선순위 큐를 이용한 문제입니다. 문제의 조건이 있습니다. 1. N개의 문제는 모두 풀어야 한다. 2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 3. 가능하면 쉬운 문제부터 풀어야 한다. 3-1. 문제 난이도는 문제 번호 순이다. 여기서 조건 2에 해당하지 않는 문제들이 있습니다. ..

문제 링크입니다! https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 그래프를 사용한 DP 문제였습니다. 먼저 지을 수 있는 건물을 지은 다음, 해당 건물을 짓고 난 다음에 지을 수 있는 건물을 지어보는 식으로 최댓값을 찾아가는 문제였습니다. ex) 1 -> X , 2 -> X , 3 -> 2 , 4 -> 1,2 , 5 -> 1,3 (A -> B는 B를 짓고 나서 A를 지을 수 있다는 의미입니다.) 해당 경우, 1번과 2번을 먼저 짓습니..