MathTrauma

문제 링크 : https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 어설픈 영어 실력에도 불구하고 원문이 이해하기 쉬워서 그쪽으로 내용을 정리한다. n 개의 점의 좌표가 주어지고 그 점들 중 일부는 m 개의 도로로 연결되어 있다. 아직 연결되지 않은 점들을 최소의 비용(도로의 길이)으로 연결하는 문제이다. 1. 미리 주어진 m 개의 간선(도로)를 제한 나머지 모든 점들 사이에 간선을 만들고 비용 오름차순으로 정렬한다. 2...

문제 링크 : 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 을 확인하는 방법으로..