Hello, Freakin world!

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 바로 전에 LIS 문제를 풀었음에도 한참 헤맸습니다. 기존 LIS 로직을 그대로 쓰려면 입력 배열을 정렬할 필요가 있습니다. 정렬을 하지 않으려면 따로 처리를 해줘야 하는데 이 부분을 간과했네요. 정렬이 필요한 이유는 전깃줄이 꼬이는 조건과 관계가 있습니다. 줄 a,b가 있다고 할 때 줄이 꼬이지 않는 조건은 다음과 같습니다. - a.start b...

www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 이 문제를 계기로 다시 종만북을 펼쳐서 DP를 다시 공부했는데, 새로운 깨달음을 얻을 수 있었습니다. 지금까지 DP 문제를 풀 때, 어떤 유형는 메모이제이션을 이용해 풀어야 되고 어떤 문제는 점화식을 찾아서 바텀업으로 풀어야 된다는 식으로 문제를 분류했었는데 그럴 필요가 없었습니다. 이때까지 바텀업 방식의 풀이를 이용했지만 약간은 불편했습니다. 뭔가 직관적이지 않다라는 느낌을 지울 수 없었기 때문입니다. 그럼에도 ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 그래프의 최단 거리 알고리즘을 기반으로 하는 구현 문제입니다. 이 문제의 포인트는 역시 최단 거리의 물고기를 찾고 선택하는 과정에 있습니다. 저도 여기서 한참 헤맸는데요. 문제의 조건을 이렇습니다. 1. 최단 거리의 물고기가 여러 마리일 때, 위쪽에 있는 물고기가 먼저 우선 순위를 가진다. 2. 높이가 같다면 왼쪽에 있는 물고기의 우선 순위가 더 높다. 제가 이 문제에서 헤맸던 이유는 ..

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 이 문제를 제대로 이해하려면 기존의 기본적인 BFS 개념에 차원을 하나 더해야됩니다. 지도 위에 두 개의 층이 있다고 생각할 수 있습니다. 하나는 벽을 부수지 않은 경로를 표시하는 지도, 하나는 벽을 부수고 이동하는 경로를 나타내는 지도. 아래의 그림을 보면 쉽게 이해할 수 있을겁니다. 대부분의 간단한 BFS 예제들은 행렬 상의 2차원 평면에서 움직이지만, 이 문제는 벽을 부쉈는지 ..

www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA 은 간단하게 트리 구조의 특성을 이용해 단순하게 해결했는데, 이번 문제는 효율성을 고려하지 않으면 풀 수 없었습니다. 영어로 LCA로 검색을 해보면 이 문제에 관해 여러 가지 풀이가 존재한다는 걸 알 수 있습니다. cp-algorithms.com/graph/lca.html Lowest Common Ancestor - O(sqrt(N)) and O(log N) with O(N) preproces..

www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net 트리 구조의 특성을 생각해보면 풀이를 떠올릴 수 있다. 트리 구조에서 하나의 노드는 다수의 자식을 가질 수 있지만 부모 노드를 오직 하나만 가진다. 그렇기 때문에 각 노드에서 부모 노드의 참조를 저장해두면 두 개의 노드에서 따라올라가면서 최소 공통 조상을 찾을 수 있다. 까다로운건 이 문제에서 입력으로 트리를 구성하기 위해서는 일단 양방향 노드 그래프를 만들어야 되는데, 나는 그냥 한번 임시 트리를 만들..

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP 문제를 계속 풀고 있는데, 패턴이 참 다양하다는 생각이 듭니다. 그리고 꽤 재밌네요 ㅋㅋㅋ 핵심 아이디어는 위처럼 (i,j) 위치의 값이 1일 때 위, 왼쪽 위, 왼쪽 위치의 요소도 1이면 정사각형 만들어 진다에서 출발합니다. 나머지는 저 위의 아이디어를 기반으로 점화식을 작성하면 됩니다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java..

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 이때까지 DP와는 성격이 조금 다른 문제였다. 이전까지는 단순히 완전 탐색의 바텀업 버전이었지만 이 문제는 재귀를 이용한 탑다운 방식에 cache배열을 추가하면서 해결할 수 있다. 이 문제에서 가장 중요한 한 문장이 있다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는..

www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제를 제대로 이해만 하면 쉽게 풀 수 있는 문제입니다. 비행기의 종류에 간선 하나가 대응하기 때문에모든 도시를 탐색할 수 있는 최소한의 비행기 종류는 그냥 단순히 모든 노드를 다 탐색하는데 필요한 간선의 수입니다. 네. 그냥 단순 그래프 순회 문제입니다. import java.io.*; import java.util.ArrayList; import java.util.Lis..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 글의 초점은 문제 풀이에 있지 않다. 그러므로 바로 본론으로 들어가겠다. 이 문제의 점화식은 다음과 같다. 아직 몇 문제 풀어보진 않았지만 지금까지 풀어본 DP 문제들은 '완전 탐색의 바텀-업 버전'이었다. 이런 문제들은 완전 탐색을 바텀업으로 구현하기 위해 점화식을 세울 필요가 있다. 이 점화식도 그냥 하늘에서 떨어지는게 아니라 완전 탐색의..