두부의 코딩일기

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 전형적인 다익스트라 알고리즘 문제이다. dp와 bfs를 이용해서 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다. 다익스트라에 대해서 잘 모르면 아래 링크를 먼저 보는 걸 추천한다. 자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리 다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 이번 문제는 bfs와 dfs를 동시에 사용하는 문제로 3개의 벽을 세워서 바이러스로 부터 안전한 구역을 최대한 넓게 만들어야한다. 우선 임의로 중복되지 않은 3개의 벽을 계속 세워야하므로 dfs를 이용한다. 벽을 세우고, 다시 복구를 반복하면서 벽 3개가 완성되면 bfs를 돌리면 된다. public static void dfs(int wall) { if (wall == 3) { bfs(); // 벽이 3..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 이번 문제는 최소 비용 신장 트리 (MST) 유형의 문제이다. 해결 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다. 필자는 사실 크루스칼 알고리즘을 처음 들어본다. 그래서 한 번 정리해봤다. 자바 최소 비용 신장 트리(MST), 크루스칼 알고리즘(Kruskal Algorithm) 정의 크루스칼 알고리즘 (Kruskal Algorithm) 정의 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 중 하나이다...

크루스칼 알고리즘 (Kruskal Algorithm) 정의 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 중 하나이다. 최소 비용 신장 트리 (Minimum Spanning Tree) 는 무엇일까? 정점 N개를 가지는 그래프에서 (N-1)개의 간선을 연결해야한다. 연결한 간선의 가중치 합이 가장 최소가 되는 그래프 모든 정점이 연결되야하지만 싸이클이 되면 안된다. A : 간선이 5개로 N-1개를 가져야하는 신장 트리 법칙에 어긋나고, [1, 3, 4] 정점에서 순환 싸이클을 돌고 있으므로 연결 그래프이다. B : 간선이 4개로 N-1개를 가져야하는 신장 트리 법칙에 어긋나지않지만 가중치 값 (2 + 5+ 7 + 6) 으로 최소 비..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 이번 문제는 랜선 자르기, 숫자 카드 등과 같은 이분 탐색 알고리즘 문제이다. 이분 탐색에 대해서 잘 모르거나 이해가 가지 않는다면 위 문제를 먼저 풀어보는 걸 추천한다. 이 문제의 목표는 N개의 집이 주어졌을 때 C개의 공유기를 집 간격을 최대한 띄워서 설치하는 것이다. 그렇다면 이분 탐색을 어떻게 적용시켜야할까? 이분 탐색에서 중요한 건..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 이번 문제는 간단한 수학으로 풀 수 있는 문제라고 생각할 수 있지만 보석의 개수와 가방의 무게의 범위가 커서 시간 초과가 발생할 것이다. 시간 초과 에러를 발생시키지 않으려면 우선순위 큐를 이용해야 한다. 우선순위 큐는 여러 개의 값이 들어있을 경우 오름차순으로 자동 정렬된다고 생각하면 된다. 문제 해결 과정은 아래와 같다. 1. ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 조건이 많아서 생각할 게 많았던 bfs 문제로 알고리즘 진행 과정을 보면서 설명하겠다. 1. 입력받은 값 중에 '9'는 아기 상어의 위치이며 아기 상어는 총 1마리만 존재한다. 1) 아기 상어의 x, y 좌표를 저장함 (shark_x, shark_y) 2) 저장 후에 아기 상어의 위치는 0으로 변경한다. (해당 위치도 탐색 과정에 포함되어야함) 3) 물고기 위치를 담을 수 있는 배열 ..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 이번 문제는 정렬 후에 간단한 식만 만들어주면 해결할 수 있는 문제다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제로 i 번째 사람이 돈을 인출하는데 걸리는 시간은 i-1 번째 사람이 돈을 인출하는데 걸리는 시간 + 이전까지의 대기 시간이다. 이전까지의 대기 시간이 짧을수록 필요한 시간이 줄어들 것이다. 즉, i 번째 사람이 돈을 인출하는데 걸리는 시간이 짧은 순서로 정렬하면 된다. 오름차순 정렬이..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import java.io.*; import java.util.*; public class Main { static int[][] node; static boolean[][] visited; static int N; static String result_dfs = ""; static String result_bfs = ""; public static void ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 이 문제는 dp를 사용하지 않고 bfs와 dfs를 사용하게 되면 메모리 초과가 발생한다. 그렇다면 dp를 활용해서 메모이제이션을 해주어야한다. 예제 1번에서 2, 3번째 방법을 그림으로 보면 메모이제이션을 쉽게 이해할 수 있다. 그림을 보면 알 수 있듯이 20부터 도착지까지 갈 수 있는 방법이 동일하다. 그렇기 때문에 왼쪽 그림처럼 먼저 dfs 탐색을 진행했다면 오른쪽 그림의 경로에선 20..