1. 그리디 (Greedy)

그리디는 매 순간 가장 좋아보이는 것을 선택하여 미래의 영향은 고려하지 않는 알고리즘이다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하기 때문에 보통 가장 큰 순서대로, 가장 작은 순서대로 같은 기준이 있으면 그리디를 사용하면 된다. 그리고 정렬을 해야 그리디가 가능하기 때문에 정렬하는 것도 잊지 말아야 한다.

가장 쉬운 그리디 문제로 거스름돈 계산이 있다. 거슬러 줘야 할 돈이 n일때, 거슬러 줘야 할 동전의 최소 개수를 구하는 문제이다.

n = 1260
cnt = 0

coin_types = [100, 500, 50, 10]
coin_types.sort(reverse=True)  # 화폐의 단위가 큰 것 부터 확인하기 위해 내림차순 정렬

# O(K)
for coin in coin_types:
    cnt += n // coin
    n %= coin
    
print(cnt)

이때 가지고 있는 동전의 큰 단위가 작은 단위의 배수 형태이기 때문에 그리디를 사용할 수 있다. 만약 화폐의 단위가 무작위로 주저진 경우에는 다이나믹 프로그래밍을 사용해야 한다.

2. 구현 (Implementation)

구현 문제는 풀이를 떠올리기 쉽지만 코드로 옮기기 어렵다. 사소한 조건들이 많거나, 실수 연산, 문자열 끊어서 처리 등 적절한 라이브러리 찾아서 사용해야 하는 문제들이 구현 문제에 해당한다. 즉, 완전 탐색이나 시뮬레이션 문제들이 구현에 해당한다.

완전 탐색은 모든 경우의 수를 다 계산하는 방법이고, 시뮬레이션은 문제에서 제시한 알고리즘을 차례대로 수행하는 방법이다.

3. 알고리즘 설계 및 시간제한

코딩 테스트에서 시간제한은 보통 1초~5초 정도이다. 시간 제한이 1초인 문제에서 일반적인 기준은 다음과 같다.

• N <= 500 : $O(N^{3})$
• N <= 2,000 : $O(N^{2})$
• N <= 100,000 : $O(NlogN)$
• N <= 10,000,000 : $O(N)$

시간과 메모리 측정

파이썬에서 프로그램의 수행 시간과 메모리 사용량을 확인하는 방법은 아래와 같다.

import time
from random import randint

start_time = time.time()  # 현재 시간으로 측정 시작

array = []
for _ in range(1000):
    array.append(randint(1, 100))  # 1부터 100 사이의 랜덤한 정수 배열에 삽입

end_time = time.time()  # 현재 시간으로 측정 종료

print('time :', end_time-start_time)  # 수행시간 출력
# time : 0.000997304916381836