랄뚜기의 코딩일기

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 문제 행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.) 행의 수가 3이고 열의 수가 5인 ..

https://www.acmicpc.net/problem/24464 24464번: 득수 밥 먹이기 $N$일 치 식단표를 만들 때 가능한 경우의 수를 $1\,000\,000\,007(=10^9+7)$로 나눈 나머지를 출력한다. www.acmicpc.net 문제 프로젝트 하느라 바쁜 득수는 밥 먹을 시간이 부족하다. 그래서 주로 찾는 식당 네 개 중 하나에서 하루에 한 번 밥을 먹는다. 귀찮으면 굶을 때도 있다. 늘 새로운 느낌을 받고 싶었던 득수는 다음과 같은 규칙으로 다음날 갈 식당을 정한다. 첫날에는 굶거나, 임의로 원하는 식당 하나를 골라서 간다. 어제 굶지 않았다면, 오늘은 식당을 가지 않아도 된다. 어제 식당을 가지 않았다면, 오늘은 식당을 가서 밥을 먹어야 한다. 오늘 간 식당은 다음날 가지 않..

https://www.acmicpc.net/problem/11660 이 문제를 풀기 위해서는 dp[i][j]가 1,1부터 i,j까지 영역의 합을 나타내야 한다. 위와 같은 값이 주어졌다고 가정해보자. 배열의 각 칸에는 1,1부터 i,j까지의 영역의 합을 입력해야 한다. ?에는 1+2+5+7, 즉 15가 와야 한다. 파란 영역(1+5)과 빨간 영역(1+2)을 활용하여 ? 값을 구하기 위해서는 중복되는 부분(1)을 빼줘야 한다. 점화식을 세우면 dp[i][j]=input[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1] 이란 것을 직관적으로 알 수 있다. 이제 dp 배열을 활용하여 답을 구하면 된다. 초록색 영역의 합을 구해야 된다고 가정하자. 초록색 영역=빨강색 영역-주황색 영역-노..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 그냥 LCS문제인줄 알았는데 공통되는 문자열을 구해야하기 때문에 공통된 문자들이 연속적이어야 한다는게 기존 LCS문제와 달랐다. 기존 LCS에서 LCS[i][j]가 나타내는 것이 한 문자열의 i번째와 다른 문자열의 j번째까지 공통된 문자의 개수였다면 이 문제에서 LCS[i][j]가 의미하는 바는 한 문자열의 i번째와 다른 문자열의 j번째까지의 공통 부분 문자열의 크기를 저장해야 한다. ..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 저번 학기 알고리즘 설계 분석에서 배운 행렬 곱의 최소화 문제와 같은 알고리즘이다. 막상 수업시간에 이해를 하지 못했는데 이번에 다시 문제를 보면서 제대로 이해했다. 이 문제를 풀기 위해서는 위와 같은 방식으로 반복문을 돌 줄 알아야 한다. 위 처럼 반복문을 돌기 위한 코드는 다음과 같다. for(int j=1;j>K; for(int i=1;i>K_[i]; sum_[i]=sum_[i-1]..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 사용가능한 메모리가 4MB라는 것을 주의해야 한다. 나는 평소 dp처럼 모든 값을 받고 연산하는 것이 아니라 메모리를 줄이기 위해 값을 받을 때마다 연산하도록 구현하였다. max_배열과 min_배열을 이용하였는데 max_에는 현재까지 내려가는 비용의 최댓값을, min_배열에는 현재까지 내려가는 비용의 최솟값을 저장해 주었다. #include #include #include #include #include #in..

https://www.acmicpc.net/problem/13841 13841번: It Prefokery Pio You are a member of a secret society named Japanese Abekobe Group, which is called J. A. G. for short. Those who belong to this society often exchange encrypted messages. You received lots of encrypted messages this morning, and you tried to decrypt them a www.acmicpc.net 이 문제는 어떤 문자열이 주어졌을 때, 해당 문자열로 만들 수 있는 가장 긴 palindorme을 구하는 문제이..

https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 쉬워보여서 도전했는데 플레는 역시 플레 문제... 다른 분의 코드를 참조하여 풀었지만 다행히 방식이 똑같았다. leftdown에는 왼쪽 밑, rightdown에는 오른쪽 위, leftup에는 왼쪽 위, rightup에는 오른쪽 위로 얼마나 긴 선분이 존재하는지 저장하였다. 그리고 각 점 ( i , j )를 방문하면서 왼쪽 밑으로 가는 선분의 길이(leftdown)와 오른쪽 밑으로 가는 선분의 길이(rightdown) 중 작은 값 k를 골라 1부..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp의 대표문제인 LCS문제를 풀었다. dp의 핵심은 dp배열이 무엇을 의미하는지 알아내는 것이 핵심이다. i=첫번째 문자열(s1)의 인덱스, j=두번째 문자열(s2)의 인덱스라고 할 때, dp[i][j]는 s1의 i번째 s2의 j번째까지 비교했을 때 LCS2의 최대 크기를 의미하게 된다. LCS를 구하는 알고리즘은 다음과 같다. 1. s1[i]==..