콘텐츠로 건너뛰기
Home » dynamic programming

dynamic programming

오일러 프로젝트 82

(참고: 이 문제는 81번 문제의 좀 더 어려운 버전입니다)

아래와 같은 5×5 행렬이 있습니다. 맨 왼쪽 열의 아무곳에서나 출발하여 위/아래/오른쪽으로만 움직이면서 맨 오른쪽 열까지 갈 때, 빨갛게 표시된 경로의 합이 994로 가장 작습니다.

31kB 짜리 파일 matrix.txt에는 80×80 행렬의 정보가 들어있습니다. 위와 같은 방법으로 이 행렬의 맨 왼쪽 열에서 출발하여 오른쪽 열까지 갈 때, 경로 합의 최소값은 얼마입니까?

더 보기 »오일러 프로젝트 82

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

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

오일러 프로젝트 18

다음과 같이 삼각형 모양으로 수를 배열했습니다.

3
7 4
2 4 6
8 5 9 3

삼각형의 꼭대기부터 아래쪽으로 인접한 수를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23이 가장 큰 합을 갖는 경로가 됩니다.

다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

참고: 여기서는 경로가 16,384개 밖에 안되기 때문에 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다. 하지만 67번 문제에는 100층자리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.

https://euler.synap.co.kr/problem=18
더 보기 »오일러 프로젝트 18

오일러 프로젝트 14

우박수 양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다. n → n / 2 (n이 짝수일 때) n → 3 n + 1 (n이 홀수일 때) 13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다. 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다. (역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런… 더 보기 »오일러 프로젝트 14

동적계획법

동적 프로그래밍

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

오일러 프로젝트 31

영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)

이 동전들을 가지고 2파운드를 만드는 방법들은 다양할 것입니다. 예를 하나 들면 이렇습니다.

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

2파운드를 만드는 서로 다른 방법은 모두 몇 가지나 있습니까?

https://euler.synap.co.kr/problem=31
더 보기 »오일러 프로젝트 31