728x90 반응형 백준 알고리즘/dp9 [백준 9251][파이썬] LCS (최장 공통 부분 수열) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp[x][y]를 다음과 같이 정의한다. dp[x][y]는 첫 번째로 입력받은 문자열을 s1이라 하고 두 번째로 입력받은 문자열을 s2라고 한다면 s1에서 x번째 문자까지와 s2에서 y번째 문자까지를 비교했을 때 최장 공통 부분 수열의 길이이다. 예를 들어 dp[2][4]라고 한다면 "AC"와 "CAPC"의 최장 공통 부분 수열의 길이인 "AC"즉, 2.. 2023. 3. 18. [백준 11066][파이썬] 파일 합치기 (dp 알고리즘) https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net dp를 활용하여 삼중 반복문을 사용하여 푸는 문제이다. dp[x][y]는 다음과 같이 정의한다. 인덱스 x 파일부터 인덱스 y 파일까지 하나의 파일로 합치는데 필요한 최소비용 이를 이용하여 dp 알고리즘을 적용하면 된다. 가장 먼저 x와 y가 동일한 경우를 보자. 다음과 같이 파일들의 크기를 나열할 때 15 1 21 3 4 5 35 5 4 3 5 98 21 14 17 32 dp[0][0].. 2023. 3. 15. [백준 2839][파이썬] 설탕 배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net dp로 문제를 풀어보았다. dp[i]의 값은 N이 i일 때의 배달하는 봉지의 최소 개수이다. 만들 수 없다면 -1을 저장한다. 1. 먼저 길이가 N+1이고 모든 값이 -1인 리스트를 생성한다. dp=[-1]*(n+1) 만약 N킬로그램을 만들 수 없는 경우 dp[i]의 값을 변경하지 않으면 된다. 2. dp[1]부터 dp[5]까지는 미리 값을 넣어준다. dp[1:6]=[-1, -1, 1, -1, 1] 3. .. 2023. 1. 23. [백준 1699][파이썬] 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 일단 dp[i]의 값을 i를 제곱수들의 합으로 표현할 때 최소 개수로 정한다. 그렇게 되면 dp[i]의 값은 dp[1] + dp[i-1] dp[2] + dp[i-2] dp[3] + dp[i-3] . . . 위 값들 중 가장 작은 값이 된다. 처음엔 위 방식으로 이중 반복문을 돌려서 답을 구했으나 시간 초과가 발생했다. 시간을 더 줄일 수 있는 알고리즘을 사용.. 2023. 1. 14. 이전 1 2 3 다음 728x90 반응형
