알고리즘을 공부하는 데 있어서 우선적으로 공부해야 하는 알고리즘이 있다면 세 가지가 있다고 한다.

• 그리디 알고리즘
• 탐색 알고리즘
• DP ( 동적계획법)

이 세 가지인데 그중에서 그리디 알고리즘에 대해 공부한 것을 정리하는 글

그리디 알고리즘(Greedy Algorithm)이란

탐욕법이라고도 부르며 현재 상황에서 가장 좋은 것을 고르는 알고리즘이다.

현재 상황에서 가장 좋은 것을 고른다는 것은 어떠한 문제가 여러 단계로 나뉘어

차례로 알고리즘이 이어지는 경우, 그 단계마다 가장 좋은 선택을 한다는 것을 의미한다.

그러나 현재 상황에서 가장 좋은 것을 고르는 행위가 그 문제의 모든 경우의 수에서 발생하는최적의 해라는 것을 담보하지는 않는다. 그렇기에 문제를 봤을 때 이 문제가 그리디 알고리즘으로 

풀 수 있는지 추론할 수 있는 능력이 필요하다.

 문제를 그리디 알고리즘으로 풀기 위한 조건

• 각각의 값이 서로 다른 값에 영향을 주지 않을 것
• 그리디 알고리즘으로 풀어낸 값이 모든 경우의 수에서 최적의 해일 것
• 주어진 상위의 값이 하위 값의 배수일 것

세 번째 조건이 그래도 문제를 파악하는데 가장 도움이 되지 않을까 싶다.

그런데 세 번째 조건을 만족해도 그리디로 풀 수 없는 문제가 있으니 문제같다......

예제

백준 11047번 문제

필요한 동전의 최솟값을 구하는 문제로 가장 큰 가치를 가진 동전부터 차례로 나누면 

동전의 최솟값을 구 할 수 있을 것으로 보인다.

거기에 그리디 알고리즘을 적용하게 만든 가장 중요한 문장은 노랗게 칠한 문장 같다.

주어진 상위의 값이 하위 값의 배수라는 것을 알려주었으니 말이다.

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

for i in range(N):
    arr.append(int(input()))
arr.reverse()                   # 동전을 큰 수부터 계산하기 위해서

R = 0                           # 필요한 동전의 갯수
for i in arr:
    if K//i != 0:               # 조건이 없어도 되긴하다.
        R += K//i                
        K = K%i

print(R)

문제풀이 코드

이제야 한 문제 풀어본 것이기 때문에 앞으로도 문제를 풀어보면서

내가 그리디 문제인지 잘 추론할 수 있는 능력을 기르도록 해야겠다.

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문 하나를 단축시킬 수 있었다.

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까지라 그런거 같다.