[이코테] 3. 그리디 알고리즘 - 1이 될 때까지
Algorithm/이코테2021

[이코테] 3. 그리디 알고리즘 - 1이 될 때까지

반응형

 

 

그리디 알고리즘 - 1이 될 때까지

 

 

문제 설명

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다.

단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.

  1. N에서 1을 뺍니다.
  2. N을 K로 나눕니다.

예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다.

이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다.

결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다.

 

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

 

난이도 표기 잘못된 것 같은데요,, ㅜ^ㅜ

 

 

 

문제 해결 아이디어

주어진 N에 대하여 "최대한 많이 나누기"를 수행하면 됨.

  • 1을 빼는 것 보다 2 이상으로 나누는 작업이 N을 훨씬 많이 줄일 수 있음.
    • N = 25, K = 3일 때 예시. 

N = 25, K = 3일 때 예시.

 

 

 

정당성 분석

가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있을까?

 : N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있음.

   다시 말해, K가 2이상이기만 하면, K로 나누는 것이 1을 빼는 것 보다 항상 빠르게 N을 줄일 수 있음.(최적의 해 성립)

 

 

 

복습 도중 틀린 부분

int(input().split())이라고 사용했는데

TypeError: int() argument must be a string, a bytes-like object or a number, not 'list'라는 에러가 돌아왔다.

int(input().split())가 아니라, map(int, input().split())임을 기억하자.

 

 

 

 

소스 코드

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)

위 코드가 더 직관적으로 이해가 쉬움.문제에서 N의 범위가 10만 이하이므로, 위 처럼 문제 해결할 수 있음.

 

 

그러나, N이 100억 이상으로 큰 수가 되는 경우에 시간복잡도를 log로 줄이는 테크닉이 필요함.N이 K의 배수가 되도록 '효율적으로' 한 번에 빼는 방식으로 아래와 같이 작성 가능.

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

result = 0

while True:
  # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기  
    target = (n // k) * k # n이 k로 나누어 떨어지는 값 = target
    result += (n - target) # n - target = 나머지, 즉 나머지를 result에 넣는다.
                           # 즉, 1을 빼는 연산을 몇 번 수행할 지에 대한 내용.
    n = target # 1씩 뺀 값인 target으로 n을 최신화

    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
      break
    
    # k로 나누기
    n //= k# n을 k로 나눈다.
    result += 1

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

나는 여기서 "# 마지막으로 남은수에 대하여 1씩 빼기" 이 부분이 너무 와닿지가 않았음.(이해가 안됬음)

'왜 남은 수에 대해서 1씩 빼는거지?' 그리고 '왜 저런식으로 빼지?' 에 대한 대답이 안나오는 상태였음.

 

 

그래서,

n=26, k=5라고 가정하고 손으로 시퀀스를 따라가보니까 이해가됨.

이 시퀀스의 결론은, result에 1이 한번 더 더해졌기 때문에 22번에서 1을 한번 빼주는 것이다.

while문이 if break문(14~15번)을 만나기 전에  7~11번을 한번 수행하게 짜여져있음.

그래서 7~11번을 수행한 결과, result에 +1이 되어짐.

그래서 22번에서 result에 -1을 한번 해주는 것임.

 

이 말이 이해가 안된다면

나 처럼 손으로 적으면서 while문을 느껴보면 바로 이해 될 것이다.

 

 

 

 

 

이코테 2021 시리즈 씹어먹기 by 조랭이떡

시리즈 목차

더보기
  1. 코딩테스트 출제 경향 및 알고리즘 성능 평가
  2. 파이썬 문법 부수기
    1. 수, 리스트 자료형
    2. 문자열, 튜플, 사전, 집합 자료형
    3. 기본 입출력
    4. 조건문
    5. 반복문
    6. 함수와 람다 표현식
    7. 자주 사용되는 표준 라이브러리
  3. 그리디
    1. 그리디 알고리즘이란?
    2. 거스름돈
    3. 1이 될 때 까지
    4. 곱하기 혹은 더하기
    5. 모험가 길드
  4. 구현
  5. DFS & BFS (추후링크)
  6. 정렬 알고리즘 (추후링크)
  7. 이진 탐색 (추후링크)
  8. 다이나믹 프로그래밍 (추후링크)
  9. 최단 경로 알고리즘 (추후링크)
  10. 기타 그래프 이론 (추후링크)
  11. 코딩 테스트에서 자주 출제되는 기타 알고리즘 (추후링크)
  12. 개발형 코딩 테스트 (추후링크)

 

반응형

    티스토리툴바