Cara's Moving Cara's Moving

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]일 경우의 최대값을 저장하고, 두 번째 원..

Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/equal/problem?isFullScreen=true 문제의 제약 조건은 다음과 같이 두 가지가 있었다. - "한 명을 제외하고 초콜릿을 나눠줄 수 있다." - "결과적으로 배분한 초콜릿의 개수가 같아야 연산이 끝이 난다." 문제를 풀어나가는 아이데이션 과정부터 쉽지 않았다. 특히 첫번째 조건을 코드로 처리하는 데 있어서 어려움을 겪었다. 오직 딱 한 명을 제외하고 숫자를 더해서(1,2,5) 모든 Array의 숫자들을 동일하게 만드는 것이 어려웠다. 구글링을 통해 문제를 해결해 나갈 수 있었는데, 먼..

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)로 무게와 가치라는 원소를 가지고 있다...

변수 세 개를 받아서, 최대 수익을 구하는 함수 만들기 그 세 개의 변수란, 1) 판매 개수에 따른 매출에 대한 리스트. 즉, 리스트의 인덱스가 판매 개수이며 리스트의 실제값은 인덱스값만큼 판매하였을 때의 매출액에 해당한다. 2) 판매하고자 하는 제품의 개수 3) 특정 개수 별 최대 매출액이 저장되어 있는 딕셔너리 이 문제 또한 앞서 소개한 두 개의 전략처럼, Memoization과 Tabulation 각각의 전략으로 접근 가능하다. 먼저 #Memoization인 경우 다음과 같이 풀 수가 있다. def max_profit_cache(p_of_list, n, cache): #만약, 판매n의 개수가 0이거나 1인 경우에는 price_list에 있는 것을 #그대로 리턴하면 된다. 단, 이 값또한 cache에..

Dynamic programming을 위해서는 두 가지의 조건이 필요하다. 최적 부분 구조와 중복되는 부분 문제가 그 조건에 해당한다. - 조건 1) 먼저, 최적 부분 구조(optimal substructure)의 경우에는 부분 문제들의 최적을 답을 이용해서 원래 문제의 최적의 답을 구하는 방식이다. 특정 시점의 최적값을 구하기 위해서 바로 전 시점의 최적값들의 비교를 통해서 현 시점의 최적값을 구하는 경우를 생각해보자. 이전 시점의 최적값이 고정값인 경우도 있고(피보나치 수열의 경우) 혹은 여러 경우의 수에 따라서 값이 달라져 최적 부분 구조를 찾기 위해서 여러 조합을 후보로 생각해야 할 수도 있다. - 조건 2) 재귀 호출시 중복(overlapping recursive calls)일 경우, 재귀적 해..