동적계획법

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - RGB 거리" 문제는 거리에 있는 집들을 R(red), G(green), B(blue)로 칠할 때, 다음 제약사항을 만족하면서 최소 비용으로 칠하는 문제입니다.인접한 집은 같은 색으로 칠할 수 없음1번 집과 2번 집은 다른 색이어야 함N번 집과 N-1번 집은 다른 색이어야 함2~N-1번 집은 양옆의 집과 다른 색이어야 함현재 집을 칠하는 최소 비용이 이전 집의 색상 선택에 따른 최소 비용에 의존하므로, 문제를 작은 부분 문제로 나누어 해결할 수 있는 최적 부분 구조를 만족하며, 동일한 계산이 반복되는 중복되는 부분 문제 특성도 있어 다이나믹 프로그래밍으로 해결할 수 있습니다. [Algorithm] 동적 계획법(Dynamic Programming, DP..

LIS이란 ❓LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)는 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 여기서 부분 수열이란, 원래의 수열에서 원소들의 순서를 유지하면서 일부 원소들을 선택한 새로운 수열을 말합니다. 증가하는 수열이란, 선택된 원소들이 항상 오름차순으로 배치되는 수열을 의미합니다.LIS 예시주어진 수열이 [10, 20, 10, 30, 20, 50]일 때, LIS는 [10, 20, 30, 50]입니다. 이 부분 수열은 주어진 수열의 원소들 중에서 가장 긴 증가하는 부분 수열로, 원래 수열의 순서를 유지하면서 오름차순으로 나열된 부분 수열입니다. LIS의 특징1. 부분 수열원래 수열에서 일부 원소들을 선택하여 만든 새로운 ..

문제설명입력 & 출력나의 풀이 이번 문제는 2xn 타일링 문제에 이어지는 문제입니다. 위 그림과 같은 타일이 존재할 때 입력으로 n을 받아 2xn의 크기의 직사각형을 채우는 문제입니다. 타일을 채우다 보면 n = 5일 때 0~5까지의 타일링의 수는 다음과 같습니다. n= 0 ➡️ 1 (채우는 방법이 없으므로 1부터 시작)n= 1 ➡️ 1n= 2 ➡️ 3n= 3 ➡️ 5n= 4 ➡️ 11n= 5 ➡️ 21위 타일링의 수를 생각해서 DP의 가장 핵심요소인 점화식을 도출해야 합니다. 좀 더 이해를 하기 쉽게 그림으로 표현하면 다음과 같습니다.  만약에 n = 3일 때를 보면 n-1의 타일에서 2x1의 타일이 추가된 것을 볼 수있습니다. n-2의 타일에서 2x2를 채우는 경우는 1x2 ➡️ 2개 2x2 ➡️ 1..

문제설명입력 & 출력 나의 풀이 이번 문제는 가로는 2로 고정되어 있고 입력받은 N의 세로 크기만큼의 직사각형에 2x1, 1x2크기의 타일을 채워 넣을 수 있는 경우의 수를 구하는 문제입니다.  부분 문제의 중복큰 문제를 작은 부분 문제로 나눌 수 있습니다.위 그림처럼 n-1인 직사각형에 2×1 타일을 세로로 놓는 경우와, 크기가 n-2인 직사각형에 1 ×2 타일 두 개를 가로로 놓는 경우로 나눌 수 있습니다. 이렇게 작은 부분 문제들이 중복되어 나타납니다. 최적 부분 구조 DP 문제는 작은 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있는 최적 부분 구조를 가집니다.n이 1~5일때 타일을 배치할 수 있는 경우의 수는 위와 같습니다. 그림을 자세히 보면 n일 때는 n-1의 타일에 2x1타일..