그리디 알고리즘 (2) / 큰수의법칙, 숫자카드게임, 1이될때까지

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 

본 포스팅에서 작성한 코드문제는 해당 저서에 나와있는 문제 일부입니다.

---

https://westshine-data-analysis.tistory.com/30

그리디 알고리즘 (1) / 그리디 알고리즘이란

▷ 동빈이의 큰 수의 법칙 

 

1. 아이디어: 가장 큰 수를 M//K * K만큼 더할 수 있다. 그 외 남은 나머지 횟수만큼은 두번째로 큰수로 더한다. 만약 배열에 가장 큰 수가 중복되면 중복된 수만큼 더 반복하여 더할 수 있다. 따라서 가장 큰 수가 배열 내에 몇 개 있는지 확인하고 그 수를 K에 곱해줄 수 있다. 

 

2. 정당성 검증: 항상 최적의 해가 나오기 위해선 최대값이 반복될 수 있는 점을 고려해야한다. 또한 배열에서 max값을 찾을 때 두번째 max값을 찾기 위해 기존의 max값은 배열에서 제거하고 max함수를 취해줘야한다. 

 

> 내가 생각한 코드

import time
start= time.time()

n,m,k = map(int, input().split())
lst= list(map(int, input().split()))

k *= lst.count(max(lst))
print(m//k * k * lst.pop(lst.index(max(lst))) + m%k * max(lst))

end= time.time()
print(end- start)

10.78512454032898 소요

 

> 답안 예시코드

import time
start= time.time()

n,m,k = map(int, input().split())
lst= list(map(int, input().split()))

lst.sort()
first= lst[n-1]
second= lst[n-2]

cnt= int(m/(k+1)) * k
cnt += m%(k+1)

result=0
result += (cnt) * first
result += (m-cnt) * second

print(result)

end= time.time()
print(end- start)

5.796936511993408

 

> 예시답안과 아이디어는 동일했다. 코드길이는 내가 작성한 코드의 길이가 더욱 짧았음에도 예시 코드와 비교해보았을 때 시간은 거의 2배가량 차이났다. 가장 큰 이유는 max(lst)와 같이 반복되는 함수와 그 외의 함수사용이 예시코드 보다 많았기 때문일 것이다. 예시코드는 볼 수 있다싶이 가장 필요한 함수 연산 이외에 기본연산으로 문제를 풀었다. 가능한 필요한 함수만 추려 사용하고 반복사용하는 것을 피해야겠다. 

 

 

▷ 숫자카드 게임

1. 아이디어: 2차원 배열에서 각 행마다 최소값을 뽑고 그 최소값들 중 가장 최대값을 뽑는다. 최소값을 특정 변수에 넣어두고 다른 행들의 최소값이 넣어둔 값보다 크면 해당 값으로 변수에 들어있는 값을 바꾸도록한다

 

> 내가 작성한 코드

start= time.time()


n,m= map(int, input().split())
result=0 
for i in range(n):
    lst= list(map(int, input().split()))
    val= min(lst)
    if result < val:
        result= val
print(result)

end= time.time()
print(end- start)

10.494086980819702 소요

 

> 예시 답안 코드

start= time.time()

n,m= map(int, input().split())
result=0 
for i in range(n):
    lst= list(map(int, input().split()))
    val= min(lst)
    result= max(result, val)
print(result)

end= time.time()
print(end- start)

8.355951070785522 소요

 

> 두 코드에서 다른 부분은 행의 최소값 중에서 최대값을 구하는 부분이다. 나는 조건문을 통해 풀었지만 예시에선 max함수를 사용해 result값을 최대값으로 바꿔주었다. 2초 정도의 차이가 나는 것으로 보아 해당 문제에선 조건문보다는 max()함수의 시간복잡도가 더 적은 것으로 보인다. 

 

 

▷ 1이 될 때까지

1. 아이디어: N이 K로 나눠떨어지는 수가 될때까지 1번 과정을 반복하다 그 수가 되면 2번 과정에서 N을 K로 나눈 나머지가 1이 될때까지 반복한다. 

 

> 내가 작성한 답안

n,k = map(int, input().split())
result = 0 
while n%k != 0:
    n -= 1
    result +=1 
while n != 1:
    n = n// k
    result += 1
print(result)

> 나는 우선 n이 k로 나눠떨어지는 수가 될때까지 1씩 빼는 과정을 먼저 수행했는데 만약 N이 10만 이상의 수가 되면 1씩 먼저 빼는 연산에 많은 시간이 소요될 것이다. 예시 답안에서는 먼저 n을 k로 가능한 한 많이 나눈 후 나눠떨어지지 않을 때 1씩 빼주는 방법을 소개한다. 구조는 내가 짠 것과 상당히 비슷하지만 N이 아주 큰 수일 때의 시간복잡도를 고려했을 때 예시답안이 더 효율적인 답안이 될 것이다.