알고리즘 문제 풀이(2)

1번

정수 4는 1, 2, 3의 합으로 표현할 때 아래와 같이 7가지의 방법이 있다. 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 자연수 N을 입력 받아, N을 1, 2, 3의 합으로 표현할 때에, 몇 가지 방법이 있는지 계 산하여 출력하는 프로그램을 작성하시오.

 

입력

입력은 표준입력(standard input; 키보드를 통한 입력)을 사용한다. 입력은 첫 줄에 자 연수 N이 하나 주어진다. 이 때, N은 1 이상 100000 이하의 범위이다.

출력

출력은 표준출력(standard output; 모니터 화면에 출력)을 사용한다. 주어진 자연수 N 을 1, 2, 3의 합으로 표현할 때에 가능한 방법의 수를 정수 형태로 출력한다.

입력 예	출력 예
1	1
4	7
10	274
15	5768

 

일단 입력을 몇 개 나열해서 규칙(점화식)을 찾아보자

입력	출력
1	1(1)
2	2(1+1, 2)
3	4(1+1+1, 2+1, 1+2, 3)
4	7 = 4(1+1+1+1, 2+1+1, 1+2+1, 3+1) + 2(1+1+2, 2+2) +1(1+3)
5	13 = 7(4인경우 +1) + 4(3인경우 +2) + 2(2인경우 +3)
6	24 = 13(5인경우 +1) + 7(4인경우 +2) + 4(3인경우 +3)
7	44 = 24(6인경우 +1) + 13(5인경우 +2) + 7(4인경우 +3)

입력 값이 4 이상부터는T(n) = T(n-1) + T(n-2) + T(n-3) 점화식을 가진다

시간복잡도 O(n)

 

 

2번

N * N개의 칸이 있는 테이블이 있고, 치즈 몇 개가 테이블에 놓여있다. 치즈를 좋아하 는 생쥐 미키는 테이블의 (1,1)에서 출발해서 (N,N)에 도착할 때까지 많은 치즈를 먹고 싶어한다. 하지만 머리가 나쁜 미키는 위로 올라가거나 오른쪽으로만 이동할 수 있다. 예를 들어, 아래 그림에서 미키는 5개의 치즈 중 최대 3개의 치즈만 먹으며 이동할 수 있다.

테이블 크기 N과 M개의 치즈 위치가 주어졌을 때 최대로 먹을 수 있는 치즈의 개수 를 구하는 프로그램을 작성하시오. 치즈의 위치는 (x,y)의 좌표로 주어지며 왼쪽 아래 구석의 위치를 (1,1)로, 맨 오른쪽 위 구석의 위치를 (N,N)으로 한다.

 

입력

입력은 표준입력(standard input; 키보드를 통한 입력)을 사용한다. 입력은 첫 줄에 자 연수 N과 M이 주어진다. 이 때, N과 M은 1 이상 10000 이하의 범위이다. 다음 M개의 줄에 각각의 치즈의 위치 x와 y가 주어진다.

출력

출력은 표준출력(standard output; 모니터 화면에 출력)을 사용한다. 주어진 입력에 대 해 최대로 먹을 수 있는 치즈의 개수를 정수 형태로 출력한다.

 

이 문제는 최소경로 알고리즘을 DP로 풀 떄 치즈의 개수만 더하는 기능을 추가한다는 느낌으로 풀면 된다.

어차피 최종 목적지에서 왼쪽(N-1)과 아래(M-1)의 경우만 알면 결과를 알 수 있기 때문에 부분 문제를 recursion하면 된다.

위 그림을 예시로 들면

5	0	1	1	3	3
4	0	1	1	2	2
3	0	1	1	2	2
2	0	0	1	1	2
1	0	0	0	0	0
M/N	1	2	3	4	5

각 숫자는 미키가 해당 칸까지 갔을 때 먹을 수 있는 치즈의 최대 개수이다.

C(x,y)는 (x,y)에 치즈가 있으면 1, 없으면 0의 값을 가지는 함수

D(x,y)는 (1.1)에서 출발하여 (x,y)까지 갈 때 미키가 먹을 수 있는 치즈의 최대 개수를 나타내는 함수

D(N, N)을 구하는게 목표이기 때문에 다음과 같은 점화식으로 DP 프로그래밍을 작성하면 된다.

D(x,y) = D(x-1, y) + D(x, y-1) + C(x,y)

           = 0 (x=0 or y=0)

알고리즘

D[0..N, 0..N] 2차배열 선언 및 초기화

for i=0 to N
	D[0,i] = 0
    D[i,0] = 0
for x=1 to N
	for y=1 to N
    	D[x,y] = D[x-1,y] + D[x,y-1] + C(x,y)
return D[N,N]

 

 

3번

Nadiria 라는 (상상의) 나라에서는 다음과 같은 액면가의 동전(화폐)을 사용한다고 한다. $1, $4, $7, $13, $28, $52, $91, $365 어떤 곳이든 사람들은 돈을 주고 받을 때, 가능한 적은 개수의 동전을 사용하기를 원한다. 입력으로 자연수 K 가 주어지면 Nadiria 화폐를 이용하여 $K 를 만들 수 있는 최소 동전 개수를 출력하는 알고리즘을 설계하고 분석하시오.

 

1, 4, 7, 13, 28, 52, 91, 365

예를 들어 K=10 일 때 1,1,1,7인 경우가 최소일 때 여기서 1을 빼면 K=9일 때의 최소와 같을 것이다 .최소가 아니라면 K=10일 때도 1,1,1,7이 최소가 아닐 것이다. 이걸 DP 개념으로 보면 이전 값들의 결과에서 더하는 경우를 고려하면 table의 이전 값으로 해결할 수 있을 것이다.

M(K) = min(M(K-c) | c={ 1, 4, 7, 13, 28, 52, 91, 365} and c<=K} + 1

 

 

 

4번

길이가 n 인 정수의 배열 A[0..n-1]가 있다. A[a] + A[a+1] + … + A[b]의 값을 최대화하는 구간 (a, b)를 O(n) 시간 안에 찾는 방법을 설계하고 분석하라. 예를 들어, 배열 A가 아래와 같이 주어졌을 경우 (n = 10), 31 -41 59 26 -53 58 97 -93 -23 84 답은 a = 2, b = 6인 경우의 59+26-53+58+97=187가 된다.

 

31 -41 59 26 -53 58 97 -93 -23 84

S(j)를 A[0..n-1]에서 j에서 끝나는 구간 중 최대합으로 정의 (구간 [a,b]로 안 구하는 이유는 DP 기법을 쓰면 이전 값을 table에 저장할 것이기 때문에 그냥 0부터 j까지 해도 최대합이 구해짐)

S(j-1)의 값을 안다면 S(j)는 j의 값을 포함하거나 포함하지 않을텐데 A[j]의 값이 양수면 무조건 포함할 것이고 음수면 다음 결과에 따라 포함할지 말지 결정해야하기 때문에 포함하거나 버리거나 할 수 있다. 포함하면 S[j] = S[j-1] + A[j]이고 버리면 다시 그부분부터 시작이므로 S[j]=0

S(j) = max{A[0], 0] (j=0)

      = max{S(j-1) + A[j], 0} (0<j<=n-1)

따라서

배열 S[0..n-1] 준비

S[0] = max(A[0], 0)

for j=1 to n-1

  S[j] = max(S[j-1] + A[j], 0)

return max{S[0], S[1], ..., S[n-1])

 

시간복잡도 O(n), O(n)의 메모리 사용

 

 

5번

길이가 n 인 정수의 배열 A[0..n-1]가 있다. A[a]*A[a+1] * … * A[b]의 값을 최대화하는 구간 (a, b)를 찾는 방법을 설계하고 분석하라. 배열 A의 원소는 양수, 음수, 0 모두 가능하다. 예를 들어, 배열 A가 아래와 같이 주어졌을 경우 (n = 7), -6 12 -7 0 14 -7 5 답은 a = 0, b = 2인 경우의 (-6)*12*(-7)=504가 된다.

 

최대합처럼 하지만 음수 x 음수, 0의 경우를 고려해야 한다. 따라서 최대합을 할 때와 달리 최소인 경우도 table에 저장해줘야 함

P(j)를 A[0..n-1]에서 j에서 끝나는 구간 중 최대곱으로 정의(P(j)는 항상 1이상의 값)

A[j]가 양수인 경우 => max{P(j-1) * A[j], 1}

A[j]가 음수 혹은 0인 경우 => max{Q(j-1) * A[j], 1}

Q(j)를 A[0..n-1]에서 j에서 끝나는 구간 중 최소곱으로 정의(Q(j)는 항상 0, 1, 음수)

A[j]가 양수인 경우 => min{Q(j-1) * A[j], 1}

A[j]가 음수 혹은 0인 경우 => min{A[j], Q(j-1) * A[j]}

배열 두 개를 선언하고 위 점화식에 따라서 저장

마지막에 P(0)..P(n-1) 중 최대인 것을 리턴

시간복잡도: O(n)