kakasoo

요즘 DP 문제만 주구장창 풀고 있는데, DP를 푸는 요령은 이렇다. 먼저 DP[n]이 의미하는 것이 무엇인지 찾는다. 이 문제에는 DP[n]의 정의는, n을 만들기 위해서 필요한 최소 제곱수 항이었다. DP[n]을 그러면 숫자들의 나열로 생각한다. ( 이 문제는 합이기 때문에 덧셈의 나열로 생각하면 된다. ) 거기서 마지막이 무엇인지 생각한다. 이 문제에서는 당연히, n의 제곱근이 될 것이다. 그렇다면 우리가 알 수 있는 게 생긴다. DP[n - 마지막 값의 제곱] + 1이 DP[n]이라는 점화식이다. const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process..

알고리즘에 대해 알고리즘을 배우기 전에 대부분의 사람들이 궁금한 것이, 수학적인 능력의 유무가 알고리즘을 배우는 데에 필수적인지 일 것이다. 나도 어렴풋이 그런 걸 느끼기도 했고, 경험해가며 굳이 필요없다는 것을 느꼈다. 인공지능을 한다거나, 아니면 그래픽스를 할 게 아니라면 필요없다는 것을 이해할 수 있었다. 비록 내가 인공지능이나 그래픽스를 해본 것은 아니지만, 수식을 쓰는가 안 쓰는가, 그런 도구적인 쓰임과 자신이 사용하는 공식들에 대한 이해 없이 그저 수학적 사고력만으로 풀 수 있는 문제들 선이 내게 필요한 cut line 이었기 때문이다. 그 이상으로 가려면 아직 시간도 많고, 필요할 때 배워도 문제 없겠다고 싶었다. (Q. 나는 하루에 8시간 정도 code를 짜고 있는데, 필요할 때 배워도 문..