DP
-
[백준] [DP] 제곱수의 합Data miner/Algorithm & Data structure 2022. 11. 11. 15:07
문제 소스 링크 : https://www.acmicpc.net/problem/1699 문제 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N이 주어진다. (1 ≤..
-
[자료구조] [python] [Dynamic Programming] Sherlock and CostData miner/Algorithm & Data structure 2022. 2. 14. 13:24
Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/sherlock-and-cost/problem?isFullScreen=true - A Array의 앞에서부터 원소값을 결정한다고 하였을 때, A[i] - A[i-1]를 최대화 시키는 값을 가지는 A[i]의 경우의 수는 결국 A[i] =B[i] 이거나 A[i] = 1 이다. 이와 같은 성질을 이용하여, temp라는 임시 Array에 초기값이 (0, 0) 튜플을 원소로 가지는 배열을 만든다. 이 temp Array의 경우, 각 튜플의 첫번째 원소는 A[i]가 B[i]일 경우의 최대값을 저장하고, 두 번째 원..
-
[자료구조] [python] [Dynamic Programming] EqualData miner/Algorithm & Data structure 2022. 2. 12. 00:42
Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/equal/problem?isFullScreen=true 문제의 제약 조건은 다음과 같이 두 가지가 있었다. - "한 명을 제외하고 초콜릿을 나눠줄 수 있다." - "결과적으로 배분한 초콜릿의 개수가 같아야 연산이 끝이 난다." 문제를 풀어나가는 아이데이션 과정부터 쉽지 않았다. 특히 첫번째 조건을 코드로 처리하는 데 있어서 어려움을 겪었다. 오직 딱 한 명을 제외하고 숫자를 더해서(1,2,5) 모든 Array의 숫자들을 동일하게 만드는 것이 어려웠다. 구글링을 통해 문제를 해결해 나갈 수 있었는데, 먼..
-
[자료구조] [python] [Dynamic Programming] The Coin Change ProblemData miner/Algorithm & Data structure 2022. 2. 8. 20:15
Hackerrank의 Data structures 관한 문제 중에서 Algorithms에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true 문제를 푸는 아이디어를 떠올리는 것은 어렵지 않다. Coins 리스트에서 앞의 원소의 코인부터 시작해서 무제한으로 제공되는 코인을 통해 가능한 금액의 경우의 수를 구하고, 이후 인덱스의 코인들의 조합을 통해 가능한 금액을 업데이트 하는 식으로 구하면 된다. 하지만, 실제 이를 코드로 구현하는 과정에서 시간이 소요되었다. 실제 풀이한 코드 방법은 다음과 같다. 문제에서 주어진 우리가 만들어야 하는 금액이 n이고, Coins 리스트에..
-
[DP] [Algorithm] Fractional Knapsack AlgorithmData miner/Algorithm & Data structure 2020. 3. 26. 16:30
https://pongdangstory.tistory.com/487 이전 포스팅에서, Unfractional knapsack problem을 다루었다. 이번에는 가방에 물건을 담을 때, 물건의 일부를 담는 경우는 어떠할까? 믹서기 같은 물건의 경우, 믹서기를 쪼개면 그 기능을 다하지 못하기 때문에 쪼갤 수 없는 반면에, 초콜릿이라고 한다면, 초콜릿은 소분해서 담을 수 있고 그 가치도 그 소분한 가치만큼에 해당하기 때문에 쪼갤 수 있다. 이 경우 그리디 알고리즘의 접근법으로 비교적 간단히 풀 수 있다. 이전의 input과 동일하게 문제가 주어졌다고 가정하자. K는 가방에 담을 수 있는 최대 무게 상한선이다. 즉, 물건이든, 물건의 부분이든 이 K kg의 무게를 넘을 수 없다. stuff_array는 다음과..
-
[DP][Algorithm] Knapsack Algorithm. 백준 12865 평범한 가방Data miner/Algorithm & Data structure 2020. 3. 26. 15:53
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 냅색알고리즘이라고 불리는 이 유명한 문제는 다음과 같다. 가방에 가치를 극대화하도록 물건들을 담아야 한다. 이 때 가방은 특정 무게 이상을 담을 수 없다. 제한된 K kg의 이하의 물건들을 담을 수 있다. 물건들은 (Weight, Value)로 무게와 가치라는 원소를 가지고 있다...
-
[DP] [DFS] 백준 1520 내리막길 +aData miner/Algorithm & Data structure 2020. 3. 21. 15:49
문제 출처; https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 위의 그림에서 왼쪽 끝에서부터 오른쪽 아래까지 지나갈 수 있는 경로 수에 대해서 구해야 한다. 단, 움직일 때 원래 위치한..