오늘 알고리즘 문제를 몇가지 풀어 보았다.
많은 경우의 다이나믹 프로그램밍을 이용한 알고리즘은 간단한 형식으로 구현이 가능하다.
하지만 아이디어를 떠올리는게 쉽지 않았다.
목표한 금액이 되는 화폐 선택의 가지 수를 산출하는 (100 = 20x2 + 10x6 or 20x3 +10x2 ...) 알고리즘
점화식을 만드는 것까지가 엄청나게 힘들었다.
대부분의 Dynamic programing은 점화식통해 표현이 가능하니,
점화식이 가능한지 살펴보는게 중요하다.
순열은 흔히 몇가지를 선택하는 경우에 문제에서 고르게 된다.
순열이나 조합문제는 조금 더 풀어봐야 확실하게 어떤 유형의 문제가 순열과 조합을 사용하면 좋을지 눈에 들어올 것 같다.
멱집합은 많은 경우는 흔한 문제는 아니었다.
예를 들어
상의, 하의, 신발, 모자를 선택해서 입을 수 있는 문제가 있다. (프로그래머스)
모두 선택하지 않아도 되는 경우를 포함한다면 생각해볼만 한 풀이 방법이다.