Algorithm/Dynamic Programming (3) 썸네일형 리스트형 [Algorithm] 최장 증가 부분 수열(LIS) 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. {6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 {2, 5, 8, 7} 이고, 길이는 4 {2, 5}, {2, 7} 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것은 {2, 5, 8, 7} {10, 20, 10, 30, 20, 50} 이라는 배열이 있을 경우, LIS는 {10, 20, 30, 50} 이고, 길이는 4 D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대길이 라고 정의할 때, 가장 긴 증가하는 부분 수열을 계산하는 점화식을 작성해보면, 다음과 같다. (DP 테이블.. [Algorithm] 1로 만들기 문제 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. 1) X가 5로 나누어떨어지면, 5로 나눈다. 2) X가 3으로 나누어 떨어지면, 3으로 나눈다. 3) X가 2로 나누어 떨어지면, 2로 나눈다. 4) X에서 1을 뺀다. 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들어야한다. 이 연산을 사용하는 횟수의 최솟값을 출력해라. 입력 조건 첫째 줄에 정수 X가 주어진다. (1 [Algorithm] Dynamic Programming (동적 계획법) 다이나믹 프로그래밍 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 어떤 문제에서는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다. 피보나치 수열 다이나믹 프로그래밍의 대표적인 예시인 피보나치 수열을 보자. 피보나치 수열은 이전 두항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열은 다음과 같은 형태로 끝없이 이어진다. 이를 점화식으로 나타냈을 때 알 수 있는 특징은 다음과 같다. f(n) = f(n - 1) + f(n.. 이전 1 다음
