다이나믹 프로그래밍
백준 2655번 : 가장높은탑
https://www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net 아이디어가 어렵진 않아서 풀 순 있었지만 재귀로 구현하는데 시간이 오래 걸렸던 문제다. N개의 벽돌은 각각 높이와 서로 다른 넓이의 정사각형 밑면을 갖고 있고 무게도 모두 다르다. 이 벽돌들을 차례차례 쌓아올려서 가장 높은 탑을 만드려고 한다. 벽돌을 쌓기 위해서는 밑에 있는 블록보다 위에 있는 블록의 무게가 가벼워야하고, 밑면의 넓이도 작아야한다. 탑을 가장 높게 쌓아올렸을때 사용한 벽돌의 ..
백준 9251번 : LCS
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 접근 방법을 생각하지 못해 해답을 보고 푼 문제이다. 주어진 두 문자열의 부분 수열 중, 공통으로 들어있는 가장 긴 부분 수열의 길이를 구하는 문제다. 처음 떠오른 생각은 두 문자열의 부분 수열을 모두 구하고 비교하려고 했다. 문자열의 길이가 최대 1000이기 때문에 당연히 불가능하지만 이 방법밖에 머릿속에 떠오르지 않았다. 다이내믹 프로그래밍의 메모이..
백준 12865번 : 평범한 배낭
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차원 리스트를 이용한 메모이제이션을 생각하는 과정과 사소한 실수로 푸는데 시간이 많이 소요됐다. 문제를 요약하면 N개의 물건은 각각 무게와 가치를 갖고 있는데, 주어진 배낭의 용량(K)을 넘지 않게 물건을 넣어서 배낭 안에 들어있는 물건들의 가치의 합을 최대로 만드는 ..