본문 바로가기

알고리즘

 (179)
11066번 : 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 이번 문제는, DP 점화식을 생각하지 못해서 구글링 통해서 코드를 참고했다. 뭔가, 사칙 연산에 관련된 것은 항상 같은 방식으로 ..
6359번 : 만취한 상범 https://www.acmicpc.net/problem/6359 6359번: 만취한 상범 문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고 www.acmicpc.net 이 문제도 DP를 잘 정의하면 쉽게 풀 수 있다. 동적 계획법에서 항상 메모이제이션이 필요한 것은 아니다. 자, DP를 만약에 현재 ..
1309 : 동물원(Bottom-Up, Top-Down) https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이번 문제는, 점화식을 생각해서 잘 풀었다. DP[N]을 세로 길이가 2 * N인 우리에 사자를 놓는 방법이라고 가정하자. DP[N - 1]을 이용해서, DP[N]을 구할 수 있을까? DP[N - 1]의 마지막 우리에 사자가 좌, 우 혹은 없음에 따라서, DP[N]에 나올 수 있는 값이 달라진다. 따라서, DP에 마지막 우리에 사자의 좌, 우 혹은 없음을 표시해줘야 한다. 0 - 사자가 좌 1 - 사자가 우 2 - 사자가 없음 이라고 했을 때, DP를 세워보자. DP[0][N] = DP[1][N - 1] + DP[2][N - 1]..
2225번 : 합분해(점화식의 중요성) https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 규칙을 찾아보려고 했을 때 쉽지 않았다. DP에서 가장 중요한 것은 점화식이 아닐까... 우선 점화식이 찾는 습관부터 들이도록 하자. 하향식 접근으로 간단하게 문제를 풀어보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #include using namespace std; int N, K; long long dp[201][201]; long long solve(int N, int K) { if (K == ..
1890번 : 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 이 문제는 기분좋게 풀었다. DP를 이용한 하향식 접근으로 문제를 해결했다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 1..
11054번 : 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 못 풀어서 해설을 본 문제. 증가하는 부분 수열을 두 번 이용하면 풀 수 있는 문제. DP 정의가 복잡해지고 있다면, 문제의 해결 접근 방법이 맞는지 다시 생각해봐야 한다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 ..
1520번 : 내리막 길(C++, 시간 초과, Bottom-up, Top-down) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. www.acmicpc.net 이번 문제는, 다이나믹 프로그래밍 문제이다. 대학생 때, Bottom-up 접근 방법, Top-down 접근 방법들을 배웠던 기억이 난다. 그러면서 호출되는 순서를 그래프로 표현해봐라는 과제가 있었는데, 하면서도 이걸 왜하나 싶었는데... 이제 그 중요성을 알 수 있었다. 또한, 지금까지 접근했던 문제들이 B..
1904번 : 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 오랜만에 깔끔하게 풀은 문제! DP문제로 분류되어 있어서, DP로 접근하긴 했다. 이 문제는 비교적 쉬운 DP문제라 노골적으로 DP문제임..

티스토리툴바