코딩 테스트에서 자주 등장하는 대표적인 그리디(Greedy) 문제를 Python으로 해결해 보겠습니다. 길이가 n인 costs 배열이 주어지며, 여기서 costs[i]는 i번째 아이스크림 막대의 가격을 의미합니다. 우리에게는 처음에 c개의 동전이 있으며, 이 동전으로 최대한 많은 아이스크림을 구매하는 것이 목표입니다.
예를 들어 입력이 costs = [3,1,4,5,2], c = 10이라면 출력은 4가 됩니다. 인덱스 0, 1, 2, 4에 해당하는 아이스크림을 구매하면 총 가격이 3 + 1 + 4 + 2 = 10이 되어 정확히 예산 안에서 4개를 살 수 있기 때문입니다.
문제 해결 접근 방식
핵심 아이디어는 간단합니다. 가장 저렴한 아이스크림부터 순서대로 구매하면 주어진 예산으로 최대 개수를 확보할 수 있습니다. 이러한 방법론을 그리디 알고리즘이라고 부르며, 매 순간 최선의 선택을 반복해 전체 최적해를 얻는 전략입니다.
구체적인 단계는 다음과 같습니다.
costs리스트를 오름차순으로 정렬합니다.인덱스 변수 i를 0으로 초기화합니다.
i가 리스트 길이보다 작고, 남은 동전 c가
costs[i]이상일 때까지 반복합니다.현재 아이스크림 가격만큼 c에서 차감합니다.
i를 1 증가시킵니다.
반복이 끝나면 i(구매한 아이스크림 개수)를 반환합니다.
Python 코드 구현
아래 예시 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(costs, c):
costs.sort()
i = 0
while(i < len(costs) and c >= costs[i]):
c = c - costs[i]
i = i + 1
return i
costs = [3,1,4,5,2]
c = 10
print(solve(costs, c))입력
[3,1,4,5,2], 10
출력
4
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 정렬 단계가 지배적이므로 O(n log n)입니다. 정렬 후에는 각 원소를 한 번씩만 확인하므로 선형 시간 O(n)으로 처리되며, 추가 메모리 사용 없이 제자리(in-place) 정렬을 활용하기 때문에 공간 복잡도 역시 효율적입니다.