알고리즘[Algorithm] | 그리디(Greedy, 탐욕법)

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘

즉, 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

기준에 따라 좋은 것을 선택하는 알고리즘이므로 "가장 큰 순서대로" 또는 "가장 작은 순서대로"와 같은 기준을 제시해준다.

 

아래는 책에 제공되어 있는 연습 문제인데, 문제는 검색하면 나와있으니 나는 내가 접근한 방식이나 풀이 위주로 글을 작성했다.

[이코테] 실전문제 1: 큰 수의 법칙

처음엔 반복문으로 풀이하려고 접근했다가 문제를 계속 살펴보니

굳이 반복문을 사용하지 않고 풀 수 있을 것 같다는 생각이 들어 중간에 풀이를 한번 갈아엎었다.

 

가장 큰 수를 만들기 위해서는 숫자 배열 중 첫 번째로 큰 수, 두 번째로 큰 수만 필요하고,

가장 큰 수를 연속할 수 있는 횟수인 K번 더한 뒤 두 번째로 큰 수를 한번 더하고 또 가장 큰 수를 K번 더하는 방법으로 접근했다.

 

만약 첫 번째, 두 번째 수가 같다면 그 값을 M번 더하여 반환하도록 하였다.

 

이를 코드로 구현하면 아래 소스코드와 같다.

M // K로 가장 큰 수를 연속하여 더할 수 있는 횟수를 구했고, M % K로 두 번째 큰 수를 더해야 하는 횟수를 구했다.

N, M, K = map(int,input().split())
numbers = list(map(int,input().split()))
numbers.sort()

answer = 0
first = numbers[N-1]
second = numbers[N-2]

if (first == second):
  answer = first * M
else:
  answer = (first * K * (M // K)) + (second * (M % K))

print(answer)

 

[이코테] 실전문제 2: 숫자 카드 게임

이 문제를 풀면서 가장 많이 시간을 쓴 부분은 입력 값을 받는 부분이었다.

입력받는 자체는 어렵지 않지만, 뭔가 조금 더 효율적이게 값을 받고 싶다는 생각이 들어서 데이터 가공을 이리저리 해보다가

그냥 원래대로 돌려두고 문제를 풀었다.

 

책에 있는 풀이처럼 각 행마다 가장 작은 수를 뽑은 뒤 그중 가장 큰 수를 선택하는 풀이 방법으로 접근했다.

아래 소스코드는 나의 풀이이다.

import sys

N, M = map(int,input().split())
datas = [sys.stdin.readline().rstrip() for _ in range(N)]

answer = 0

for data in datas:
  a = list(map(int, data.split()))
  a.sort()

  if (answer < a[0]):
    answer = a[0]

print(answer)

 

여러 줄을 입력받아야 해서 sys 라이브러리를 사용했고, 가장 작은 수를 찾기 위해 sort()로 정렬 후 0번 인덱스 값을 찾았다.

문제를 푼 뒤 풀이를 확인했는데, min()을 사용할 수 있다는 것을 깨달았고,

굳이 sys 라이브러리를 사용하지 않아도 풀 수 있다는 것을 깨달았다.

 

이 부분을 기억에 더 남기기 위해 풀이 소스코드도 추가해 둬야겠다.

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

answer = 0
for i in range(N):
  data = list(map(int, input.split()))
  min = min(data)
  answer = max(answer, min)

print(answer)

 

[이코테] 실전문제 3: 1이 될 때까지

이 문제는 풀긴 풀었으나 최소 횟수를 구해야 하는 것을 확인하지 못하고 해설을 봐버려서 제대로 풀어보지 못했다.

그러나 제공된 해설을 이해하는데 꽤 시간이 걸렸다.

 

아래는 제공된 해설 코드이다.

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N == k로 나누어떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

여기서 target = (n // k) * k result += (n - target) n = target 이 부분이 이해가 잘 안 됐다.

책에는 설명이 N == k로 나누어 떨어지는 수가 될 때까지 1씩 빼기 라고 되어있어서 더더욱 이해가 안 됐다.

그렇지만 변수들을 print 해보면서 디버깅을 차근차근 하니 이해가 됐다.

 

가장 중요한 점은 수에서 -1 하는 단계보다 수를 나누는 단계가 더 많이 수행되도록 하는 것이다.

코드를 차례대로 읽으며 단계를 설명해 보면 다음과 같다.

 

1. target = (n // k) * k를 통해 n이 k로 나누어 떨어지는 값을 target에 저장한다.
2. result += (n - target)에서 n - target은 현재 n이 target이 되기 위해 -1해야 하는 횟수를 구한 것이고 이 값을 result에 더하여 과정의 횟수를 반영한다.
3. 이후 result += 1 n // = k를 통해 나누는 과정을 수행한다.

여기서 target = (n // k) * k 부분을 기억에 남겨야 할 것 같다.

 

여담이지만 너무 이해가 안 돼서 책의 깃허브에 가서 코드를 확인했었는데, 내가 제일 헷갈렸던 설명 부분이

N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기 로 수정되어 있었다. 책에도 반영되어 있었다면 이해가 쉬웠을 텐데 ㅜㅜ

그래도 덕분에 더 기억에 잘 남을 것 같아서 결과적으론 좋은 듯하다 =)