자료구조&알고리즘3 0-1 Knapsack Problem 0-1 Knapsack Problem 다이나믹 프로그래밍의 대표적인 문제라 할 수 있는 문제입니다. 무게 제한이 있는 배낭에 가치가 최대가 되도록 짐을 넣는 문제인데, 넣을 수 있는 짐을 쪼갤 수 있느냐 없느냐에 따라 ① 분할가능 배낭문제(Fractional Knapsack) ② 0-1 배낭문제(0-1 Knapsack problem) 으로 나눠집니다. 분할가능 배낭문제는 Greedy 알고리즘을 활용하여 최적으로 풀이가 가능하지만 분할이 불가능한 0-1 배낭문제는 모든 경우의 수를 봐야합니다. 0-1 배낭문제를 최적화 하기 위해 다이나믹 프로그래밍, Tabulation이 활용됩니다. 0-1 배낭문제에 (가치, 무게) 형태의 Tuple 이 저장된 리스트가 Input으로 들어온다고 하면, 아래와 같은 테이블을.. 2020. 10. 4. Fibonacci Number Fibonacci Number Fibonacci Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 다이나믹 프로그래밍(Dynamic Programming, 이하 DP)을 이해하는데 기본이 되는 문제입니다. DP 는 중복된 하위 문제들(Optimal Substructure)의 결과를 저장해뒀다가 풀이에 활용하는 방식으로 문제를 하위 문제들로 분할하여 풀이한다는 점에서 분할정복, 그리디 알고리즘과 공통점이 있지만, 탐욕 선택 방식의 유무에 따라 그리디 .. 2020. 10. 4. Different Ways to Add Parentheses [분할 정복] Different Ways to Add Parentheses Different Ways to Add Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 숫자와 연산자를 문자열로 입력받아 가능한 모든 조합의 결과를 출력하는 문제로 괄호를 어디에 추가하느냐에 따라 다양한 조합과 결과가 가능합니다. 연산자를 만났을 때 Left, Right를 구분하는 분할을 수행하고 연산의 결과를 결합하여최종 결과를 내는 방식으로 풀이하면 됩니다. S.. 2020. 10. 4. 이전 1 다음