MathTrauma

문제 링크 : https://www.acmicpc.net/problem/11503 11503번: Tree Edit Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of two lines. The first line contains a string representing T1 and the second line www.acmicpc.net 문제가 길어서 대충 읽었다가 'ordered tree' 라는 조건을 놓쳐서 시간을 많이 허비했다. 자식들의 순서..

문제 링크 : https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 가장 마지막에 오는 것은 내림차순이라는 문제의 설명이 모든 것을 말해 주고 있다. N=5 인 경우 즉, 1 2 3 4 5 로 이루어지는 한 순열을 관찰해 보자. $$ 2 \; 3 \; 5 \; 4 \; 1 $$ 1. 순열에서 가장 긴 내림차순으로 이루어진 마지막 부분(suffix)을 찾았을 때, 앞 부분이 2 3 으로 시작되는 순열의 마지막임을 알게 된다. 그렇다면 앞 부분 2 3 을 바꾸어야 할 것이다. 2. 뒤의 5 4 1 중에서 3 보다..

문제 링크 : https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net $ dp[n][k] $ 는 n 을 만드는 과정에서 마지막 수가 k( =1,2,3)인 경우의 수를 뜻한다. 1. Bottom-Up 예를 들어 보자. dp[10][2] 는 2로 끝나면서 10 을 만드는 경우의 수이다. 2 를 연이어 쓸 수 없으니 덧붙일 수 있는 것은 1, 3. 1 을 덧붙여 dp[11][1] 을 만드는데 기여하고, 3을 덧붙여서 dp[13][3] 을 만드는데 기여한다. $ dp[i][j] $ 를 i 를 1 부터 차례로 ..

문제 링크 : https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 설명을 이해하는데 시간이 걸렸지만 대략 다음과 같이 해석하면 될 듯하다. 문제의 표현 '한 겹의 친구를 쓰러뜨린다.' 의 의미는 현재 0 인 칸만을 이용해서 도달할 수 있는 1 은 제거할 수 있다가 된다. (매 단계 도달한 1 은 제거하고 다음 단계로 진행한다.) 그렇다면 출발 지점(*)에서 도착 지점(#)에 이르는데 거치는 1 의 개수의 최소값 +1 을 구하는 문제가 된..

문제 링크 : https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 탑다운, 바텀업 모두를 빠르게 작성하는 연습. 자연수 i 를 제곱수들의 합으로 표현할 때 필요한 제곱수의 개수를 최소화하라는 문제이니, 이를 dp[i] 라 두자. i 이하의 수에 대해서 최소화된 개수를 모두 알고 있다면 다음이 성립한다. $$ dp[i]= \min\limits_{j^2 \le i} dp[i-j^2] +1$$ 1. Bottom-UP ..

문제 링크 : https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 조건에서 메모리의 크기가 비용의 크기보다 훨씬 범위도 넓고 큰 값을 다룬다. 문제를 다르게 해석하는 것이 풀이를 용이하게 만들어 줄 듯하다. 일정량의 메모리를 확보하기 위한 최소 비용을 구하기 보다 일정 비용으로 확보할 수 있는 최대 메모리를 구해보자. 즉, dp[i][j] 를 i 번째 앱까지 j 비용으로 확보할 수 있는 최대 메모리로 두겠다는 의미이다. #include using name..

문제 링크 : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리를 구하는 데에는 대표적인 두 알고리즘인 Prim 알고리즘과 Kruskal 알고리즘이 있다. 두 가지 모두 구현하고 몇 가지 첨언한다. 1. Kruskal Algorithm 간선의 가중치를 오름차순으로 정렬하여 하나씩 조사한다. 기존에 선택된 간선들과 cycle 을 형성하지 않으면 선택한다. cycle 을 확인하는 방법으로..

문제 링크 : https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 입력을 문자열 str 로 받아서 처리한다. p 를 문자열에서 현재 처리할 index 라 하자. dp[p] 는 p 를 시작 위치로 하는 부분 문제의 결과값을 의미한다. 세 가지 가능성이 있다. 1. 더 이상 진행이 불가능한 경우 -> str[p] 가 '0' 이 경우 해당 수를 알파벳에 대응시킬 방법이 없다. 더 이상 진행하지 않고 return 0 을 하면 된다. 가짓수를 세는 문제니 0 을 돌려준다는 ..