본문 바로가기

Algorithm/dp4

Knapsack - 제한 용량에 최대 가치 채우기 Knapsack 문제 일반화10kg 배낭에 넣을 수 있는 물건이 4개가 있고 각 물건의 무게와 가치는 다음과 같다.무게 : 5, 4, 6, 3가치 : 10, 40, 30, 50여기서 각 물건은 넣거나 넣지 않을 수 있다. 최대 가치를 구해야 하므로 가장 작은 문제 부터 최대 가치를 만들어서 10kg 문제까지 해결해보자여기서 가장 작은 문제는 1kg 배낭에 채울 수 있는 최대 가치라고 정의하자. 1. (5, 10) 의 물건1 ~ 4kg 배낭엔 채울 수 없으므로 가치는 05kg 배낭으로 가치는 10 2. (5,10) (4,40) 의 물건1 ~ 3kg 배낭엔 채울 수 없으므로 가치는 04 ~ 8kg 배낭엔 (4, 40)을 채울 수 있으므로 가치는 409 ~ 10kg 배낭엔 (4, 40), (5, 10) 추가할.. 2024. 8. 23.

[알고리즘] 개미 전사 (DP-이코테) 문제 유형 : 다이나믹 프로그래밍 문제 설명(요약) : 최소한 한 칸 이상 떨어진 인덱스의 요소들을 합하여 나가는 과정 후 최댓값을 구하는 문제 접근 : {3, 5, 4, 5, 6, 8, 4} 예제 케이스 만들기 현재 인덱스의 요소는 -2칸 or -3칸 떨어진 인덱스의 요소로부터 올 수 밖에 없음 최댓값을 구하기 위해선 -2칸 or -3칸 떨어진 인덱스와 현재 값과의 합중 최댓값으로 갱신되어야 함 점화식 추론 : A[i] = max(A([i-2] + A[i]),(A[i-3] + A[i])) 결론 : dp 리스트의 마지막 인덱스와 그 전 인덱스 중 최댓값을 구하면 원하는 답을 구할 수 있음 코드 구현 : n = int(input()) dp = list(map(int,input().split())) dp[2.. 2023. 4. 18.

[알고리즘] 합분해 (DP-GoldⅤ) 목적 : dp 테이블 손으로 써서 푸는 습관을 들이기 위해서 문제 설명(요약) : 0~N까지의 숫자 중 K개를 택해서 택한 숫자의 합이 N이 되는 경우의 수를 구하기 조건 -> 중복 허용, 숫자 위치만 바꾼 것은 다른 경우로 count 해결 전략: 1. 머리로 풀다가 이차원 dp형태로 풀어야 겠다 싶어 손으로 풀기 시작 2. 1~6까지의 경우의 수를 직접 구해봄 (조합,순열) 3. 피보나치 수열 인줄 알았는데 단순 대각선 합이였음 4. 점화식 세움 5. 끝 직접 그려본 dp 테이블 : 점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1] 2023. 3. 18.

[알고리즘] 가장 긴 증가하는 바이토닉 부분 수열 (DP-Gold IV) 목적 : 다른사람의 매우 직관적인 풀이를 복습하기 위해서 문제 설명(요약) : 증가 or 감소 , 증가+감소, 감소+증가 의 특징을 가진 바이토닉 수열 중에서 가장 긴 수열을 찾아 길이를 구하면 되는 문제 나의 시도 : 1. 가장 긴 증가 or 감소 수열에서 기울기 부호가 바뀌는 지점의 인덱스를 구해 그 후 가장 긴 반대 수열 길이 더하기 깨달은 것: 가장 긴 증가 수열이 아니더라도 가장 긴 바이토닉 수열이 될 수있다. 반대의 경우도 마찬가지 해결 전략: dp 배열에는 해당 인덱스 값마다 최대 길이가 들어있으므로 해당 시점에서의 증가수열길이 + 감소수열길이 -1 을 해주면 된다. 단 감소 수열은 top-down 방식으로 증가 수열의 길이를 할당 해줘야 겹치는 부분에서 길이 합을 구할 때 제.. 2023. 3. 18.

이전 1 다음

티스토리툴바