다이나믹프로그래밍4 [Algorithm] 이코테 개미 전사 | 파이썬 (DP, Dynamic Programming) [문제]개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.{1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 .. 2024. 7. 3. [Algorithm] 백준 1463, 이코테 1로 만들기 | 파이썬 (DP, Dynamic Programming) ※ 1463 1로 만들기https://www.acmicpc.net/problem/1463[문제]정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. ⓐ X가 5로 나누어 떨어지면 5로 나눈다.ⓑ X가 3으로 나누어 떨어지면 3으로 나눈다.ⓒ X가 2로 나누어 떨어지면 2로 나눈다.ⓓ X에서 1을 뺀다. 정수가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 1. 26 - 1 = 25 ( ⓓ)2. 25 / 5 = 5 ( ⓐ)3. 5 / 5 = 1 ( ⓐ) [입력 조건]첫째 줄에 정수 X가 주어진다.(1 [출력 조건]첫째 줄에 연산을 하는 횟수의 .. 2024. 7. 3. [Algorithm] DP(Dynamic Programming, 동적 계획법) 동적 계획법(DP)란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 특정 범위까지의 값을 구하기 위해 이전 범위의 값을 활용하여 효율적으로 값을 얻는 기법이다. 이전 범위의 값을 저장(Memoization)함으로써 시간적, 공간적 효율 얻는다. 동적 계획법(DP)의 적용주어진 문제를 부분 문제로 나누었을 때, 부분 문제의 답을 통해 주어진 문제의 답을 도출할 수 있을 때부분 문제의 답을 여러 번 구해야 할 때즉, 한 번 계산한 값을 다시 사용해야 할 때Memorization이전에 구해둔 값을 저장해서 중복 계산을 방지이전 범위의 답을 구하면, 바로 배열에 저장해 놓자!시간과 공간면에서 모두 효율적!방법탑다운(하향식) 방식 : 큰 문제를 해결하기 위해 작은 문제 호출보텀업(상향식) .. 2024. 1. 5. [Algorithm] DP 백준 11057 오르막 수 | C++ ※ 11057 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 해결 TIP 수의 길이가 N일 때의 오르막 수의 개수를 한 번에 구하지 말고 이전에 구한 값을 활용해보자. 숫자의 길이와 일의 자리 수를 기준으로 오르막 수의 개수를 계속 저장하고, 활용하자. -> DP 알고리즘 문제 해결 풀이 dp[i][j] = 수의 길이가 i이고, 일의 자리 수가 j인 오르막 수의 개수 = (j보다 작은 수 o.. 2022. 9. 9. 이전 1 다음
