Dynamic Programming 검색 결과
4 개의 검색 결과가 있습니다.
프로그래밍/알고리즘(Algorithm)

[알고리즘][Java] 동적 계획법(Dynamic Programming)

[알고리즘] 동적 계획법(Dynamic Programming) □ 1. 개 요 동적 계획법(Dynamic Programming, 이하 DP)은 알고리즘 보다는 하나의 문제해결 페러다임으로서 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 기본적인 아이디어에서 출발한다. 특히 큰 문제를 동일한 작은 문제들이 여러 번 반복되는 경우에 그 답을 저장해두고 재활용하게 되며, 혹자는 '기억하며 풀기' 라고 부른다. 이름의 기원은 Richard Bellman이 1950년대에 사용한 단어로 현재까지 이어져 온 것으로 특별한 의미는 없다. □ 2. DP를 사용하는 이유 DP는 일반적인 재귀 방식(Naive Recursion) 방식과 뿌리는 같으나 일반 재귀에서의..

2023. 7. 11. 12:56
Programming Problem/동적 계획법(Dynamic Programming)

[Java] 백준 11726번 2×n 타일링 (DP)

[Java] 백준 11726번 2×n 타일링 (DP) □ 문 제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. ○ 입 력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) ○ 출 력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. [문제 링크] 백준 11726번 2×n 타일링 □ 문제풀이 n이 1, 2, 3, 4, 5일 때를 직접 그려보면 아래의 규칙을 가짐을 알 수 있다. dp[n] = dp[n - 1] + dp[n - 2] 결과론적으로 2 X n 크기의 직사각형을 채울 수 있는 경우의 수는 2 X (n - 1)일 때 그릴 수 있는 ..

2023. 6. 18. 15:19
Programming Problem/동적 계획법(Dynamic Programming)

[Java] 백준 1463번 1로 만들기 (DP)

[Java] 백준 1463번 1로 만들기 (DP) * 학습 목적의 게시물이나 혹시 이 게시물이 문제가 된다면 언제든 연락 부탁드립니다. * 더 나은 풀이를 위한 훈수, 조언 등 모두 환영합니다! □ 문 제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. ○ 입 력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. ○ 출 력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. [문제 링크] 백준 1463번 1로 만들기 □ 문제풀이 주어진 세 가지 연산으로 확인해야 할 조건은 아래 4가지 이다. 정수 X가 6으로 나누어 떨어질 경우 정수 X 연산 횟수의 최솟값은 X /..

2023. 6. 17. 21:29
Programming Problem/동적 계획법(Dynamic Programming)

[Java] 백준 1003번 피보나치 함수(DP, Top-Down, Bottom-Up)

[Java] 백준 1003번 피보나치 함수(DP, Top-Down, Bottom-Up) * 학습 목적의 게시물이나 혹시 이 게시물이 문제가 된다면 언제든 연락 부탁드립니다. * 더 나은 풀이를 위한 훈수, 조언 등 모두 환영합니다! 문 제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1..

2023. 6. 17. 19:44