dynamic programming 검색 결과

해당 글 28건

알고리즘 풀이 - 백준 14002(가장 긴 증가하는 부분 수열 4, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 LIS 관련 포스팅은 여기를 참조 유사한 문제인 11053번(가장 긴 증가하는 부분 수열) 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 문제의 내용을 보려면 아래 더보기 클릭 더보기 이 문제는 LIS의 길이 및 그 배열을 구하는 문제이다. 2. 풀이 이 문제는 이전 포스팅의 11053문제와 같은데 추가적으로 LIS의 배열 그 자체까지 출력하는 문제이다. 상단의 관련글 중 링크를 참조하자. DP문제이므로 간단히 문제의 정의, 기저 상태, 점화식을 알아보자. 정의 : 길이 N의 배열에서 LIS의 길이 및 배열 구하기 길이 N이라는 값 자체가 State이므로 배열의 길이에 따른 결과값만 저장하는 배열을 별도로 생성한다. DP의 ..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 11. 20:40

알고리즘 풀이 - 백준 11053(가장 긴 증가하는 부분 수열, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 LIS 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 문제의 내용을 보려면 아래 더보기 클릭 더보기 이 문제는 LIS의 길이를 구하는 문제이다. 2. 풀이 이 문제는 상단의 관련글에서 표기한 LIS 포스팅을 보는 것이 더 낫다. 간단히 이야기하여 순차적으로 저장된 데이터가 있는 배열의 부분 배열 중 증가하면서 가장 긴 부분 배열을 구하는 문제이다. 이 문제는 기본적으로 DP로 풀 수 있고, 그 보다 더 개선된 시간복잡도를 갖는 방식으로 풀어내는 것도 가능하다. 해당 내용 또한 상단의 LIS 포스팅에 있으니 참고하자. 간단히 문제의 정의, 기저 상태, 점화식을 알아보자. 정의 : 길이 N의 배열에서 LIS의 길이를 구하기..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 11. 16:49

알고리즘 풀이 - 백준 2193(이친수, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 문제의 내용을 보려면 아래 더보기 클릭 더보기 길이 N이 주어질 때, N 길이의 이친수의 개수를 구하는 프로그램 이친수란? 0으로 시작하지 않으며, 1이 연속으로 오지 않는 0, 1로만 이루어진 수. ex) 10010 ( O ), 1101 ( X ) 2. 풀이 이 문제는 DP로 풀 수 있다. 이전의 포스팅인 계단 수를 구하는 경우와 비슷하지만 이전의 수가 0 또는 1의 State로만 지정된 것이다. 여기서 State는 숫자의 길이인 N과 N-1번째 숫자가 0 또는 1 경우의 2가지이다. 2차원의 State를 저장하는 배열을 기반으로 각 부분이 의미하는 바는 아래와 같다. DP[N][0] = DP[N-..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 8. 20:03

알고리즘 풀이 - 백준 10844(쉬운 계단 수, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 문제의 내용을 보려면 아래 더보기 클릭 더보기 길이 N이 주어질 때, N 길이의 계단 수의 개수를 구하는 문제 2. 풀이 이 문제는 간단하게 DP로 풀 수 있다. 왜 그럴까? N이라는 숫자의 길이가 State로 주어질 때, 현재 N-1까지의 숫자가 123432....5 라고 가정하자. 그렇다면, 다음에 추가될 수 있는 것은 4 또는 6일 것이다. 즉, N-1번째 숫자의 State에 따라 다음에 올 숫자가 결정되는 것이다. 즉, N이라는 숫자의 길이와 N-1번째 숫자인 2개의 State를 갖고 반복 / 재귀를 통해 풀 수 있는 문제이다. 2차원의 State를 저장하는 배열을 기반으로 할 때, 각 부분이..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 8. 19:41

알고리즘 풀이 - 백준 15990(1, 2, 3 더하기 5, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 비슷한 문제인 9095번(1, 2, 3 더하기) 포스팅은 여기를 참조 1. 문제 문제 링크는 여기를 참조 문제의 내용을 보려면 아래 더보기 클릭 더보기 이 문제는 1, 2, 3을 더해 N을 만드는 것은 동일하나 연속된 숫자를 사용할 수 없다. 2. 풀이 이 문제는 비슷한 문제인 9095번과 마찬가지로 DP로 해결 가능하다. 하지만 이전에는 State를 나타내는 N의 값만 변수로써 동작시키도록 값을 저장하였지만 이번에는 가장 최근에 사용된 값이 1, 2, 3중 어느 것이었는지도 알아야 한다. 따라서, State를 저장하는 배열이 2차원으로 생성되어야 한다. 즉, DP[N][1], DP[N][2], DP[N][3]과 같이 N*3의 배열을 ..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 7. 19:31

알고리즘 풀이 - 백준 16194(카드 구매하기 2, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 비슷한 문제인 11052번(카드 구매하기) 포스팅은 여기를 참조 1. 문제 문제 링크는 여기를 참조 문제 내용을 보려면 아래 더보기 클릭 더보기 이번 문제는 16194번과 비슷한데 그 상태에서 최대값이 아닌 최소값을 구하는 방향으로 바뀐 것이다. 즉, 카드 N개 구매 시, 최소의 비용을 구하는 문제 2. 풀이 이 문제 또한 이전의 포스팅 문제와 같이 DP로 풀 수 있다. 카드 N개를 구해하는데, i번째 카드팩에는 i개의 카드가 있으며 i번째 카드팩의 가격을 P[i]라고 부르자. 이 때, N개의 카드를 원하는 경우 그 비용의 최소값이 DP[N]이라고 부르자. 그렇다면, N개의 카드를 구매하는 경우의 수는 다음과 같을 것이다. 1) P[N..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 7. 19:30

알고리즘 풀이 - 백준 11052(카드 구매하기, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 문제 내용을 보려면 아래 더보기 클릭 더보기 카드 N개 구매 시, 최대의 비용을 구하는 문제 2. 풀이 이 문제는 DP로 해결할 수 있다. 우선 문제를 이해해보자. 카드 N개를 구매하고자 하는데, i개의 카드가 들어있는 카드팩이 있고 i번째의 카드팩의 가격을 P[i]라고 부르자. 이 때, N개의 카드를 원하는 경우 그 비용의 최대값이 DP[N]이라고 부르자. 그렇다면, N개의 카드를 구매하는 경우의 수는 다음과 같을 것이다. 1) P[N] : N번째 카드팩만 구매하는 경우 2) DP[1] + P[N-1] : N-1번째 카드팩을 구매하고 1개의 카드팩을 사는 경우의 수 중 가장 최대의 비용인 경우 3)..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 7. 19:29

알고리즘 풀이 - 백준 9095(1,2,3 더하기, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 이 문제를 완전 탐색(재귀)를 이용하여 풀 수도 있다. 그 방법은 여기를 참조 2. 풀이 이 문제는 DP로 해결 가능하다. 우선 두 가지 조건이 만족하는지 알아보자. 각 정수는 n으로 표기하여 이 자체가 변수로 하나의 State를 나타낸다. 정수 n을 1, 2, 3의 합으로 나타내는 방법은 아래와 같다. n = (n-3) + 3 n = (n-2) + 2 n = (n-1) + 1 즉, 작은 문제들인 n-3, n-2, n-1을 반복하여 사용하고 해당 최적 결과값이 그대로 사용되므로 DP의 두 가지 조건인 Overlapping Subpro..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 6. 21:54