본문 바로가기

알고리즘/백준

(109)
[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번까지의..
[BOJ 10942] 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍의 단골 소재인 팰린드롬이다. 다이나믹 프로그래밍의 핵심은, 큰 문제들을 해결하기 위해서 작은 문제들의 값을 이용하는 것이 핵심이다. 그렇다면, 팰린드롬을 분석해보자. 인덱스 i ~ j의 숫자들이 팰린드롬인지 확인해야 한다. 다이나믹 프로그래밍의 본질, 큰 문제를 해결하기 위해서 작은 문제들의 값을 이용해보자. DP[i][j]를 인덱스 i부터 j까지 펠린드롬 여부라고 정한다. DP[i][j]를 큰 문제라고 했을 때, ..
[BOJ 9251] LCS(왜 동적계획법인가?) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 정말 다이나믹 프로그래밍의 정석같은 문제라고 볼 수 있다. 이 문제를 재귀 함수나, 동적 계획법으로 풀지 않았을 경우를 생각해보자. 두 문자열중에, 짧은 문자열을 사용해서 나올 수 있는 조합들을 모두 체크해본다고 가정하자. 짧은 문자열의 길이가 5라고 가정하면, 5C0 + 5C1 + 5C2 + 5C3 + 5C4 + 5C5의 연산이 필요하다. ..