ComDoc ComDoc

https://school.programmers.co.kr/learn/courses/30/lessons/1843 DP 대신 재귀와 lru_cache로 풀 수 있을 때도 있다~! from functools import lru_cache def solution(arr): @lru_cache(maxsize=None) def solve(t): if len(t) == 1: return [int(t[0])] result = [n1 + (n2 if t[i] == "+" else -n2) for i in range(1, len(t), 2) for n1 in solve(t[:i]) for n2 in solve(t[(i + 1):])] return [max(result), min(result)] return max(sol..

최근 7일 통계 중에 배낭 문제가 1위길래... 옛 글을 다시 읽어보니... 동전 거스름돈을 언급만 하고... 풀지 않았더군요. https://comdoc.tistory.com/entry/35-%EB%B0%B0%EB%82%AD%EB%AC%B8%EC%A0%9CKnapsack-problem-%ED%8C%8C%EC%9D%B4%EC%8D%AC 그리디는 간단해서 원문에 추가했습니다만... 그 외는 내용이 많아서 새 포스트로 올려봅니다. 1. 그리디 알고리듬(탐욕법) 우리나라 동전은 500, 100, 50, 10, 5, 1원이 있습니다. 이 상황에서는 그리디 알고리듬으로 문제를 풀 수 있습니다. 각 단계에서 최선의 값을 구하는 것이 전체적으로도 맞는 답이 됩니다. * 간략한 코드를 위해 동전은 크기가 큰 순서대로 ..