실전 압축 코딩

5214번: 환승 (acmicpc.net) 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 누구나 쉽게 BFS를 떠올릴수 있지만 메모리와 시간 초과를 피하기 위해 새로운 발상이 필요했던 문제. 풀이 알고리즘 파악 BFS 일반적인 BFS 방식으로는 메모리 초과나 시간 초과가 날 수 밖에 없다. 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M의 범위는 1≤K,M≤1,000이다. 하이퍼튜브 하나당 정점끼리 K*K 개의 간선이 연결되므로 그래프의 총 간선의 개수는 최악의 경..

5719번: 거의 최단 경로 (acmicpc.net) 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 알고리즘 파악 다익스트라 + DFS 출발점 S에서 D까지 가는 최단경로를 구하는 문제이다. 단, 단순한 최단경로가 아닌, (복수의) 최단경로를 제외한 나머지 경로에서의 최단거리를 구하는 것이다. 구현 총 두번의 다익스트라와 dfs를 통한 경로 탐색을 진행한다. 1. 다익스트라를 돌려 최단길이를 모두 구한다. 이 과정에서 이차원 boolean 배열인 route에 경로를 저장한..

1561번: 놀이 공원 (acmicpc.net) 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 매개변수 탐색의 개념을 잘 이해할 수 있는 좋은 문제 풀이 알고리즘 파악 이분탐색 (매개변수 탐색) 일반적인 매개변수 탐색 문제에서 조금 변형된 문제이다. 문제의 핵심은 -> 몇 분에 아이들이 전부 탑승할 것인가? + 몇 번째 놀이기구에 마지막 아이가 탑승할 것인가?이다. 하나씩 살펴보면 1. 몇 분에 아이들이 전부 탑승할 것인가? -> 매개변수 탐색을 통해 시간을 구한다. b..

17143번: 낚시왕 (acmicpc.net) 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 알고리즘 파악 시물레이션 뭐 복잡한 건 없다. 그냥 구현 문제이다. 구현 1. m마리의 상어를 담는 배열과, 상어의 위치를 기록할 2차원 map 배열을 만든다. 2. 낚시왕은 오른쪽 열로 한 칸씩 전진한다. 그 후 해당 열에서 가장 가까운 상어 한 마리를 잡는다. 잡은 상어는 무게를 더한다. 2. 잡은 상어는 status 상태를 false 로 만들어 죽은것으로 취급한다.(상어가 서로를 잡아먹을..

2842번: 집배원 한상덕 (acmicpc.net) 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 풀이 알고리즘 파악 DFS + 투 포인터 피로도를 구하는 방식은 최고 높이 - 최저 높이 이다. 즉, P를 포함한 모든 K를 방문하는 경우의 수 중, 최고 높이와 최저 높이의 차가 가장 작은 경우를 구하는것 이다. 투포인터로 최저 높이와 최고 높이를 구한뒤, 해당 최저 높이와 최고 높이로 모든 K와 P를 방문할수 있는지를 DFS를 통해 확인한다. 구현 1. 마을의 모든 고도를 TreeSet에 ..

16930번: 달리기 (acmicpc.net) 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 풀이 알고리즘 파악 BFS 한 번 이동할 때마다 K 만큼의 이동을 할 수 있다. 즉 진영이의 위치를 queue에 저장하고 동서남북 방향으로 최대 +k만큼의 범위를 저장하면 되는 것이다. 하지만 K가 최대 1000이기 때문에 모든 위치에서 매번 K*4 만큼 탐색을 하는 것은 매우 비효율적이다. 이 탐색 횟수를 줄이는 것이 이 문제의 핵심이다. 구현 1 탐색 위치가 인덱스 범위를 벗어나거나 벽과 만나면 탐색을 ..

3197번: 백조의 호수 (acmicpc.net) 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 처참했던 흔적.... 많이 해맸던 문제인데 풀이가 의외로 단순했다 풀이 알고리즘 파악 BFS 구현 1.백조를 움직이고 얼음을 만나면 멈추기 각 위치를 queue에 저장 2.얼음의 위치를 queue 에 담아두고 녹이기 + 다음에 녹일 얼음을 queue 저장 3.백조가 서로 만나면 종료 1) 얼음을 녹이는것 부터 살펴보자. 얼음을 녹일때 항상 1행 1열 부터 시작하면 엄청난 시간 낭비이다..

1043번: 거짓말 (acmicpc.net) 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net long 자료형 비트 연산 때문에 고생한 문제.... 기본적인 CS 지식이 부족하다고 느꼈다. 풀이 알고리즘 파악 비트 마스킹, 유니온 파인드 문제를 정리하면, 결국 지민이는 둘 중 하나를 선택해야 한다. 과장하기 vs 진실을 말하기 그런데 여기서 조건이 있다. 과장을 한 대상에게 진실을 말하면 안 되고, 진실을 말한 대상에게 과장을 하면 안 된다는 것이다. 즉, 바이러스에 감염되듯이 진실을 들을 대상과 같이 파티에 참석한 인원..

11049번: 행렬 곱셈 순서 (acmicpc.net) 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 알고리즘 파악 DP 처음부터 DP 냄새가 나서 알고리즘은 쉽게 파악했지만... 디테일 한 풀이에서 시간이 많이 걸린 문제 구현 1. 행렬의 곱셈 방식 파악하기 n*m 의 행렬과 m*k의 행렬의 곱셈식은 n*m*k이다. 즉, (ABC)(DEF) -> (A의 N) * (D의 N) * (F의 M)인 것이다. 2. DP ABCDEF의 모든 경우의 수는 -> (A)(BCDEF) , (AB)(CDEF)..

1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 생각보다 오래 걸린 문제... 처음에 잘못 접근을 해 애 먹었다. 풀이 알고리즘 파악 위상정렬+ DP 처음에 무턱대고 BFS로 접근하였다... 단순히 이전 건설 시간의 최댓값만 총 건설시간에 더하였는데 모든 정점이 서로 연결된 케이스를 풀 수가 없었다... 구현 문제의 핵심은 결국 내 건물의 까지의 총 건설시간 = (이전 테크 건물들의 총 건설시간 중 최댓값) + (내 건설시간) 이라고 생각했다. 그래..