dynamic programming 검색 결과

해당 글 28건

알고리즘 풀이 - 백준 11727(2xN 타일링2, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 비슷한 문제인 11726번(2xN 타일링)은 여기를 참조 1. 문제 문제 링크는 여기를 참조 이번 문제는 11726번과 비슷한데 거기에 타일이 하나 추가되었다. 2xn의 타일을 2x1, 2x2, 1x2의 타일로 채울 수 있는 경우의 수를 구하는 문제이다. 2. 풀이 이 문제는 DP로 풀어낼 수 있다. 이전 11726번과 같으나 2*2가 추가되어 n의 상태를 증가시켜 가며 채운다는 것만 변한 것이다. 따라서 2*n을 채우려면 다음과 같은 3가지 경우의 수가 있을 것이다. ⅰ. 2*(n-1)에서 2*1로 세로로 하나 채우는 경우 ⅱ. 2*(n-2)에서 1*2로 가로로 두개 채우는 경우 ⅲ. 2*(n-2)에서 2*2로 하나 채우는 경우 따라..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 6. 19:29

알고리즘 풀이 - 백준 11726(2xN 타일링, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 문제 문제 링크는 여기를 참조 이 문제는 2x1 또는 1x2 타일로 2xn타일을 채우는 문제이다. 2. 풀이 이 문제는 2*n타일로 채운다는 것을 통해 좋은 힌트를 얻을 수 있다. 세로 길이가 2로 정해져 있기 때문에 세로를 채우려면 가로로 2개를 넣거나 세로로 1개를 넣으면 된다. 이 때, 가로로 2개를 채워서 넣게 되면 2*2만큼이 채워지게 되고 세로로 한 개를 채워 넣으면 2*1개가 채워진다. 여기서 DP로 풀 수 있다는 것을 알 수 있는데, 만약 2*n을 채울 수 있는 방법에서 n은 하나의 state가 되는 변수이고 더 작은 n만큼의 타일을 채운 것에서 규칙을 부여할 수 있다는 것을 알 수 있다. 위에서 적었듯이 세로를 채..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 6. 10:39

알고리즘 풀이 - 백준 1463(1로 만들기, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 문제 문제 링크는 여기를 참조 간단하게 설명하여 1 ~ 1,000,000 까지 숫자 중 하나를 입력 받아 해당 숫자에서 1을 빼거나, 2 또는 3으로 나누는 작업을 반복하여 1이 되게 하려면 몇 번의 연산이 필요한지 구하는 문제이다. 2. 풀이 우선 이 문제는 DP로 풀 수 있다. DP로 풀 수 있는지 어떻게 알 수 있을까? DP인지 아닌지 확인하려면 우선 2가지 조건이 만족되는지를 알아야 한다. 그 조건은 다음과 같다. 1) Overlapping Subproblems(겹치는 부분 문제) 2) Optimal Substructure(최적 부분 구조) 예를 들어, 숫자 5를 1로 만들기 위해서는 아래와 같은 방법이 있을 것이다. 5 ..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 5. 20:53

알고리즘 - Dynamic Programming(동적 계획법)

1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 그래서 혹자는 DP가 아닌 '기억하며 풀기'라고 부르기도 한다. 2. DP를 쓰는 이유 왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 ..
자바 프로그래밍/알고리즘(Algorithm) 2021. 1. 5. 15:08