투빅스 9&10기 1주차 Dynamic Programming - 10기 강인구

1번. 맨 위층의 숫자부터 시작해 아래에 있는 수 중 하나를 선택해 내려올 때, 선택되어 왔던 모든 수의 합이 최대가 되는 경로의 합을 구하는 알고리즘을 완성하시오. 아래층에 있는 수는 현재 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형을 이루는 숫자는 모두 정수이며 0이상 99이하이다.

import random

import csv

import time

import os

 

#명령창으로부터 input값을 얻어 n에 저장한다.

#n이 1000,2000으로 클수록 생각보다 오래 걸리길래, 몇 초가 걸렸는지 궁금해서 시간을 확인했다.

#n=1000 - 1.859초, n=3000 - 14.752초

n=int(input("삼각형의 크기(층)를 입력하시오 : "))

cal_start = time.time()

 

#Input값을 토대로 n층의 랜덤한 삼각형을 만들어, triangle.csv에 저장한다.

with open('triangle.csv', 'w', newline='') as fw:

    wr = csv.writer(fw,delimiter=',')

    for i in range(1,n+1):

        a=[]

        j = 1

        while j <= i:

            a.append(random.randint(0,99))

            j=j+1

        wr.writerow(a)

fw.close

 

#저장한 triangle.csv를 읽어오며 각 row는 하나의 배열이므로 a배열은 2차원 배열이 된다.

with open('triangle.csv', 'r') as fo:

    reader_csv = csv.reader(fo)

    i=0

    for row in reader_csv:

        a[i]=row

        i=i+1

        if n <= 30:

            print(row)

i=n

 

#triangle을 불러온 뒤 경로합을 구하기 위해 아래층에서부터 올라간다.

#수열의 개념이므로, i에 대해 일반화 하면 알고리즘을 만들 수 있다.

#i-1층의 j번째에 i층의 j,j+1번째 수 중 더 큰 값을 더하면 i층을 지우고 i-1번째 층까지만 생각 해도 된다.

#이 개념으로 맨 윗층까지 반복하면 맨 윗층은 i층까지의 최대 경로합과 같아진다.

while i >= 2:

    #print(a[i-1])

    for j in range(0,i-1):

        a[i-2][j]=int(a[i-2][j])+max(int(a[i-1][j]),int(a[i-1][j+1]))

        #print(a[i-2][j])

    i=i-1

   

elapsed = int(1000*(time.time() - cal_start))

 

#맨 윗층인 a[0][0]이 최대 경로합이다.

print('Calculate time : %d ms\n최대 경로합 : %d'%(elapsed,a[0][0]))

os.system('Pause')

2번. 0과 1로 채워진 행렬이 있다. 행렬에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 반환하는 함수 large를 완성하시오.

 

import random

import numpy as np

 

#n = 5

#a=np.array([[1,1,1,1,0],[1,1,1,1,1],[0,1,1,1,1],[1,1,1,0,1],[1,1,1,1,1]])

 

#크기가 n인 정사각행렬을 만들며 a에 저장한다.

n = int(input('정사각행렬의 크기를 입력하시오. : '))

a = np.zeros((n,n))

for i in range(0,n):

    for j in range(0,n):

        a[i,j]=random.randint(0,1)

print(a)

 

#행렬의 2행2열의 원소부터 오른쪽 아래로 차근차근 확인해 나간다.

#각 원소의 왼쪽,왼쪽위,위를 확인해 그 수가 크기가 몇인 사각형에 포함됐었는지 확인한다.

#각 원소의 해당방향의 수 중 min값+1을 자기 자신에 대입하며, 이 수가 사각형의 크기가 된다.

#대입하면서, 최대인 값을 maximum에 저장한다.

def large(matrix):

    maximum=1

    for i in range(1,n):

        for j in range(1,n):

            if not a[i-1,j-1]==0 and not a[i-1,j]==0 and not a[i,j-1]==0 and not a[i,j]==0:

                a[i,j] = min(a[i-1,j-1],a[i-1,j],a[i,j-1])+1

                if a[i,j]>maximum:

                    maximum = a[i,j]

    return pow(maximum,2)

 

area = large(a)

 

print('\n')

print(a)

print('\n')

print('Max area = %d'%area)

 

3번. 수열 {10, 20, 40, 25, 30, 15, 50}이 있다. 이 수열의 부분수열 중 모든 원소가 점차 증가하는 수열은 {10, 20, 25, 30, 50}, {10, 20, 40, 50} 등이 있다. 이 중 길이가 가장 긴 수열은 {10, 20, 25, 30, 50}이고 길이는 5이다. 이렇게 수열에서 길이가 가장 긴 증가 부분수열의 길이를 반환하는 알고리즘을 완성하시오.

 

a = [10,5,20,40,22,25,30,15,50] #기존 문제에 5,22 추가

#a = [10,20,40,25,30,15,50]

#[10,20,25,30,50]

#[5,20,22,25,30,50] 가장 긴 수열

print(a)

n = len(a)

 

#수열길이를 확인하기 위해 a와 크기가 같게 b배열을 만든다.

b=[]

for i in range(0,n):

    b.append(1)

#print(b)

 

#가장 긴 수열의 제일 처음은 무조건 a[0]이 되므로 i는 1부터 시작한다.

#a[i]와 이전의 값들과 비교하며 a[i]가 더 크고, b[i]가 이전의 값과 같거나 작으면, b[i]에 이전의 값+1을 한다.

#위 말의 뜻은 더 긴 수열이 확인됐다는 뜻이며, b의 가장 큰 값이 가장 긴 수열의길이가 된다.

for i in range(1,n):

    for j in range(0,i):

        if a[j]<a[i] and b[i]<=b[j]:

            b[i]=b[j]+1

#print(b)

print('가장 긴 수열의 길이 = %d'%max(b))

 

#기존 문제의 알고리즘 수행 과정

#10

#5

#5 20

#5 20 40

#5 20 22

#5 20 22 25

#5 20 22 25 30

#5 20 22 25 30 50

 

4번. 길이가 서로 다른 젓가락쌍들이 있다. 만약 옆에서 길이가 맞는 젓가락쌍을 찾는다면 길이가 맞는 젓가락들의 원래의 짝이 하나의 쌍을 이루고 길이가 맞는 젓가락쌍은 다른 곳에 보낸다. 이 때의 배송비는 새로 만들어진 젓가락쌍과 보내는 젓가락 중 하나의 길이의 곱(원)이다. 배송비를 최소화하여 주어진 젓가락을 배송하려고 할 때, 최소 배송비를 반환하는 함수 chopchop을 구현하라.

 

import numpy as np

 

#a=[10,30,5,60]

a=[30,35,15,5,10,20,25]

#크기 n인 행렬 M을 만든다.

#이때 우리는 최소 배송비를 알아야하므로, M에는 가장 큰 값을 저장한다.

#j,k=i+j 사이의 수 m에 대해 (즉, m은 M안의 i크기의 행렬을 확인하는 수) M에 각 배송비를 더하여 대입한다.

#M[j,k]은 32비트 최대 수이므로 해당 과정을 1회 거쳤을 때 자연스럽게 배송비에 대한 값이 들어간다.

def chopchop(array):

    n=len(array)

    M=np.zeros((n,n))

    for i in range(1,n):

        for j in range(1,n-i):

            k=i+j

            M[j,k]=pow(2,32)

            for m in range(j,k):

                M[j,k]=min(M[j,k],M[j,m]+M[m+1,k]+a[j-1]*a[m]*a[k])

    print(M)

    return M[1,n-1]

 

mincost=chopchop(a)

print('최소 배송비 : %d 원'%mincost)

 

5번. A국의 동전 단위는 1, 3, 5원으로 이루어져 있다고 하자. 8원을 지급하는 방법은 5+1+1+1, 5+3, 3+3+1+1, 3+1+1+1+1+1, 1+1+1+1+1+1+1+1 의 다섯 가지가 있다. 입력이 n=8, s={1,3,5}라면 지급 방법의 경우의 수 5를 출력해야한다.

이러한 지급 방법의 경우의 수를 계산하는 알고리즘을 구현하라.

 

import numpy as np

 

#명령창으로부터 지급할 금액, 동전 종류를 입력받는다.

n = int(input('지급할 금액을 입력하시오 : '))

s = input('모든 동전 단위를 입력하시오 (띄어쓰기로 구분) : ').split()

print('\n')

#n=8

#s=[1,3,5]

 

#중복되는 경우를 방지하기 위해 동전 종류를 오름차순으로 정렬한다.

#수식적 계산을 위해 char형인 s를 int형으로 바꾼다.

s=sorted(s)

k=len(s)

for i in range(0,k):

    s[i]=int(s[i])

 

#경우의 수에 대한 배열 a를 만든다.

#이 때 가장 작은 단위로 지급하는 방법 1가지는 반드시 있으므로 a[0]=1이다.

a=np.zeros(n+1)

a[0]=1

 

#n원에 대해, 각 동전 종류별로 j가 각 단위보다 커지면 a에 이전 수를 더하고,

#다음 동전 종류에 대해서 해당 작업을 반복한다.

for i in range(0,k):

    for j in range(1,n+1):

        if (j-s[i])>=0:

            a[j]+=a[j-s[i]]

 

print('지급 방법의 경우의 수는 %d 가지 입니다.'%int(a[n]))