코딩 공부 - 시간 복잡도, 그리디, 문제 풀이(1)

입사한지 약 11개월 차에 접어들었습니다. 지금까지 일에 치여 사느라 중요한걸 잊고 살았던 부분이 있었던 것 같습니다. 사실 AI 개발자로 일을 하면서 가장 중요한 것 중 하나는 파이썬 코딩을 잘 하는 것이라고 생각합니다. 그동안 이에 대해서 등한시 했던 것 같습니다. 그래서 앞으로 몇 달간 나동빈 님의 "이것이 취업을 위한 코딩테스트다 with 파이썬" 이라는 책을 보면서 다시 파이썬의 기초를 되새김질 하는 시간을 가지고자 합니다. 

 

1. 복잡도 

코딩을 하는데에서 어떻게 보면 가장 중요한 요소입니다. 이는 알고리즘의 성능을 나타내는 척도인데 시간 복잡도 및 공간 복잡도로 나뉠 수 있다고 합니다. 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미합니다. 공간 복잡도의 경우 특정한 크기의 입력에 대해서 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미합니다. 즉, 이 두가지가 낮을수록 좋은 알고리즘을 의미합니다. 

 

이 두가지 복잡도가 일종의 Trade-Off 관계라고 합니다. 예를 들어 메모리를 조금 더 사용하면 대신 반복 연산을 줄일 수 있기 때문에 시간 복잡도는 감소합니다. => 이 때 메모리를 더 소모하는 대신에 얻을 수 있는 시간 이점이 있는 경우가 많은데 이런 방법 중 메모이제이션이 있다고 합니다.

 

시간 복잡도를 표현할 때 주로 Big-O 표기법을 많이 사용하는데 이를 해당 서적에서는 빠르게 증가하는 항만을 고려하는 표기하는 방법이라고 정의되어 있습니다.(엄밀한 정의는 아님)

 

Big-O 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^N)	지수 시간

 

공간 복잡도를 표현할 때 역시 Big-O 표기법을 활용한다고 합니다. 시간이 메모리로 표현된다는 다른 점이 있습니다. 

 

시간과 메모리 측정을 간단하게 하는 방법은 아래의 코드와 같습니다. 물론 이 부분은 역시 모두가 잘알고 있으실 것이라고 생각합니다. 

import time 
start_time = time.time()

end_time = time.time()
print("time :", end_time - start_time)

 

 

2. 그리디 

Greedy 알고리즘은 어느 책을 가든 처음으로 등장하는 어쩌면 단순하지만 강력한 문제 해결 방법입니다. 보통은 한국어로 탐욕법이라고 표현되는데요. 말그대로 어떠한 문제가 있던간에 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이라고 합니다.  이를 제 생각대로 번역을 하면 큰 설계 과정을 거치지 않고 그때 그때 좋아 보이는 것만 고르는 방식이라고 정의해볼 수 있는데요. 

 

1) 거스름돈 예제 

 

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 있다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라 단, 거슬러줘야 할 돈 N원은 항상 10의 배수이다. 

 

(1) 내 풀이 

def counter(N):
    if N % 10 == 0:
        five = N // 500 
        hundread = (N - 500* five) // 100
        fifty = (N - 500* five - 100*hundread) // 50
        ten = (N - 500* five - 100*hundread- 50*fifty) // 10
        return five + hundread + fifty + ten
    else:
        return '잘못된 금액입니다'

print(counter(1260)) #6

 

일단 생각나는데로 코드를 작성해보았는데,  실제 답변을 보니 더 간단하게 짤 수 있는 방법이 있는데 이렇게 짜버렸다... 

 

(2) 실제 답변

def counter(N):
	count = 0 
    coin_types = [500,100,50,10]
    
    for coins in coin_types:
        count += N// coins
        N %= coin
       
counter(1260)

 

둘다 시간복잡도는 O(k) 입니다. 그리디 알고리즘의 경우 모든 알고리즘에 적용할 수 있는 것은 아니라고 합니다. 즉, 어떤 문제에서는 그리디 알고리즘을 활용한다면 최적의 해를 구할 수 없는 경우가많다고 합니다. 그러나 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있을 가능성이 매우 높은 경우 가장 효과적이라고 합니다. 

 

2) 큰 수의 법칙 

 

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

 

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정한다. 예를 들어 순선대로 2, 4, 5, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 +6 +5인  46이 된다.

 

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이가능하다. 결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4인 28이 도출된다.

 

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오. 

 

입력 조건

1. 첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.

3. 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

출력 조건

첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

 

입력 예시

5 8 3

2 4 5 4 6

 

출력 예시

46

 

(1) 내 풀이 

arr1 = list(map(int, input().split(' ')))
# 두 번째 줄 읽기
arr2 = list(map(int, input().split(' ')))

def big_num(arr1, arr2):
    n,m,k = arr1 
    if len(arr2) == n:
        max_num = sorted(set(arr2))[-1]
        max_num2 = sorted(set(arr2))[-2]
        answer = max_num * k * (m//k) + max_num2 * (m%k)
        return answer
    else:
        return '입력을 다시 확인해주세요'
        
print(big_num(arr1, arr2))

 

(2) 실제 풀이 

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

data = list(map(int, input().split()))

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

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

result = 9
result += count * first
result += (m-count) * second

 

문제를 일부 잘못 해석한 부분이 있는 것 같긴합니다. (전체에서 두번째로 큰 수를 예를 들어 1, 2,2, 3,3, 3 이라고 하면 문제는 3을 저는 2를 택했습니다.)