[이코테] 1이 될 때까지

문제 풀면서 작성한 메모

풀이 과정

---

1. 문제를 정독하면서 메모한다. 주의해야 할 것은 ※으로 표시한다.

입력 첫째 줄에 어떠한 수 N과 나눌 수 K가 주어진다. 이 둘을 입력 조건과 함께 메모했다. 그리고 문제에서 사례로 든 예시는 하나하나 살펴봤다.

2. 알고리즘을 떠올리고 적용하려고 노력한다.

역시 그리디 알고리즘을 알고 있으므로 어떻게 적용할지 고민했다. 지금 당장 가능한 선택 중 최적의 선택을 해야 하므로 N이 K로 나누어 떨어지면 2번의 과정('N을 K로 나눈다.')을, 나누어 떨어지지 않으면 1번의 과정('N에서 1을 뺀다.')을 하는 것이 최적이라 생각했다. 2번의 과정이 N이 K로 나누어 떨어질 때만 선택할 수 있으므로 최적의 해임을 보장받을 수 있다. 그리디는 정렬 알고리즘과 자주 짝을 이뤄 출제되는데, 이번 문제는 정렬할 필요가 없었다.

3. 필요한 변수에 대해서는 변수명을 작성한다.

앞서 답안 예시들이 모두 변수명을 소문자로 시작했으므로 N을 n이라 K를 k라 이름 지었다.

4. 바로 문제 풀지 말고 주석을 달며 의사 코드를 작성한다.

# n,k 입력받기

# 횟수 초기화
# n이 1이 될 때까지 반복
  ## n이 k로 나눠지면
    ### 2번 방법 사용하고 결과 n에 대입
    ### 횟수 추가
  ## n이 k로 안 나눠지면
    ### 1번 방법 사용하고 결과 n에 대입
    ### 횟수 추가

# 횟수 return

 

먼저 n, k에 입력받은 N, K를 저장한다. 횟수를 세기 위해 cnt라는 변수를 만들어 0으로 초기화하고, 1번 혹은 2번의 과정을 한 번 수행할 때마다 1씩 증가시킨다. n이 1이 될 때까지 n이 k로 나누어 떨어지면 2번 방법을, 나누어 떨어지지 않으면 1번 방법을 사용했다. 그리고 최종적으로 cnt를 출력한다. 

5. 의사 코드에 맞춰 구현한다.

# n,k 입력받기
n, k = map(int, input().split())

# 횟수 초기화
cnt = 0
# n이 1이 될 때까지 반복
while n != 1:
  ## n이 k로 나눠지면
  if n % k == 0:
    ### 2번 방법 사용하고 결과 n에 대입
    n //= k
    ### 횟수 추가
    cnt += 1
  ## n이 k로 안 나눠지면
  else:
    ### 1번 방법 사용하고 결과 n에 대입
    n -= 1
    ### 횟수 추가
    cnt += 1

# 횟수 return
print(cnt)

답안 예시

---

3-5.py 단순하게 푸는 답안 예시

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

// N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)

 

나누어 떨어질 때는 나누고 나누어 떨어지지 않을 때는 1을 빼는 것은 같지만, 나의 경우 케이스를 두 가지로 나눠서 다르게 처리했다면 답안 예시는 나누는 것이 default이다. 즉, 나누어 떨어지면 계속 나누는 것이다. 왜냐하면 어떠한 수가 있을 때 K로 나누는 것이 1을 빼는 것보다 숫자를 훨씬 많이 줄일 수 있기 때문이다. 어느 풀이가 더 좋은지는 모르겠지만 이 답안 예시가 나보다 훨씬 더 그리디 알고리즘을 적용하려고 고민한 풀이였다.

3-6.py 답안 예시

# 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)

 

 

문제에서는 N의 범위가 10만 이하이므로, 3-5.py처럼 일일이 1씩 빼도 문제를 해결할 수 있다. 하지만 N이 100억 이상 큰 수가 되는 경우 시간 초과가 될 수 있으므로 3-6.py처럼 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 작성할 수 있다. 

 

사실 이 코드는 보자마자 바로 이해하기 어려웠다. 그래서 파이썬 튜터를 이용해 하나하나 추적해보며 이해했다. 이 문제는 1이 될 때까지 최소 횟수를 구하면 되는데 1일 때도 0으로 만들어서 최소 횟수에 +1을 하고 다시 -1 하는 과정이 불필요하다고 느껴졌다. 그리고 이 풀이를 과연 실전 상황에서 사용할 수 있을까 의문이 들었다.

 

# n,k 입력받기
n, k = map(int, input().split())
# 횟수 초기화
cnt = 0

while True:
  ## n이 k로 나눠질 때까지 1씩 빼기
  target = (n // k) * k
  # n이 1일 때 반복문 탈출
  if n == 1:
    break
  cnt += (n - target)
  n = target
  ## k로 나누기
  cnt += 1
  n //= k

# 횟수 return
print(cnt)

 

불필요한 것들을 빼보았다. 헷갈릴 수 있는데 cnt가 위의 답안 예시에 result에 해당한다. n이 k보다 작을 때 break 하는 것이 아니라 n이 1일 때 break 하도록 바꾸었고, 그렇다 보니 마지막으로 남은 수에 대하여 1씩 뺄 필요가 없어졌다. 이렇게 바꿔도 문제에서 사례로 든 두 케이스 모두 정상적으로 동작했다.

개념 정리

---

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

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

 

그리디 알고리즘의 경우 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해 준다. 이는 정렬 알고리즘을 사용했을 때 만족시킬 수 있어 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 책에 나온 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 따라서 처음에 문제를 만났을 때는 항상 최적의 해를 보장할 수 있을 때까지 이것저것 다양한 아이디어를 고려해야 한다.

 

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 이후 배우게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보는 것도 한 방법이다.

코드

---

GitHub - leeejihyun/algorithm: 알고리즘 문제 풀이

출처

---

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2021), p99-102