문제설명입력 & 출력나의 풀이이번 "백준 - 1로 만들기" 문제는 동적 계획법(DP)을 활용하여 해결할 수 있는 문제입니다. [Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기동적 계획법 DP란❓ 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다. 주로 줄여서 DP라고 많이 말하며, 주pixx.tistory.com 이 문제는 주어진 수 n을 1로 만들기 위해 최소 몇 번의 연산이 필요한지를 구하는 문제로, 가능한 연산은 다음과 같습니다n이 3으로 나누어 떨어지면 3으로 나눈다. n이 2로 나누어 떨어지면 2로 나눈다. n에서 1을 뺀다.위 연산을 생각해본다면 결국 3가지의 ..
동적 계획법
문제설명입력 & 출력나의 풀이이번 "백준 - 돌 게임"문제는 2명의 플레이어(상근,창영)가 돌을 1개 또는 3개 가져갈 때 마지막 돌을 가져가는 사람이 승자하는 게임입니다. 규칙을 정리하자면 다음과 같습니다.돌이 N개 있다.상근이와 창영이가 번갈아 가며 돌을 가져간다.각 턴에 1개 또는 3개를 가져갈 수 있다.마지막 돌을 가져가는 사람이 승리한다.상근이가 먼저 시작한다.이번 문제는 동적 계획법 (Dynamic Programming)알고리즘을 사용하여 풀 수 있습니다. [Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기동적 계획법 DP란❓ 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 ..
동적 계획법 DP란❓ 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다. 주로 줄여서 DP라고 많이 말하며, 주어진 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 동일한 문제가 나왔을 시 저장해둔 결과를 재사용함으로써 전체 문제를 효율적으로 해결하는 기법입니다. 위 말을 기준으로 핵심을 뽑아보자면 다음과 같습니다.하나의 큰 문제를 여러 개의 작은 문제로 나누어 결과 저장동일 결과 재사용 DP 문제 성립 조건동적 계획법(DP)는 두 가지 주요 원리인 "최적 구분 구조"와 "중복되는 하위 문제"를 기반으로 합니다. 최적 부분 구조(Optimal Substructure)문제의 최적 해가 하위 문제의 최적 해로 구성되는 ..
