🐨코알라 오딧세이
글 목록
개발

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

나동빈 님의 '이것이 취업을 위한 코딩테스트다 with 파이썬'을 바탕으로 시간 복잡도, Big-O 표기법, 그리디 알고리즘을 정리하고 거스름돈·큰 수의 법칙 문제를 풀어봅니다.

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

프로그래밍/코딩 공부 시리즈 : 알고리즘 기초

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

1. 복잡도

코딩에서 어떻게 보면 가장 중요한 요소입니다. 복잡도는 알고리즘의 성능을 나타내는 척도로, 크게 두 가지로 나뉩니다.

  • 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미합니다.
  • 공간 복잡도: 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미합니다.

즉, 이 두 가지가 낮을수록 좋은 알고리즘입니다.

두 복잡도는 일종의 Trade-Off 관계입니다. 메모리를 조금 더 사용하면 반복 연산을 줄일 수 있어 시간 복잡도가 감소합니다. 메모리를 더 소모하는 대신 시간 이점을 얻는 대표적인 방법으로 메모이제이션(Memoization) 이 있습니다.

Big-O 표기법

시간 복잡도(및 공간 복잡도)를 표현할 때 주로 Big-O 표기법을 사용합니다. 빠르게 증가하는 항만을 고려하여 표기하는 방법입니다.

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

시간과 메모리 측정을 간단하게 하는 방법은 아래 코드와 같습니다.

import time
start_time = time.time()

# ... 알고리즘 코드 ...

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

2. 그리디(Greedy)

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 coin in coin_types:
        count += N // coin
        N %= coin

    return count

counter(1260)

두 풀이 모두 시간복잡도는 O(k) 입니다. 실제 풀이는 동전 종류를 리스트로 관리하여 반복문 하나로 간결하게 처리한 것이 핵심입니다.

문제 2) 큰 수의 법칙

문제

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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 = 0
result += count * first
result += (m - count) * second

print(result)

문제를 일부 잘못 해석한 부분이 있었습니다. 두 번째로 큰 수를 구할 때 저는 set()으로 중복을 제거했는데, 문제에서는 서로 다른 인덱스에 해당하는 수가 같아도 서로 다른 것으로 간주합니다. 예를 들어 [1, 2, 2, 3, 3, 3]에서 두 번째로 큰 수는 3이지만 저는 2를 택하는 실수가 있었습니다. 실제 풀이처럼 인덱스 기준(data[n-1], data[n-2])으로 접근하는 것이 올바릅니다.

댓글

0 / 1000