반응형 dp43 [Python][이코테] 개미 전사 / DP 문제 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. {1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을.. 2022. 10. 25. [Python][이코테] 1로 만들기 / DP 문제 설명 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지이다. x가 5로 나누어 떨어지면, 5로 나눈다. x가 3으로 나누어 떨어지면, 3으로 나눈다. x가 2로 나누어 떨어지면, 2로 나눈다. x에서 1을 뺀다. 정수 x가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하시오. 예를 들어 정수가 26이면 26 - 1 = 25 25 / 5 = 5 5 / 5 = 1 입력 조건 첫째 줄에 정수 x가 주어진다. (1 ≤ x ≤ 30,000) 출력 조건 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 입력 예시 26 출력 예시 3 솔직히 어떻게 풀어야 할지 감도 안 잡혀서 걍 풀이를 보고 풀이를 보고도 뭐지.. 싶어서 하나하나 돌.. 2022. 10. 23. [Python][이코테] 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 Dynamic Programming 모든 프로그램은 컴퓨터의 연산 속도와 한정된 메모리 공간에 제한되어 있다. 다이나믹 프로그래밍은 이러한 제한 속에서 우리는 주어진 요소들을 최대한으로 활용하는 효율적인 알고리즘을 작성해야 한다. 다이나믹 프로그래밍은 동적 프로그래밍, 동적 계획법 이라고도 한다. 피보나치 수열 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제로 피보나치 수열이 있다. 피보나치 수열을 우리가 학창 시절 배운 점화식을 이용해 풀어보면 HTML 삽입 미리보기할 수 없는 소스 피보나치는 첫 번째 항과 두 번째 항이 1이기 때문에 위와 같이 정의된다. 즉 n번째 피보나치 수 = (n - 1)번째 수 + (n - 2)번째 수 단, 1번째와 2번째 수는 1 이를 코드로 구현하.. 2022. 10. 22. 이전 1 ··· 8 9 10 11 다음 반응형
