part 2. 알고리즘 유형 분석 - 탐욕법 Greedy Algorithm

1

탐욕법 Greedy Algorithm

• 매 순간마다 최선의 경우만 골라서 선택하는 방식의 알고리즘
• 다른 경우는 고려하지 않고, 나중은 생각하지 않는다.
• 모든 경우를 다 보진 않아서, 완전탐색 알고리즘 보단 빠르다
• 어떤 경우가 최선인지 찾아야 하고, 규칙성을 발견하는게 포인트
• 당연한 말이지만 그렇다고 완벽하게 이상적인건 아니니 주의

2

동전 거스름돈 문제

• A : 10, 50, 100, 500원 동전을 무한하게 갖고 있다.
• 손님에게 800원을 거슬러주려고 할 때 동전을 최소한으로 주는 방법은?
  • 큰 단위부터 우선적으로 주는게 가장 효과적~
• B: 만약 100, 400, 500원 동전을 무한하게 갖는경우?
  • 400원짜리 2개 주는게 이득임(그리드로 풀수 없는 반례)
• 이러한 경우가 발생하는 이유는 A는 단위가 배수관계로 증대됨, B는 그렇지 않음. 배수의 관계로 B에서는 500원만으로 400원짜리 기준으로 만드는걸 만들수 없고 반대도 그러하므로 안되는 것이다.

따라서… 그리디 문제의 핵심은 ‘판별’

• 이 문제가 진짜 그리디인가 아닌가? 를 파악하는 감각이 필요하다.

3

boj.kr/11047

동전 0

내 생각

• 다행이도 들어오는 값들 중 동전의 관계는 배수라고 명시되어 있다.
• 이 말은 배수 관계이니 그리디를 사용 가능하다는 것. 그렇다면 전체 값을 받은 뒤 동전의 제일 마지막 큰 값부터 목표인 값 k 에 빼는 방식으로 처리하면 될 것으로 보인다.

n, k = map(int, input().split())  
# print("n = ", n)  
# print("k = ", k)  
  
coins = [int(input()) for _ in range(n)]  
coins.reverse()  
# print(coins)  
howManyCoins = 0  
i = 0  
# 구하는데 성공은 했지만 시간초과를 받앗다.  
# while k > 0:  
#     while i < n:  
#         if coins[i] <= k:  
#             howManyCoins += 1  
#             k = k - coins[i]  
#             if coins[i] > k:  
#                 i += 1  
#         else:  
#             i += 1  
  
# 시간초과를 피하기 위해선 한번에 계산 되어야 함  
for coin in coins:  
    if coin <= k: 
    # 조건문으로 쓰지 않는 코인을 스킵하는 것은 속도가 큰 차이가 없다. 
    # 조건문이 있든 없든 44ms ~ 40ms 정도 나옴 
        howManyCoins += k // coin  
        k %= coin  
    else:  
        continue  
  
print(howManyCoins)

4

boj.kr/1449

수리공 항승

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다. 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

예제 입력 1

4 2
1 2 100 101

예제 출력 1

2

예제 입력 2

4 3
1 2 3 4

예제 출력 2

2

예제 입력 3

3 1
3 2 1

예제 출력 3

3

내 생각

• 물이 새는 포인트는 N, 테이프 길이는 L,
• 물 새는 포인트를 돌면서, L의 길이로 커버 되는 영역을 제외한다.
• N, L은 1000 보다 작은 자연수, 물이 새는 곳도 1000보다 작음.
• 물이 새는곳을 기준으로 0.5 좌우로 덮어야만 적절하게 커버가 된다. 즉, L값을 기준으로 좌우 0.5 씩을 뺀 범위 내에 값이 존재 해야한다.
• 즉, 최초 값을 만나면, 해당 값을 L에서 0.5 뺀 부분으로 기록하고, 그 다음 값이 범위 내에 들어가면 유지, 들어가지 않는 위치라면 다음 테이프를 고정을 반복하면 된다.
• 나는 수치적으로 계산을 하려고 하였는데, 이때 어려웠던 부분은 좌표 부분이 점이고, 따라서 테이프 길이를 잘 계산했어야 했다.
• 저자는 좌표를 가지고 진행하였으나, 이 경우 치명적인 단점은 좌표 전체를검수하기에 시간복잡도, 공간복잡도 모두 안 좋다는 점이다. 따라서 좌표압축이 필요하다.

N, L = map(int, input().split())  
breakPoint = [int(x) for x in input().split()]  
breakPoint.sort()  
  
  
# print("N : ", N)  
# print("L : ", L)  
# print("breakPoint: ", breakPoint)  
  
def f(a, b, c):  
    print("min : ", a, "/ max : ", b, "/ total tapes : ", c)  
  
  
minTape = breakPoint[0] - 0.5  
maxTape = minTape + L  
ans = 1  
# f(minTape, maxTape, ans)  
  
for i in range(N):  
    if (minTape < breakPoint[i]) and (maxTape > breakPoint[i]):  
        continue  
    else:  
        ans += 1  
        minTape = breakPoint[i] - 0.5  
        maxTape = minTape + L  
    # f(minTape, maxTape, ans)  
  
print(ans)  
  
  
# 저자가 이야기 하는 방법  
N, L = map(int, input().split())  
cord = [False] * 1001  
for i in map(int, input().split()):  
    cord[i] = True  
  
ans = 0  
x = 0  
while x < 1001:  
    if cord[x]:  
        ans += 1  
        x += L  
    else:  
        x += 1  
  
print(ans)