본문 바로가기

알고리즘

 (179)
[BOJ 5582] 공통 부분 문자열 간단한 문제인데 벙쪄있었다. 왜 그랬을까? 아마도 dp를 공통 부분 문자열의 최장 길이로 정의할려다가 보니 점화식을 못세워서 뇌정지가 왔던 거 같다.. 이 문제를 풀기 위해서는, 점화식을 세워야 한다. S1과 S2의 각 각 인덱스를 i와 j라고 하자. dp는 S1[i]와 S2[j]가 공통 부분 문자열의 마지막 부분일 때, 공통 부분 문자열의 길이의 값이다. dp[i][j] = dp[i - 1][j - 1] + 1 (S1[i] == S2[j]) dp[i][j] = 0 (S1[i] != S2[j]) 위의 점화식을 통해서 코드를 작성하면 된다. 해설코드(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 #include #include u..
[BOJ 1038] 감소하는 수(다이나믹 프로그래밍, 수학 풀이) https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. www.acmicpc.net 다이나믹 프로그래밍은 For문을 이용하거나, 재귀적으로 함수를 구성하는 것이 아니다. 문제를 나누어서 해결하는 것이다! 이 문제가 그러한 특징을 정확히 담고 있다. 새로운 감소하는 수를 찾으려면, 기존에 감수하는 수를 이용할 수 있다. 기존..
[BOJ 9084] 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. www.acmicpc.net 각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 구해야 한다. x를 임의의 동전의 값이라고 할 때, dp[M] += dp[M - x]로 식을 세우면 엄청 큰 값이 나오게 ..
[BOJ 11060] 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다. 재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해 www.acmicpc.net 다이나믹 프로그래밍의 본질은 기본 문제를, 여러 작은 문제들로 나눠서 해결하는 것이다. i번째 칸까지 점프하는 최소의 값을 생각해보..
[BOJ 2302] 극장 좌석(접근법 및 시행착오 공유) https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 N; dp[0] = 1; dp[1] = 1; dp[2] = 2; for(int i = 3; i > M; for(int i = 1; i > v..
[BOJ 2098] 외판원 순회(비트마스크, 자세한 설명) https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 분류이다. 다이나믹 프로그래밍의 본질은 소문제의 해결 방법을 이용해서 대문제를 해결하는 것이다. i번째에 방문되는 도시들과 i + 1번째 방문되는 도시들간의 관계를 정의해보자. i번째 방문되는 도시들의 집합을 A, i + 1번째 방문되는 도시들의 집합을..
[BOJ 10164] 격자상의 경로 https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 이번에 다룰 문제도, 다이나믹 프로그래밍 문제입니다. 꼭 지나야 하는 지점을 통해서, 최종 목적지(N, M)까지 도달하는 경우의 수를 찾아야 합니다. 위의 조건을 만족하는 경우의 수를 찾기 이전에, 임의의 (i, j)의 지점에 도달하는 문..
[BOJ 5557] 1학년(메모리 초과 발생 이유) https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 문제이다. 다이나믹 프로그래밍의 본질은, 큰 문제를 작은 문제를 통해서 해결한다라는 것을 잊지말자! i번까지의..

티스토리툴바