dynamic programming 검색 결과

해당 글 28건

알고리즘 풀이 - 백준 9465(스티커, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 2*n으로 배치된 스티커가 각각 점수가 부여되어 있을 때, 점수합이 최대가 되도록 스티커를 떼는 경우를 찾는 문제이다. 2. 풀이 문제의 예시로 든 스티커를 한 번 그림으로 아래와 같이 살펴보자. 스티커를 뜯게 되면 인접한 다른 스티커도 뜯기고 해당 점수는 Count되지 않게 된다. 그래서 뜯는 경우가 한정되어 있다. 이 문제는 직관적으로 DP로 풀 수 있을 것으로 보인다. 왜냐하면, 좌측에서부터 스티커를 뜯어나간다는 가정을 해볼 때, 다음 스티커를 찢는 경우가 이전의 경우에 영향을 받게 되기 때문이다. 실제로, 만약 위 스티커의 배치를 행열로 본다면 2행 5열이라고 볼 수 있을 ..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 14. 21:04

알고리즘 풀이 - 백준 11057(오르막 수, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 N 자리의 숫자가 주어졌을 때, 오르막 수의 개수를 구하는 문제이다. ※ 오르막 수란? 오름차순으로 숫자가 이루어진 경우를 의미한다. 예를 들어 112334는 오르막수 이지만 1121은 아니다. 즉, N의 자리에서 1의 자리로 이동하며 숫자가 점점 커지거나 이전의 숫자와 같은 경우에만 해당한다. 숫자가 0으로 시작할 수도 있다! 2. 풀이 N자리의 숫자가 있고 좌측부터 1번째, 1번째 ~, N번째의 자리수라고 생각해보자.(N자리 이므로 index 기준) N자리의 숫자에서 1~N까지 1번째를 제외한 자리수에서 모두 이전 위치의 숫자에 영향을 받게 된다. 예를 들어 N = 3이라고 한..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 14. 13:19

알고리즘 풀이 - 백준 1309(동물원, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 더보기 이 문제는 2*N의 우리에 사자를 배치하는 경우의 수를 찾는 문제이다. 2. 풀이 2*N칸의 우리가 주어지는데 한 마리도 배치하지 않는 경우 또한 1가지의 경우로 쳐야 한다. N번째 위치에 사자를 배치한다면, 3가지의 경우가 있을 수 있다. ① N번째에 배치하지 않는 경우 ② N번째에 좌측에만 배치하는 경우 ③ N번째에 우측에만 배치하는 경우 ①인 경우에는 N-1번째에 배치하지 않거나, 좌측에 하나 배치하거나, 우측에 하나 배치하는 경우가 있을 것이다. ②인 경우에는 N-1번째에 배치하지 않거나, 우측에 하나 배치하는 경우가 있을 것이다. ③인 경우에는 N-1번째에 배치하지 않거나, 좌측에 하..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 13. 23:05

알고리즘 풀이 - 백준 1149(RGB 거리, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 더보기 이 문제는 N개의 집이 1열로 위치할 때, 인접한 집과 색이 같지 않도록 빨강, 초록, 파랑으로 칠하는 경우의 수 중 그 비용이 가장 작은 것을 구하는 문제이다. 2. 풀이 이 문제는 간단하게 DP로 해결이 가능하다. 인접한 위치의 집과 색상이 다르면 되기 때문에 이전 위치와 동일한 색상으로 칠하지 않는 색 중 가장 최소 비용인 것을 구해나가면 되기 때문이다. 이 문제에서 State는 N개의 집 중 몇 번째에 위치했느냐, 어떤 색으로 칠해졌느냐의 2가지이다. 색은 3개이므로, 0, 1, 2라고 표현하자. 그러면 State를 저장하는 배열은 DP[][]로 지정할 수 있다. 크기는 N * 3으로 ..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 13. 19:39

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

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 관련 문제인 9095번(1, 2, 3 더하기) 포스팅은 여기를 참조 관련 문제인 15990번(1, 2, 3 더하기 5) 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 더보기 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 2. 풀이 이 문제는 상단에 표기한 9095번과 같은데 정수 n의 범위가 넓어졌고 그 결과를 특정 수로 나누어야 한다는 것에 차이가 있다. 간단하게 푸는 방법은 9095와 같으니 다시 한 번 아래와 같이 참고하자. 정수 n을 1, 2, 3의 합으로 나타내는 방법은 아래와 같다. n = (n-3) + 3 n = (n-2) + 2 n = (n-1) + 1 즉, 작은 문제들인 n-3, n-2,..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 13. 13:06

알고리즘 풀이 - 백준 2225(합분해, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 문제의 내용을 보려면 아래 더보기 클릭 더보기 이 문제는 N, K가 주어질 때, N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다. 2. 풀이 0~N까지의 숫자가 K개 주어진다. 그렇다면 N=5, K=3이라고 한다면 0~5까지의 숫자가 3개 주어지고 3개의 합이 5가 된다는 의미이다. 이를 구하려면 어떻게 해야 할까? 만약 마지막에 더할 숫자를 M이라고 가정해보자. 그렇다면 아래와 같을 것이다. ? + ? + M = 5 그렇다면, M이 만약 0이라면 이전 까지의 합이 5이고, 1이면 4, 2이면 3. 3이면 2, 4이면 1, 5이면 0이라는 의미이다. 즉 이를 식으로 쓰면 ..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 12. 21:42

알고리즘 풀이 - 백준 1699(제곱수의 합, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 문제의 내용을 보려면 아래 더보기 클릭 더보기 이 문제는 특정 수 N을 제곱수들의 합으로 표현 시, 최소항의 개수를 구하는 문제이다. 2. 풀이 문제를 이해하기 위해 간단히 예시를 들어보자. N=8일 때, 제곱수들로 나타낼 수 있는 경우의 수는 몇 가지일까? 다음과 같다. $ 8=1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 $ $ 8=2^2 + 1^2 + 1^2 + 1^2 + 1^2 $ $ 8=2^2 + 2^2 $ 이 문제는 위와 같이 여러 가지 경우의 수에 따라 숫자를 나타낼 수 있을 때, 그 항의 수를 최소로 나타내는 경우를 찾아야 한다. 위의 예시는 2가 될..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 12. 19:42

알고리즘 풀이 - 백준 1912(연속합, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 문제의 내용을 보려면 아래 더보기 클릭 더보기 이 문제는 배열의 연속합 중 가장 큰 값을 구하는 문제이다. 2. 풀이 이 문제는 간단하게 DP로 풀어낼 수 있다. 우선 문제를 이해하자. 배열 내에서 단순히 값을 몇 개 뽑아서 더하는 것이 아니라 연속합 중 최대의 경우를 구해야 한다. 연속합은 1개만 있어도 연속합이 될 수 있다. 아래와 같은 배열이 있을 때를 예시로 조금만 알아보자. arr[i]는 원 배열이고, sum[i]는 연속합이 최대가 되는 경우의 배열이다. 인덱스 i 0 1 2 3 arr[i] 10 -12 30 -8 sum[i] 10 -2 30 22 sum[i]을 보며 왜 저렇게 되었는지 알아..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 12. 12:33