알고리즘 별 문제 정리 (34) 썸네일형 리스트형 [C++] 백준 9251: LCS https://www.acmicpc.net/problem/9251 모든 가능한 수열을 다 비교할경우 0.1초의 시간제한으로 인해 틀리게된다.이 문제의 경우 DP를 사용하면 편하게 풀 수 있다! 자, DP이므로 배열의 의미를 잘 지정하는 것이 중요하다. 어떤 식으로 배열을 설정하면 좋을까?이 문제는 i와 j에 각각 문자열의 문자를 대입시키고dp[i][j]의 값으로 두 문자열의 LCS를 지정하면 된다. 이 문제를 풀어보지 않았다면 i와 j에 이런 식으로 대입시키는 건 생각 못했을 거 같다. 그럼 점화식은 어떻게 구할까?dp의 경우 논리적으로 사고하기 어렵다면 시뮬레이션을 돌려보는 것이 크게 도움이 되는 경우가 많다.이 문제도 같은 경우이다. 먼저 예제의 ACAYKP를 i에, CAPCAK를 j에 대입시킨다.. [C++] 백준 12865: 평범한 배낭 https://www.acmicpc.net/problem/12865 제목을 보면 알 수 있듯이 그 유명한 배낭 문제이다. 먼저 입력을 살펴보면N: 물건의 개수 (1 ~ 100) 10^2W: 각 물건의 무게 (1 ~ 100,000) 10^5V: 각 물건의 가치 (0 ~ 1,000) 10^3K: 가방 속 최대무게 (1 ~ 100,000) 10^5 문제에서 원하는 출력은배낭에 넣을 수 있는 물건들의 가치합의 최댓값이다. 시간 제한은 2초이므로 10^8까지는 연산해도 괜찮다. DP 문제이므로 dp 배열을 만들고 각 값이 의미하는 바를 설정하는 게 중요하다.이 문제는 배낭 문제이므로 2차원 배열을 사용한다. dp[i][j]가 있을 때,i: 임의로 설정한 각 물건의 번호로 1부터 N까지 반복한다.j: 가방 속.. 이전 1 2 3 4 5 다음
