알고리즘

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 2차원 배열을 사용하는 dp로 접근했다. 가능한 돈의 경우의 수를 동전별로 따로 접근한다. 행에는 동전, 열에는 목표하는 원을 만들고, 그에 따라 가능한 경우의 수를 할당하였다. 배열의 열을 i라고 하고, 현재 사용하는 동전 행을 j라고 하자. 그리고 현재 n원 짜리 동전으로 계산하고 있다면 다음과 같은 점화식이 나온다. dp [i][j]=dp [i-1][j]+dp [i][j-n] 현재 dp에..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 문제를 풀기 위해서는 주어진 2개의 문자열 중 하나를 기준으로 잡아 생각해야 한다. 여기서는 그 문자열을 기준문자열, 그렇지 않은 문자열을 비교문자열이라고 하겠다. ACAYKP가 여기서는 기준문자열, CAPCAK가 비교문자열이다. 기준문자열의 길이만큼 dp 배열을 만든다. 즉 배열 칸이 의미하는 것은 각 번째의 문자를 말한다. 문자열 A C A Y..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 이 문제를 보고 가장 먼저 생각난 것은 바이토닉 수열의 중앙점이다 S1 ... SN-1 > SN에서 Sk를 말하는 것이다. Sk를 어디로 S1~SN 중 어디로 할지 정하고, S1~SK에서 나오는 증가하는 부분수열의 개수+ SK~SN에서 나오는 감소하는 부분수열의 개수를 K 값에 따라 비교해 최댓값을 출력하면 된다. 2023.06.11 - [algorithm/dp] - [백준] 11053번:..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 소위 냅색문제라고 불리는 문제이다. 2차원 배열을 사용해서 풀면 된다. 열은 무게를, 행은 몇 번째 물건까지 넣었는지 표시하고, 테이블의 각 자리에 가치를 저장한다. 냅색문제에서 물건을 대할때 선택지는 2가지다. 물건을 넣던가 혹은 그렇지 않던가. 1. 그래서 물건을 넣지 않을 거면 이전 행에서 그대로 할당받고 2. 물건을 넣..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 결국 전깃줄끼리 꼬이지 않게 하려면 어떻게 하야할까? 전깃줄들을 A에서 B로 간다는 관점으로 바라보자. A에서 시작하는 점을 1~10까지 오름차순으로 정렬할 때. 그 줄에 대응하는 B 역시 오름차순으로 정렬되면 된다. 문제에서는 (A,B) 형태로 입력을 받는다. 그렇다면 A와 B를 pair형태로 저장하고, A를 기준으로 정렬한다. 그리고 A를 기준으로 정렬한 페어쌍에서 B부분만 추출해, 몇 개가 빠..

풀이 포도주를 먹어서 얻는 값은 모두 양수이다. 즉, 무조건 먹을 수 있으면 먹는게 이득이다. 입력값들을 arr[]에 저장한다. 그리고 동적계획법을 위한 dp[]를 만든다. dp[n]은 n번째 잔을 마지막으로 먹었을 때 가지는 최대의 점수 값이다. 하지만 n-2,n-1번째 잔까지 모두 먹은 경우는 n번째 잔을 먹을 수 없다. 즉 이번에 먹는 잔이 1.(n-2번째 잔은 먹지 않은 상태) AND (n-1번째 잔은 먹은 상태) 거나 2.(n-2번째 잔은 먹은 상태) AND (n-1번째 잔은 먹지 않은 상태) 여야 한다. 둘다 먹지 않은 상태는 위에서 쓴데로, 무조건 먹는게 이득이라고 했으니 생각하지 않는다. 즉 1번 식은 n-3번째까지 먹었을 경우의 최댓값에 n-1번째 잔과 n번째 잔을 더하고 2번 식은 n-..

풀이 숫자가 들어있는 직사각형 표가 주어진다. 그리고 주어진 표에서 직사각형모양으로 수를 선택할 때 그 직사각형 안 수들의 합을 구하라는 문제다. 반복문을 통해 그때그때 답을 구하게 된다면 큰 수가 주어졌을 때 시간초과가 날 것이다. 최대로 계산하는 경우는 1024*100,000으로 대략 10억 번이다. 그런데 문제 제한 시간은 1초로 초당 1억 번 정도 계산한다고 치면 시간초과가 나는 것이다. 그래서 우리는 이 문제를 동적계획법을 이용한 합으로 계산할 것이다. sum 배열에는 0,0 부터 그 위치를 꼭짓점으로 하는 직사각형을 그리고 그 합을 저장한다. 가령 sum[1][3]에는 arr [0][0], arr [0][1], arr [0][2], arr [0][3], arr [1][0], arr [1][1]..

풀이 수열에서 n번째 중 몇 번째에 오는지 표시하는 열과, 1~9까지의 수를 나타내는 열로 2차원 배열 arr을 만든다. 그리고 배열에는 그 번째가 그 숫자로 끝날 때의 값을 넣는다. 가령 arr [2][3] 은 2번째 자리가 3으로 끝날 때의 계단 수이다. 계단 수의 규칙에 따라, 0으로 끝났다면 앞 수는 1이어야만 계단수이다. 1로 끝났다면 앞 수는 0이나 2여야만 계단수이다. 2로 끝났다면 이전수는 1이나 3이어야만 계단수이다. 3으로 끝났다면 이전수는 2나 4여야만 계단수이다. . . . 8로 끝났다면 이전수는 7이나 9이어야만 계단수이다. 9로 끝났다면 이전수는 8이어야만 계단수이다. 즉, arr [m][n]=arr [m-1][n+1]+arr [m-1][n-1]이다. (단, n이 0이면 arr ..