2021.12.08

백준 11047 동전 O

N, K = map(int, input().split())
arr = []

for i in range(N):
    arr.append(int(input()))

R = 0
arr.reverse()
for i in arr:
    if K//i != 0:
        R += K//i
        K = K%i

print(R)    

본래 이번 주는 DP 문제 위주로 풀려고 했는데 

친구가 그전에 그리드와 탐색문제를 먼저 풀어보는 것이 좋다고 해서 

그리드 문제로 급히 노선을 갈아탔다.

그런데 지금 문제는 풀었지만

그리드 문제의 유형이 무엇인지 그리드 알고리즘이 무엇인지 모르기 때문에

공부하고 정리하는 시간을 가져야겠다.

2021.12.07

백준 9184 신나는 함수 실행

# 9184 ; 신나는 함수 실행
import sys

def W(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return W(20,20,20)
    
    if dp[a][b][c]:
        return dp[a][b][c]
    
    if a < b < c:
        dp[a][b][c] = W(a,b,c-1) + W(a,b-1,c-1) - W(a,b-1,c)
        return dp[a][b][c]
    dp[a][b][c] = W(a-1,b,c) + W(a-1,b-1,c) + W(a-1,b,c-1) - W(a-1,b-1,c-1)
    return dp[a][b][c]
    
dp = [[[0 for i in range(21)] for i in range(21)] for i in range(21)]

while True:
    a,b,c = map(int, sys.stdin.readline().split())
    if a == -1 and b == -1 and c == -1:
        break
    print('w({}, {}, {}) = {}'.format(a,b,c,W(a,b,c)))

input()을 사용하기보다는 sys를 import 해서 시간 단축을 조금 더 해줬다.

다른 건 문제의 식을 전부 가져왔는데

중요한 아이디어는 삼차원 배열에 값을 저장해주는 것과

그 값이 있을 경우 바로바로 꺼내오는 것이 문제풀이의 핵심인 듯하다.

삼차원 배열에 저장해도 아래 코드를 쓰지 않으면 시간 초과가 뜬다.

    if dp[a][b][c]:
        return dp[a][b][c]

여담으로 아래 코드에서 공백을 안 넣어 줬더니 틀렸습니다만 계속 떠가지고 

뭐가 문제인지 한참을 찾았다...

print('w({}, {}, {}) = {}'.format(a,b,c,W(a,b,c)))

이번 주 알고리즘 스터디의 큰 주제를 DP로 잡았다.

알고리즘 문제를 푸는 방법으로 BFS, DFS, DP 등 여러 방법들이 있지만 

오늘 풀려고 했던 문제가 DP와 관련되었고 모두 어려워해서

이번주는 DP를 단계별로 집중 탐구하는 기간으로 정했다. 

그렇기에 문제를 풀기에 앞서 DP가 무엇인지 나름대로 공부하고 이해해보고자 글을 작성한다. 

두산백과에 따르면 DP란 '다단계에 걸친 의사결정의 최적화를 추구하기 위한 수리적 계획법'이라고 한다.

너무 어렵게 적혀 있는 것 같은데 내가 이해한 DP의 핵심은 '같은 계산을 반복하지 않는 것'이다.

즉, 중복되는 부분의 값들을 메모리에 저장해 두었다가 필요할 때 꺼내 사용함으로써 

문제 풀이에 있어서 시간단축 효과를 얻을 수 있다.

DP의 방법으로 Top-Down 방식과 Bottom-Up방식의 두 가지 방식이 있다고 하는데 정확히 구분은 잘 못하겠다.

탑다운은 재귀함수를 만들어서 상위 값을 구하기 위해 하위 값을 계속해서 불러오는 것 같고,

바텀업은 하위 값부터 차례로 구해서 원하는 N번째의 값을 구하는 것 같다.

그리고 문제를 DP 방법으로 풀기 위한 조건은

1. 큰 문제를 작은 문제로 나눌 수 있다.

2.  문제의 식을 점화식으로 나타낼 수 있다.

#1463; 1로 만들기 Bottom-Up

N = int(input()) # 주어진 값 1 <= N <= 10**6
arr = [0,0,1,1] + [0]*N # N의 값의 0,1,2,3 일 때의 연산하는 최솟값, 이후 연산하는 최솟값들의 배열

for i in range(4,N+1): # N까지 연산하는 최솟값 구하기
    arr[i] = arr[i-1] + 1  # i값의 -1
    if i%3 == 0:
        arr[i] = min(arr[i], arr[i//3] + 1)
    if i%2 == 0:
        arr[i] = min(arr[i] ,arr[i//2] + 1)

print(arr[N])

바텀업 방식으로 풀어본 1463번 문제

재귀함수를 만들어서 탑다운 방식으로도 풀어보려고 했는데 능력의 한계로 인하여 실패했다...

아시는 분이 있다면 알려주세요

2021.12.03

백준 9020 골드바흐의 추측

def prime(x):                  # 소수 판별 함수
    if x == 1:
        return False
    else:
        for i in range(2,int(x**0.5)+1):
            if x%i == 0:
                return False
        return True
    
def goldhach(x):             # 골드바흐 파티션 중 두 수의 차이가 가장 작은 값
    for i in range(int(x/2),1,-1):
        if prime(i):
            for j in range(2,x):
                if (i + j) == x and prime(j):
                    return [i , j]

T = int(input())             # 테스트 케이스 

for i in range(T):
    n = goldhach(int(input()))
    for i in range(2):
        print(n[i], end = ' ')

 처음에 푼 코드

그런데 이 코드는 시간이 너무 걸렸다

골드바흐 함수를 정의하는데 for문과 범위에 쓸모없는 수들이 포함돼서 그랬다.

def prime(x):                  # 소수 판별 함수
    if x == 1:
        return False
    else:
        for i in range(2,int(x**0.5)+1):
            if x%i == 0:
                return False
        return True
    
def goldhach(x):          # 골드바흐 파티션 중 두 수의 차이가 가장 작은 값
    arr = [2] + list(range(3,(x//2)+1,2))
    for i in reversed(arr):
        if prime(i):
            if prime(x-i):
                return [i , x-i]

T = int(input())             # 테스트 케이스 

for i in range(T):
    n = goldhach(int(input()))
    for i in range(2):
        print(n[i], end = ' ')

 수정한 코드

이 코드가 처음 코드보다 시간 측면에서 7배 빠르다.

우선 소수 판별 함수에서 주어진 수가 2부터 1씩 커지는 숫자를 넣어서 나누었을 때

나머지가 0이면 False를 리턴 아닌 경우 소수이므로 True를 리턴한다.

범위를 x**0.5까지 한정한 이유는 수학적으로 x의 제곱근의 배수까지 지우면

x이하의 소수만 남게 되기 때문이다. (에라토스테네스의 체를 참고)

위 두 코드의 차이는 골드바흐 함수 정의에 차이가 있는데

짝수 n이 소수 M 과 N의 합으로 나타낼 수 있으며 M과 N의 차이가 가장 적은 값을 구할 때

소수가 2를 제외하고는 모두 홀수인 점과 M, N의 차이가 가장 적은 값은 n/2 값부터 역순으로

적용해보면 찾을 수 있다는 점을 통해 구하는 범위를 더 좁게 한정 시킬 수 있었고

n = M + N 즉 n - M = N 이라는 것을 통해서 for문 하나를 단축시킬 수 있었다.