본문 바로가기
반응형

다이나믹프로그래밍5

[골드5]백준 12865번(평범한 배낭) - 코테공부 36일차(2025.02.26) 문제유형다이나믹 프로그래밍(동적 계획법)풀이 방법 도출 과정1. 물건 N개의 물건이 있다. 각 물건은 무개W와 가치 V를 가지는데 최대 K만큼의 무개만큼 넣는다고 가정했을 때, 가치V가 가장 높을 때의 값을 구하는 문제이다.2. 첫 줄에 입력은 N, K 나머지는 W, V이다. 3. 가장 먼저 일단 가장 W가 채워질 가능성을 찾고 그 뒤로 그 가능성 중에 가장 나은 것을 고르는 방법이 있다. 이 방법은 최악의 경우 100C50이 나오는데 이는 1억을 넘는 것이기에 사용하지 않겠다. 4. 두번째로 그리디 알고리즘을 사용하는 방법이 있는데 이를 위해 가치 대비 무개 비율이 높은 순서대로 정렬한 다음 가능한 한 많은 물건을 선택한다고 해서 정확한 최적해를 보장하기에는 적절하지 않다. 5. 그러므로 동적 계획법을.. 2025. 2. 26.
[브론즈1]백준 2775번(부녀회장이 될테야) - 코테공부 36일차(2025.02.26) 문제유형다이나믹 프로그래밍(동적 계획법)풀이 방법 도출 과정1. 아파트의 거주 인원을 계산하는 문제이다. 특정 층(k)와 호(n)에 몇 명이 살고 있는지 구해야한다.2. 거주 규칙은 다음과 같다. 3. 0층의 i호에는 i명이 거주한다.4. k층의 n호에 살려면, 바로 아래층(k-1)의 1호부터 n호까지 거주하는 사람들의 합만큼 데려와야 한다. 5. 예를 등러 1틍과 2층의 3호까지를 살펴보자1층1호: 0호 1호(1명) -> 1명2호: 0층 1호(1명) + 0층 2호(2명) -> 3명3호: 0층 1호(1명) + 0층 2호(2명)  + 0층 3호(3명) -> 6명따라서 1층 3호 (n호)거주 인원은 총 6명이다. 2층1호: 1호 1호(1명) -> 1명2호: 1층 1호(1명) + 1층 2호(3명) -> 4명3.. 2025. 2. 26.
[골드5]백준 9251번(LCS) - 코테공부 31일차(2025.02.23) 문제유형동적 계획법풀이 방법 도출 과정1. 두 개의 부분 수열이 주어졌을 때, 두 수열 모두에 공통으로 등장하는 부분 수열의 개수를 구하는 문제이다.2. 각 수열의 가능한 부분 수열의 수는 길이가 n일때 약 2에 n 개이다.  에를 들어 길이가 1000인 수열은 2에 1000개의 부분 수열을 갖게 되므로, 모든 경우를 생성해 비교하는 방식은 계산량이 기하급수적으로 증가해 실제로는 불가능하다.3. 그렇다면 그리디 알고리즘으로 접근해보도록 하면 한 수열을 순회하며 특정 패턴(예: 'A', 그 다음 'AC' 등)을 차례로 찾아 나가는 그리디 방식은 일부 경우에는 효과적일 수 있으나. 항상 최적의 해답을 도출하지 못할 뿐 아니라, 최악의 경우 불필요한 중복 연산이 많아져 시간 복잡도가 크게 증가할 수 있다.4... 2025. 2. 23.
[실버1]백준 1149번(RGB거리) - 코테공부 29일차(2025.02.20) 문제유형수학풀이 방법 도출 과정1. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 것이 문제 - i-1과 i+1 과 i는 각각 색이 같으면 안됨3. 각 비용이 낮은 것을 찾으면 됨 단, 이동하면서 칠하기 때문에 잘생각해야함4. 만약 이렇게 있을 경우5.26 40 8349 60 5713 89 99  1) 26 2) 57 3) 13이렇게 해서 96이렇게 구해나가면 된다.6. 이 문제는 현재 집을 칠하는 비용을 이전 집들의 최소 비용과 연계하여 계산해야 하므로, 재귀 함수를 활용한 해결이 가능하다. 즉, 집 i를 칠하는 비용은 i-1번째 집까지의 최소 비용을 고려한 결과로 나타낼 수 있다. 이를 통해, 각 집을 칠하는 최소 비용.. 2025. 2. 20.
[실버2]백준 11048번(이동하기) - 코테공부 28일차(2025.02.19) 문제유형그리디 알고리즘풀이 방법 도출 과정1. 준규의 이동 경로는 오른쪽, 아래, 대각선 오른쪽 아래로 제한되어 있으므로, 각 위치에서 도달할 수 있는 최대 사탕 개수를 저장하는 DP 테이블을 구상할 수 있다. 2. 구체적으로 각 위치 (r, c)의 값은 이전에 도달할 수 있는 세 위치 (r + 1, c), (r, c + 1), (r + 1, c +1) 중 최대값에 현재 위치의 사탕 수를 더한 값으로 갱신된다.3. DP 테이블을 구성할 때, 아직 방문하지 않은 위치의 값은 0으로 초기화한다. "단, 가장 먼저 숫자가 0인 숫자는 최소화해야한다."라는 표현은 초기 상태나 경로 선택 시 0의 영향을 최소화해야 한다는 의미로 해석할 수 있으며, 이 경우 DP 테이블 초기화 및 경계 처리에 주의한다.4. 모든 .. 2025. 2. 19.
반응형

티스토리툴바