9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 읽기 LCS, 즉 최장 공통 부분 수열의 길이를 찾으면서, 동시에 수열까지 구해야 하는 문제이다. 이전에 한 번 풀어봤지만 잘 기억이 나지 않아 다시 공부하면서 풀어보았다. 한 마디로 DP를 활용하면 된다. 문제 풀기 LCS 수열 길이 구하기 일단 점화식을 찾기 위해 그려봤다. 이런 식으로 구할 수 있다. 즉, 두 문자열에서 str1의 i번째 문자, str2의 j번째 문자가 같은지, 같지 않은 지에 따라서 점..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 읽기 일단 해당 문제는 흔히 LIS라고 하는 가장 긴 증가하는 부분 수열을 찾는 문제이다. 처음에 봤을 때는 tree모양이 생각났지만, 그려보니 아닌 것 같았다. 찾다 보니 DP라는 것을 알았다. 문제 풀기 N이 최대 1000이기 때문에 이중 for문을 통해 탐색해도 복잡도에 걸리지 않는 시간이다. 다음과 같은 과정을 통해 문제를 해결할 수 있다. 주어진 숫자 배열을 입력 받는..

2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 아 역시 DP 문제는 쉽지 않다. 사실 그렇게 어려운 문제인 것 같지는 않지만.. 처음에 DFS로 했다가 2^1000이니까 당연히 시간초과가 나고, 거의 바로 아 DP인 것 같다는 생각을 했다. 그런데 처음에 N, K로 접근하지 않고, 첫 번째 원소를 선택하는 경우, 첫 번째 원소를 선택하지 않는 두 가지 경우를 생각했다. 즉, N, 2로 접근했다. 그런데 이렇게 하니 DP 배열에 경우의 수를 저장하는 게 아닌, 선택한 원소의 개수를 저장하게 되고 답을 제대로 구하지 못했다..

17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 읽기 처음에 DFS로 풀었는데 어김없이 시간초과.. 처음부터 시간초과가 나지 않을까 생각하긴 했는데, 최대 1000개의 집이 각각 2번씩 선택지가 있으니까 2^1000쯤 되려나? 싶다. (시간 계산 하고 풀자 ㅠㅠ) 어떻게 하지? 하다가 아 DP구나 싶었다. 최소 비용.. 넘치는 시간.. DP는 문제를 보고 이게 DP인지 파악하는 게 제일 힘들다던데 맞는 것 같다. 감을 잃지 말자. 문제 풀기 첫 번째 집에 칠한 색이 각각 R, ..

2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 문제 읽기 일단 문제를 처음 읽고서는 BFS로 풀었었다. 하지만 거의 바로 메모리 초과가 났었고! 맵의 크기는 작지만 k의 존재와 중복 방문이 가능하기 때문에 BFS 수행 시 큐가 터져버리는 것이었다. (어쩐지 골드3인데 너무 쉽게 풀려서 이상했다.) 그래서 DFS로 접근했다. 단순 DFS를 처음에 했는데, 아무래도 중복 방문이 가능하다보니 이번엔 시간 초과가 났었다. 질문 게시판을 조금 뒤져서 메모제이션을 사용한다는 방식을..

10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 읽기 일단 맨 처음에 문제를 읽었을 때는 투포인터가 생각났다. 구간을 입력 받을때마다 투포인터를 사용해서 팰린드롬인지 아닌지 판단하는 방식이다. 일단 코드를 빠르게 짜긴 했는데, 제출은 안했었다. 문제 입력의 크기를 봤다. N은 2000까지, 숫자는 100,000까지, 질문의 개수 M은 1,000,000까지 가능했다. 만약 맨 처음 푼 방식대로 제출했다면 시간 초과가 나왔을 것이다. 시간 복잡도가 M * N이 되기 때문에 제한 시간인 0.5초는 거뜬히 넘을 것 같다. 그렇게 생각하고 한 번 제출해..