오일러 프로젝트 18

오일러 프로젝트 18번 문제는 숫자 피라미드를 내려가면서 더했을 때 나올 수 있는 최대합을 계산하는 문제이다. 위에서 아래로 내려가면서 합을 구하고 경로별로 비교하는 전수검사 대신에 다른 방식으로의 접근이 요구된다.

동적계획법

동적 프로그래밍 동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다.

영국 동전의 액면가 조합 문제 관련 해설

오일러 프로젝트 31번 문제의 풀이는 해당 포스트에서 보면 허무하리만치 짧고 간단하며, 어찌보면 굉장히 이해하기 힘든 식으로 코드가 짜여져 있다. 게다가 재귀라든지 여러가지 그외 방법으로 푸는 것 보다 속도도 엄청 빠르다. (당연할 것이 재귀 호출 같은 것은 전혀 생각하지 않고 그저 정수 배열의 일부 항끼리 서로 더해나가는 2중 루프가 전부이다.) 이런 괴상한 풀이는 어떻게 나오게 되었으며,