이번 주 알고리즘 스터디의 큰 주제를 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문 하나를 단축시킬 수 있었다.

2021.12.02

백준 2581 소수

#2581 소수

M = int(input())
N = int(input())

arr = [ i for i in range(M,N+1) if i > 1]   # M~N 까지 숫자 배열

for i in range(2, int(N**0.5)+1):       
    s = [i for i in range(0,N+1,i)]         # i의 배수 배열
    if i in arr:                            
        arr = list(set(arr) - set(s))       # arr에서 배수를 전부 빼고 
        arr.append(i)                       # 맨처음 숫자만 추가 
    else:
        arr = list(set(arr) - set(s))      

if arr == []:
    print(-1)
else:
    print(sum(arr))
    print(min(arr))

소수 문제를 해결할 때 에라토스테네스의 체를 사용하면 도움이 된다.

에라토스테네스의 체는 마치 체로 걸러내듯 소수를 찾는데

숫자 N까지의 소수를 찾고 싶으면 2부터 N까지의 숫자 배열을 작성하고

2부터 시작하여 2 이외의 2의 배수를 지운다. 2는 최초의 소수(p)

그리고 그다음 소수인 3을 제외한 3의 배수를 지운다. (p = 3)

이것을 p의 제곱이 N 보다 커질 때까지 계속한다.

이를 반대로 생각하여 N의 제곱근을 구하면 P의 최댓값 범위를 정할 수 있다.

range(2,int(N**0.5)+1)

2021.11.26

백준 11399

# 11399 
N = int(input())                      # 사람의 수
P = list(map(int,input().split()))    # 인출하는데 걸리는 시간 Pi
R = [0]                               # 걸린 시간을 차례로 더한 리스트

for i in range(N):
    R.append(R[i]+min(P))             # 리스트 이전 값과 최솟값 더하기
    del P[P.index(min(P))]            # 최솟값 삭제

print(sum(R))

문제를 보면 '인출하는데 걸리는 시간'을 작은 수부터 차례로 정렬해서 더해 나가면

가장 작은 값을 얻을 수 있는 것을 알 수 있다.

그래서 처음에는 set() 함수를 사용할까 했는데 그러면 중복 값들이 삭제가 되니

그냥 min()으로 가장 작은 값을 불러오고 거기에 이전 최솟값들의 합을 더해줘서

각 사람들의 걸린 시간 리스트인 R을 만들어줬다.

2021.11.24

2108

#2108
N = int(input())
L = []

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

print(sum(L)//N)
L.sort()
print(L[round(len(L)/2)])

r = 0
s = 0
g = []
for i in L:
    if L.count(i) > r:
        r = L.count(i)
        s = i
for i in L:
    if L.count(i) == r:
        g.append(i)
g.sort()
        
try:
    print(g[1])
except:
    print(g[0])
print(max(L)-min(L))
    

정렬 문제...?

그것보다는 시간 초과를 어떻게 해결해야 할지의 문제인데

sys를 사용해도 시간초과가 뜨고

불필요한 반복구문 같은걸 제거하면 될 거 같은데 계속 시간 초과가 뜬다.

2021.11.23

1003

# 1003
def one(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return one(x-1)+one(x-2)

def zero(x):
    if x == 0:
        return 1
    elif x == 1:
        return 0
    else:
        return zero(x-1)+zero(x-2)

T = int(input())
for i in range(T):
    N = int(input())
    print(zero(N),one(N), end = ' ')

피보나치수열 함수를 이용해서 풀어보려고 했더니 시간 초과가 뜬다.

DP를 이용해서 풀어야 한다고 해서 밑에 코드를 짜봤다.

이미 계산했던 것들을 리스트에 넣어주고 다음에 그 값을 구할 때

다시 계산하는 게 아니라 리스트에서 불러오면 돼서 시간적으로 단축 가능하다.

# 1003
T = int(input())
Z = [0,1,2,3]
for i in range(T):
    N = int(input())
    if N == 0:
        print(1,0)
    elif N == 1:
        print(0,1)
    elif N == 2:
        print(1,1)
    else:
        try:
            print(Z[N-2],Z[N-1])
        except:
            for i in range(Z.index(Z[-1]),N):
                Z.append(Z[i-1]+Z[i])
            print(Z[N-2],Z[N-1])     

백준 10870

#10870
# 재귀함수로 풀기...?

def F(x):
    L = [0,1]
    for i in range(2,x+1):
        L.append(L[i-2]+L[i-1])
    return L[x]

n = int(input())
print(F(n))

리스트 없는 함수를 만들어보려고 했으나 못 만들었는데

내가 함수를 잘 몰라서 벌어진 일이었다.

#10870

def F(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return F(x-1)+F(x-2)

n = int(input())
print(F(n))

요렇게 더 간단히 작성할 수 있었다.

근데 코드길이는 짧은데 시간이랑 메모리는 같으니 별 상관없는 건가 싶은데

아마 문제의 n이 20까지라 그런거 같다.

백준 10828

import sys
N = int(input()) # 명령의 수
ST = []          # 스택

for i in range(N):
    S = list(input().split())
    if S[0] == 'push':
        ST.append(int(S[1]))
    elif S[0] == 'pop':
        try:
            print(ST.pop())
        except:
            print(-1)
    elif S[0] == 'size':
        print(len(ST))
    elif S[0] == 'empty':
        if ST == []:
            print(1)
        else:
            print(0)
    elif S[0] == 'top':
        try:
            print(ST[-1])
        except:
            print(-1)

스택문제. 함수를 써야 하나 싶다가 for구문에 if 절을 쓰면 풀 수 있을 것 같았다.

근데 시간초과가 뜨길래 아래처럼 sys를 import 해줬더니 정답

# 10828
import sys
N = int(sys.stdin.readline()) # 명령의 수
ST = []                       # 스택

for i in range(N):
    S = sys.stdin.readline().split()
    if S[0] == 'push':
        ST.append(int(S[1]))
    elif S[0] == 'pop':
        try:
            print(ST.pop())
        except:
            print(-1)
    elif S[0] == 'size':
        print(len(ST))
    elif S[0] == 'empty':
        if ST == []:
            print(1)
        else:
            print(0)
    elif S[0] == 'top':
        try:
            print(ST[-1])
        except:
            print(-1)

Test