https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 난이도에 비해 티어가 높게 책정되었다고 생각하는 문제이다. (그리고 나와 똑같이 생각한 사람이 꽤 되는 것 같다.) 펠린드롬 문자열의 성질을 이용하면 아주 간단하게 풀 수 있다. 어떤 문자열이 펠린드롬이면, 그 문자열의 양끝 문자를 제외한 문자도 펠린드롬이다. 따라서 dp[s][e] 를 s 부터 e 까지의 문자열의 펠린드롬 길이라고 한다면 dp[s][e] = dp[s+1][e-1] + 2 이다. 단, 위 점화식의 조건은 dp[s+1][..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net BFS를 응용한 단순 구현문제이다. 내가 푼 알고리즘은 다음과 같다. 1. 외곽을 모두 돌면서 빈공간의 위치를 덱에 넣고, 열쇠는 먹은 후 빈공간으로 바꾼다음 위치를 덱에 넣고, 문은 맵에 문 위치를 저장한다. (이때 같은 문이 여러개 있을 수 있으니, 맵에 리스트를 저장한다.) (열쇠는 같은 열쇠가 여러개 있을 수 있으니 집합에 저장한다.) 2. 현재 갖고 있는 열쇠로 열 수 있는 문을 모두 연다. 문을 열..
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 자료구조를 사용하는 그리디 문제이다. 우선해야하는 조건이 2개가 엮여 있어서 난이도가 있는 문제였다. 나는 그리디 알고리즘 강의를 다시 복습해서 보고나서 아래와 같은 사고로 문제를 풀었다. 결국 그리디도 최적해를 구하는 알고리즘 중 하나인데, 이 문제에서 구해야하는 것은 '보석 가치 합의 최대'이다. 그렇다면 일단 보석의 가치만 놓고보면..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 오늘 백준을 들어가보니 AC Rating이 갑자기 50정도 늘어나있었다. 아무 문제도 푼게 없는데 무슨 일인가 싶다...ㅋㅋㅋ 얼떨떨한 기분으로 푼 문제, '도시분할계획'이다. 이 문제는 MST 응용문제인데, 두 MST의 합을 최소로 해야한다는 점이 조금 까다롭게 느껴졌다. 처음에는 두 MST에 속할 노드를 백트레킹이나 조합으로 골라서 매번 MST를 구해야하나..
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 단순 BFS 문제를 구현하기 어렵게 내면 이렇게 나올 수 있다는 걸 보여준 문제이다.. 2048과 비슷하게 그냥 상하좌우 이동을 구현하고, 모든 경우의 수를 세면 된다. 각 이동마다 가능한 경우의 수가 상하좌우 4방향 이고, 10번을 넘는 이동은 의미가 없으므로 진짜 의미로 모든 경우의 수는 4^10 = 약 100만 의 경우의 수겠지만, 이 경우의..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 개인적으로 solved.ac 난이도에 비해 힘들게 푼 DP 문제이다. 이 문제는 1가지만 떠올리면 정말 정말 쉽게 풀린다. 현재 문제에서 요구하는게 '없애야 하는 전깃줄 개수의 최솟값'이다. 하지만 전체 전깃줄의 개수가 고정되어 있다는 점에서 이를 뒤집어 생각하면 '남겨야 하는 전깃줄 개수의 최댓값'을 구해서 이 문제를 풀 수도 있다. 이렇게 발상의 전환만 성공했다면, 이 문제는 단순한 LIS 문제로 바..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제는 그래프 탐색 문제를 조금 꼬아낸 문제이다. 제일 나이브한 풀이는 각 벽에 대해 BFS를 수행하는 것인데, 아무리 봐도 이건 시간 초과 풀이이다. 전체 영역이 최대 100만 칸짜리 2차원 배열인데, 이를 중복해서 순회하면 시간 초과가 안날 수 없다. 2차원배열을 한번만 순회하여, 그 결과를 이용해 답을 도출해야 한다. 그래서 나는 비어있는 영역에 대해 BFS를 수행하..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048 게임의 타일 이동을 구현하는 문제이다. 최대 이동 횟수가 5회로 매우 작은데, 한번에 이동에서 선택할 수 있는 경우의 수가 '상하좌우' 4가지 이므로 모든 경우의 수가 4^5 = 1024 이다. 모든 경우의 수를 저장하기 위해서 각 경우마다 최대 20*20 사이즈 판을 순회해야 하므로 한 경우의 수당 연산횟수는 400이다. 1024 * 400 은 굳이 계산해보..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 여러가지 방법으로 풀 수 있는 세 용액 문제이다. 나는 처음에 이분탐색을 시도 했다가 막혔는데, 구현을 쓸데없이 복잡하게 하다가 실수를 했던 것 같다. 2시간 고민하다가 다른 이분탐색 풀이 알고리즘을 보고 수정하여 맞았다. 이 문제를 투 포인터로 풀 수 있겠다는 생각까진 해봤는데, 구체적으로 어떻게 투 포인터를 써야할 지 떠오르지가 않았다. 그렇게 공부하여 알게된 알고리즘이 ..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 스티커 문제를 발전 시킨다면 이 파이프 옮기기 문제가 될 것 같다. 좋은 DP 연습문제이다. 처음에는 당연히 BFS를 이용해서 풀어야겠다고 생각했는데, BFS로는 최단경로를 찾아보기만 했지, 최단경로의 '개수'를 세어보진 않아서 백준님의 표현을 빌리자면, BFS의 형태를 모방한 브루트포스 풀이로 밖에 짜지지가 않았다. (그리고 이 방식은 당연하게도 시간초과를 받는다..) ..