동적계획법

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타일..

문제설명입력 & 출력 나의 풀이 이번 문제는 피보나치 N에서 0과 1의 개수를 출력하는 문제입니다. 피보나치수열은 워낙 유명하기 때문에 어렵지 않게 풀 수 있지만 이 문제는 기존의 피보나치 함수를 재귀호출로 푼다면 런타임 에러가 발생합니다. 따라서 동적 계획법(DP)를 사용해야 합니다. 먼저 피보나치 함수를 점화식으로 표현한다면 다음과 같습니다.F(n) = F(n-1) + F(n-2)위 점화식을 기준으로 이미 계산된 값들을 배열에 저장하여 중복된 계산을 방지해야 합니다. 먼저 dp배열을 초기화해줍니다. 첫 번째 배열은 피보나치 수의 인덱스이며, 두 번째 배열은 크기가 2를 가지는 데 0번째는 0의 개수, 1번째는 1의 개수가 들어가게 됩니다. 이제 fibo(0)과 fibo(1)은 이미 값이 정해져 있기 ..