나의 알고리즘 공부 여정7 - 최적해 알고리즘

20210317_TIL

 

• 동적계획법(이하 DP), 분할정복, 그리디 알고리즘 문제들을 풀었다. 상황별로 그에 맞는 최적해 알고리즘을 적용해보면서, 최적해 알고리즘을 잘 풀기 위한 경험을 쌓았다.
• 최적해 알고리즘 문제들을 여러 유형 접해보며, DP적 사고, 분할정복적 사고, 그리디 알고리즘적 사고 등을 연습 중이다. 상황별로 '최적'의 값을 도출해야하기 때문에 이전에 소개했던 탐색 알고리즘보다 문제가 조금 까다로운 측면이 있다. 최적의 값을 도출하기 위해 고려해야 할 상황들을 구성하고, 그 상황 별로 도출되는 결과값들을 모두 계산해야 하기 때문이다.

 

1. 최적해 알고리즘 분류

 

오늘 소개할 알고리즘은 최적해 알고리즘이다. 이름 그대로 '최적값'을 도출할 때 쓴다.

최적해 알고리즘 종류는 다음과 같다.

 

모든 상황을 고려해 최적해를 도출

• DP : 하나의 문제를 부분으로 쪼개어, 부분 문제를 해결해 '저장'한 후 이를 활용해 상위 문제를 해결. 부분 문제는 서로 중복 (Top down 방식, Bottom up 방식 두 가지 존재)
• 분할 정복 : 하나의 문제를 부분으로 쪼개어 부분 문제를 해결해 이들을 합병하여 상위 문제를 해결. 부분 문제는 서로 중복되지 않음

 

 

모든 상황을 고려하지 않고 최적해를 도출

• 그리디 알고리즘 : 문제 해결 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 내려 최종 해답에 도달

 

2. 문제 형태 분석 및 코드로 구현

 

DP 문제

2579번: 계단 오르기

최적해 알고리즘 문제의 공통적인 특징 : 문제에서 상황을 던져주고 '최솟값', '최댓값'을 찾기를 요구한다. 이 문제 역시 점수의 '최댓값'을 묻고 있다.

 

DP 문제의 고유한 특징 : 주어진 상황에서 펼칠 수 있는 모든 경우의 수를 고려한다. 이 경우의 수를 고려할 때, 부분 문제의 결과값을 누적해서 상위 문제를 푸는 데에 쓴다. DP 문제에서 중요한건 n번째 차례에 n-1, n-2, ...등 그 이전 차례의 값을 어떻게 가져다 쓸 것인지 알기 위해 n번쨰와 그 이전 차례의 '관계'를 알아차릴 수 있도록 고민을 해야 한다. (이 부분이 어려워서 DP문제가 까다로운 것이다.)

import sys

n = int(input())
stair = [0]*301
dp = [0]*301

for i in range(n):
    stair[i] = int(input())
dp[0] = stair[0]
dp[1] = stair[0] + stair[1]
dp[2] = max(stair[1] + stair[2], stair[0] + stair[2])
for i in range(3, n):
    dp[i] = max(dp[i - 3] + stair[i - 1], dp[i - 2]) + stair[i]
print(dp[n - 1])

 

 

 

 

분할 정복 문제

2630번: 색종이 만들기

최적해 알고리즘 문제의 공통적인 특징 : 문제에서 상황을 던져주고 '최솟값', '최댓값'을 찾기를 요구한다. 이 문제 역시 '최소' 횟수로 색종이를 자르며 잘린 색종이들의 수를 묻는 문제였다.

 

분할정복 문제의 고유한 특징 : 주어진 상황에서 펼칠 수 있는 모든 경우의 수를 고려한다. 이 경우의 수를 고려할 때, 부분 문제들은 서로 겹치지 않는다. 따라서 상위 문제를 해결하기 위해서는 부분문제의 값을 모두 '병합'해서 결과값을 도출해야 한다.

import sys

N = int(sys.stdin.readline().strip())
paper_list = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(N)]
white_count = 0
blue_count = 0

def divide(x, y, n):
    global white_count, blue_count
    paper_color = paper_list[x][y]
    check_color = True

    for i in range(x,x+n):
        for j in range(y,y+n):
            if paper_color != paper_list[i][j]:
                check_color = False
                divide(x, y, n//2)
                divide(x, y+(n//2), n//2)
                divide(x+(n//2), y, n//2)
                divide(x+(n//2), y+(n//2), n//2)
                return

    if check_color:
        if paper_color:
            blue_count += 1
        elif not paper_color:
            white_count += 1

divide(0, 0, N)
print(white_count)
print(blue_count)

 

 

그리디 알고리즘 문제

11047번: 동전 0

최적해 알고리즘 문제의 공통적인 특징 : 문제에서 상황을 던져주고 '최솟값', '최댓값'을 찾기를 요구한다. 이 문제 역시 동전 개수의 최솟값을 묻고 있다.

 

그리디 알고리즘 문제의 고유한 특징 : 주어진 상황에서 펼칠 수 있는 모든 경우의 수를 구하지 않고도 최적값을 구한다. 때문에 동전 문제 와 같은 문제들은 DP, 분할정복 문제보다 소스 코드 구현이 쉬워 쉬워보일 수 있으나!! 사실 그리디 알고리즘이 제일 어렵다. 어려운 이유는 다음과 같다. 첫번째로 일단 어떤 문제에 그리디 알고리즘을 쓰려면, 그리디 알고리즘으로 그 문제의 '최적값'을 구할 수 있다는 증명이 있어야 한다. 그리디 알고리즘은 모든 경우의 수를 탐색하는 것이 아니기 때문에, 쓸 수 있는 상황이 한정적이기 때문이다. 실수로, 그리디 알고리즘을 쓰면 안되는 상황에 그리디 알고리즘을 사용한다면 틀린 최적값을 구하게 된다. 두 번째로 그리디 알고리즘이 '현재상황에서'의 최적값을 계속 찾아나가는 알고리즘인데 현재 상황의 최적값이 어떤 것인지에 대한 규칙 파악 역시 필요하기 때문이다.

import sys

N, K = map(int,sys.stdin.readline().strip().split())

coins = [int(sys.stdin.readline().strip()) for i in range(N)]
coins.reverse()

count = 0
for coin in coins:
    if K//coin > 0:
        count += K//coin
        K = K - (coin * (K//coin))

    if K == 0:
        break

print(count)