암기가 없으면 알고리즘 문제들 푸는게 정말 어려워짐. 


너가 역사의 남을 정도의 수학적 직관 + 코딩 능력을 가진게 아니면 저걸 보고 바로 풀 수 있는 방법은 없다. 예를 하나들면 


리트코드 소위 perfect square 를 찾는 문제 (아래 링크 첨부)

https://leetcode.com/problems/perfect-squares/


Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.


위 문제의 일반적인 정답은 four square theorem 을 이용하면 4임.

https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem


다만 수가 중복되는 케이스가 존재하기 때문에 위의 문제의 답이 무조건 4는 아님.


여기에 Legrendre's three square theorem 적용하면 만약 수가 4^a (8*b + 7) 꼴로 나타나면 4개 정수의 square로 그렇지 않으면 3개의 정수의 square로 표현할 수 있음 .

https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem


만약 주어진 수가 단 하나의 square로 표현한 경우는 초등학교 수학을 배웠으면 자명하게 찾아낼 수 있을 거임


고로 1, 3, 4개의 정수의 square로 표현되는 경우는 O(1) 임.


다만 2개의 정수로 표현하는 경우는 만약, 주어진 수가 소수라면 모를까, 내가 알기로 일반적으로 알아내는 방법은 없고, 단지 Landau-Ramanujan constant를 통해서 밀도만 찾아낼 수 있음. https://en.wikipedia.org/wiki/Landau%E2%80%93Ramanujan_constant


이 경우 직접 root(n)개의 정수를 직접 비교해 봐야하니까, O(root(n)) 임.


정리해보면 위의 문제의 솔루션은 최상의 경우 O(1) 최악의 경우 O(root(n)) 임.


물론 대회에서는 라마누잔급 수학적 직관을 가진 사람이 아닌 이상 이걸 아무런 사전지식 없이 찾아낼 수 있을거라고는 생각안함.


고로 이걸 공부해야하는데... 그리고 pi구하는 방법 등등 이런 류 문제들이 꽤 있음.