🔗문제 보러가기 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🧑‍💻풀이 과정 기본적인 틀은 다익스트라 알고리즘인데, 최단 경로에 해당하는 각 도시들 번호를 어떻게 저장할 지가 문제였습니다. 분기가 이루어지는 각 경로마다 자기가 거쳐 온 도시 정보를 가지고 있을까 생각했다가, 메모리가 너무 많이 들 것은 물론 복사 비용이 만만치 않을 것 같아 포기했습니다. 그래서 결국 다른 분의 풀이를 참고했는데, 배열을 통해 이전 노드로 가는 길을 추적하는 참신한 방법을 사용하여 푸셔서 놀랐..

🔗문제 보러가기 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 🧑‍💻풀이 과정 위상 정렬을 사용해 풀 수 있는 문제인데, 사이클(Cycle) 감지 조건을 하나 더 넣어야 하는 문제입니다. 순서를 정하는 게 불가능한 경우는 각 가수들의 순서에 사이클이 있는 경우가 됩니다. 이는 모든 노드를 돌기 전에 큐(Queue)가 비었을 경우로 탐지 할 수 있습니다. ✏️소스 코드 및 결과 #include #include #include using namespace std; #define FAST_IO..

🔗문제 보러가기 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 🧑‍💻풀이 과정 동적 계획법(Dynamic Programming)과 위상 정렬(Topological Sort)를 사용해 풀 수 있습니다. 진입 차수가 0인 노드(v)에서 다른 인접 노드(other)로 향할 때, 다음 로직만 추가해주면 됩니다. *constructionTimes[i] : i 번째 건물의 건설 시간 *answers[i] : 먼저 지어야 하는 건물을 짓고 난 후, i 번째 건물까지 짓는 데 걸리는 최소 시간 answers[o..

🔗문제 보러가기 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 🧑‍💻풀이 과정 위상 정렬(Topological Sort)에 대해 공부한 후, 풀어보려고 골랐던 문제 중 하나입니다. 위상 정렬 알고리즘을 그대로 적용하되, 쉬운 문제부터 풀어야 하니 우선순위 큐(Priority Queue)를 대신 사용해주면 끝인 문제입니다. 이 외에는 더 이상 설명할 내용이 진짜로 없기에, 아래에 코드를 첨부하도록 하겠습니다. ✏️소스 코드 및 결과 #include #include #include..

🔗문제 보러가기 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 👨‍💻풀이 과정 처음에 문제를 보고 별 생각없이 배열 선언하고 분할 정복을 했다가 메모리 초과. (\( 2^{15} \times 2^{15} \)) 배열 없이 카운팅 변수 하나로만 아무 생각없이 셌다가 시간 초과. (하나씩 돌면서 점검하면 결국 \(\mathrm{O( 2^{15} \times 2^{15})}\)) 그래서 4등분을 하고, 찾고자 하는 (행, 열)이 해당 칸에 없는 경우에는 사각형 개수만큼 더해 주었습니다. 만약 찾고자 하는..

🔗문제 보러가기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 🧑‍💻풀이 과정 얼마 전에 다익스트라 알고리즘(Dijkstra Algorithm)을 공부했었으니, 머릿 속에서 인출하는 연습을 위해 비슷한 유형의 문제를 하나 풀어봤습니다. 우리 말이 어려운 건지, 제가 멍청한 건지 모르겠지만 매번 헷갈리는 것 같아요... 그래서 연습장에 그림 그려가며 풉니다. ( "distances[v] vs distances[u] + nextCost" 👉🏻 이게 젤 헷갈립니다. ) 알고리즘은..