4/30 다이나믹 프로그래밍, 그리디 알고리즘(Greedy Algorithm)

오늘도 어제에 이어 다이나믹 프로그래밍을 활용한 문제를 조금 풀어봤습니다
문제 난이도가 올라가 어렵기도 하고 아이디어를 떠올리고 코드로 옮기는것도 힘들었지만 실력이 늘어가는 것 같아서 좋습니다 :)

오늘 푼 문제입니다.

문제 링크

점프

문제
N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 한다. 이때 다음 조건들이 만족되어야 한다.
이동은 앞으로만 할 수 있다. 즉, 돌 번호가 증가하는 순서대로만 할 수 있다.
제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다. 그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거나, 속도를 붙여 x+1칸 점프를 할 수 있다. 물론 점프를 할 때에는 한 칸 이상씩 해야 한다.
각 돌들은 각기 그 크기가 다르고, 그 중 몇 개의 돌은 크기가 너무 작기 때문에 당신은 그러한 돌에는 올라갈 수 없다.
위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 필요한 최소의 점프 횟수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 두 정수 N, M(0 ≤ M ≤ N-2)이 주어진다. M은 크기가 맞지 않는, 즉 크기가 작은 돌의 개수이다. 다음 M개의 줄에는 크기가 작은 돌들의 번호가 주어진다. 1번 돌과 N번 돌은 충분히 크기가 크다고 가정한다.

출력
첫째 줄에 필요한 최소의 점프 횟수를 출력한다. 만약 N번 돌까지 점프해갈 수 없는 경우에는 -1을 출력한다.

예제 입력 1
19 3
11
6
16

예제 출력 1
6

이 문제는 이전 LCS와 동전을 풀었던 방식을 이용하여 풀어보려 했습니다
풀면서 최대 이동속도를 어떻게 구하지, 라는 고민하다가 검색을 해보니 int((2 * N) ** 0.5) + 1 이라는 방식으로 1부터 속도가 끊임없이 1씩 증가하며 점프할 때 N에 도달했을 때의 속도의 근삿값을 구할 수 있다는 걸 알게 되었고, dp[i][j] = min(dp[i - j][j - 1], dp[i - j][j], dp[i - j][j + 1]) + 1 라는 점화식을 얻을 수 있었습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
small = [int(input()) for _ in range(M)]

# 이동할 수 있는 최대 속력 구하기
max_speed = int((2*N)**(1/2)) + 1

# DP 테이블 초기화
dp = [[float('inf')] * (max_speed+1) for _ in range(N+1)]

# 2번 돌다리가 없는 경우
if 2 not in small:
# 2번 돌다리에서의 이동 최소 횟수 초기화
    dp[2][1] = 1
    # 3번 돌다리부터 N번 돌다리까지
    for num in range(3, N+1):
    # num번 돌다리가 없는 경우
        if num not in small:
        # 현재 속력(이동거리)에 따른 최소 이동 횟수 계산
            for speed in range(1, max_speed):
                dp[num][speed] = min(dp[num - speed][speed - 1], dp[num - speed][speed], dp[num - speed][speed + 1]) + 1

# N번 돌다리까지의 최소 이동 횟수 계산
ans = min(dp[N])

# 도달할 수 없는 경우 -1 출력, 그 외에는 최소 이동 횟수 출력
if ans == float('inf'):
    print(-1)
else :
    print(ans)

그리고 오늘은 그리드 알고리즘에 관해서 기초적인 공부를 해봤습니다

그리디 알고리즘

• 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다
• 그리디 해법은 그 정당성 분석이 중요합니다
  • 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다

예시 문제) 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.

Q. 최적의 해는 무엇인가요?
Q. 단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다
• 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다

<문제> 거스름 돈 : 문제 설명

• 당신은 음식점의 계산을 도와주는 점원입니다.
  카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다.
  손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요.
  단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

<문제> 거르름 돈 : 문제 해결 아이디어

• 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됩니다.
• N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 줍니다.
  • 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 됩니다.
• N = 1260일 때의 예시를 확인해 봅시다

<문제> 거스름 돈 : 정당성 분석

• 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 무엇일까요?
  • 가지고 있는 동전 중에서 큰 다위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.
• 막약에 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면 어떻게 될까요?
  • 그리디 알고리즘으로 문제를 풀면 500원 1개, 100원 3개의 값이 나오지만 정답은 400원 2개입니다.
• 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 합니다.

<문제> 거스름 돈 : 답안 예시(python)

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

<문제> 거스름 돈 : 시간 복잡도 분석
화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)입니다.
이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받습니다.

그리디 알고리즘을 활용한 기초 문제입니다

문제 링크

동전 0

문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1
10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1
6

예제 입력 2
10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2
12

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

money = []
count = 0

for _ in range(N):
    A = int(input())
    money.append(A)
    # 리스트를 내림차순으로 바꿈
    money.sort(reverse=True)

for coin in money:
    # 목표금액에서 뺄 수 있는 큰 수 부터 빼기
    # count에는 K원을 만드는데 필요한 동전 개수
    count += K // coin 
    K %= coin

print(count)

그리디 알고리즘에 대해 공부할때 블로그나 영상에서 많이 소개된 문제여서 그런지 그렇게 어렵지 않았습니다
오늘은 그리디 알고리즘의 기초에 대해 공부하고, 기초적인 문제를 풀어봤으니 내일은 조금 더 어려운 문제을 풀어보며 공부해봐야겠습니다