크래프톤 정글 week03, day22 - 알고리즘 문제

피보나치2

• 피보나치를 재귀방식이 아닌 DP방식으로 풀기(동적 프로그래밍)

import sys

def fibo(n):
    list = [0, 1] + [0]*(n-1)

    for i in range(2, n+1):
        list[i] = list[i-1] + list[i-2]

    return list[n]

n = int(sys.stdin.readline())

print(fibo(n))

 

01타일

• 1또는 00만을 이용해서 n개의 타일을 깔수있는 경우의 수를 구하기(동적 프로그래밍)

import sys

n = int(sys.stdin.readline())

pibo = [0, 1]
m1 = 0
m2 = 0
i = 0

while i != n:
    m1 = pibo[0] + pibo[1]
    m2 = pibo[1]
    pibo[0] = m2 % 15746
    pibo[1] = m1 % 15746
    i += 1

result = pibo[1]

print(result)

 

LCS

• 최장공통 부분 수열 알고리즘을 이용해 연속된 문자열의 개수를 출력(LCS)

import sys

def lcs(x, y):
    m = len(x)
    n = len(y)
    l = [[0]*(n+1) for _ in range(m+1)]
    cnt = 0


    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                l[i][j] = 0
            elif x[i-1] == y[j-1]:
                l[i][j] = l[i-1][j-1]+1
            else:
                l[i][j] = max(l[i-1][j], l[i][j-1])
                cnt = l[i][j]

    return cnt    


first_string = list(sys.stdin.readline())
second_string = list(sys.stdin.readline())

print(lcs(first_string, second_string))

 

동전 0

• 입력된 값을 몇개의 동전으로 낼 수 있는지 푸는 문제(그리디 알고리즘)

import sys

n, k = list(map(int, sys.stdin.readline().split()))
money = []
cnt = 0
exchange = []

for i in range(n):
    money.append(int(sys.stdin.readline()))

for i in range(n):
    exchange = money.pop()
    if k / exchange < 0:
        continue
    else:
        cnt += k // exchange
        k = k % exchange
print(cnt)

​

잃어버린 괄호

• 입력된 특정 식을 괄호를 이용해 최소값을 구하기(그리디 알고리즘)

import sys

minus = sys.stdin.readline().split('-')
result = sum(map(int, minus[0].split('+')))

for i in minus[1:]:
    result -= sum(map(int, i.split('+')))

print(result)

 

 

학습시간 : 10 ~ 25시