정수 배열의 최대 부분합 (연습문제)

배열의 연속된 부분집합의 최대합 정수 배열이 주어질 때 배열내의 연속된 원소를 더한 부분합의 최대값을 구하는 문제이다. 구간이 아닌 최대값 자체를 구하면 되는 문제이다. 간단히 생각하면 0부터 1, 2, 3 … n 까지의 합 중 최대인 값, 그 다음은 1부터 2, 3, 4 .. n 까지의 값 중 최대인값 이렇게 비교해나갈 수 있는데 그러면 반복계산이 너무

오일러 프로젝트 18

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

오일러 프로젝트 14

오일러 프로젝트 14 번 문제는 우박수에 관한 내용이다. 이 문제는 간단한 재귀함수와 메모이제이션을 통한 최적화 문제인데, 범위가 1~1백만으로 제법 크기 때문에 조금 더 깊은 고민이 필요하다. 또한 Swift에서는 단순한 메모이제이션 함수를 쓰는 경우, 재귀함수에서는 파이썬처럼 동작하지 못하기 때문에 특별한 형태의 메모이제이션 함수가 필요하다. 재귀함수를 위한 메모이제이션 함수를 어떻게 작성하는지에 대해서도 알아볼 것이다. 양의 정수 n에

동적계획법

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

오일러 프로젝트 31 – 영국 동전의 액면가 조합 문제 관련 해설

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