✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘
소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는Kotlin을 기반으로 작성하였습니다.
들어가기 전
일반적으로 프로그래밍 문제는 단순한 구현 방식으로도 해결할 수 있습니다.
하지만 단순 구현은 조건문, 반복문, 재귀 호출이 많아질수록 시간 복잡도가 커질 수 있습니다.
즉, 입력 크기가 작을 때는 구현만으로도 충분하지만,
데이터의 범위가 커질수록 더 빠른 해결 방법이 필요해집니다.
한편 어떤 문제들은 이전 계산 결과를 재사용하여 해결할 수 있는데,
이러한 방식은 동적 계획법(Dynamic Programming, DP) 에서 자주 등장합니다.
다만 DP 역시 모든 문제에 사용할 수 있는 것은 아니며,
상태의 개수가 많아지면 시간 복잡도와 공간 복잡도가 함께 커질 수 있습니다.
즉, “항상 빠르다”기보다 문제의 성질에 맞을 때 강력한 방법이라고 보는 것이 더 정확합니다.
이처럼 문제마다 적절한 접근 방식이 다르며,
그중 하나가 바로 탐욕법(Greedy Algorithm) 입니다.
탐욕법
탐욕법(Greedy)은 매 순간 가장 좋아 보이는 선택을 하면서 답을 구해 나가는 알고리즘입니다.
즉, 현재 상황에서 가장 최선이라고 판단되는 선택을 반복하여
전체 문제를 해결하는 방식입니다.
예를 들어,
- 지금 당장 가장 큰 값을 선택하거나
- 가장 빨리 끝나는 작업을 먼저 고르거나
- 가장 큰 단위부터 사용하는 방식
등이 모두 탐욕적 선택의 예시가 될 수 있습니다.
그리디 알고리즘의 핵심
그리디 알고리즘은 단순히 “가장 큰 것부터 고르면 된다”는 뜻이 아닙니다.
중요한 것은 매 순간의 최선의 선택이 전체 문제의 최적해로 이어지는지입니다.
즉, 그리디 알고리즘에서 가장 중요한 것은 다음 두 가지입니다.
- 현재 선택이 가장 좋아 보여야 합니다.
- 그 선택을 반복해도 최종적으로 정답이 되어야 합니다.
그래서 그리디 문제를 풀 때는
단순히 코드를 빨리 짜는 것보다도,
왜 이 선택이 정답이 되는지 설명할 수 있는 정당성이 필요합니다.
이 정당성이 없다면,
겉보기에는 좋아 보이는 선택이 실제 정답으로 이어지지 않을 수도 있습니다.
정리하면, 그리디 알고리즘은
- 구현은 비교적 단순한 편이지만
- 문제를 그리디로 풀 수 있는지 판단하는 것이 더 어렵고
- 반드시 정답이 되는 이유를 설명할 수 있어야 하는 알고리즘
이라고 볼 수 있습니다.
BOJ 5585
이제 그리디 알고리즘의 대표적인 예시로
백준 5585번 문제를 살펴보겠습니다.
이 문제는 1000엔을 내고 물건을 샀을 때,
거스름돈을 가장 적은 동전 개수로 주는 문제입니다.
사용할 수 있는 동전은 다음과 같습니다.
500엔100엔50엔10엔5엔1엔
이 문제는 큰 단위의 동전부터 최대한 사용하는 것이
항상 동전 개수를 최소로 만드는 구조이기 때문에
그리디 알고리즘으로 해결할 수 있습니다.
in Kotlin
import java.io.StreamTokenizer
fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
fun nextInt(): Int {
nextToken()
return nval.toInt()
}
var change = 1000 - nextInt()
val money = intArrayOf(500, 100, 50, 10, 5, 1)
var ans = 0
for (coin in money) {
ans += change / coin
change %= coin
}
print(ans)
}코드 설명
위 코드는 다음과 같은 흐름으로 동작합니다.
- 사용자가 지불한 금액을 입력받습니다.
1000 - 입력값을 통해 거스름돈을 계산합니다.- 큰 단위의 동전부터 차례대로 확인합니다.
- 현재 거스름돈에서 해당 동전을 몇 개 사용할 수 있는지 계산합니다.
- 사용한 개수는 정답에 더하고, 남은 금액은 다음 동전으로 넘깁니다.
예를 들어 거스름돈이 380엔이라면,
500엔은 사용할 수 없습니다.100엔은3개사용할 수 있습니다.- 남은 금액은
80엔입니다. 50엔은1개사용할 수 있습니다.- 남은 금액은
30엔입니다. 10엔은3개사용할 수 있습니다.
이처럼 큰 단위부터 차례대로 선택해도
항상 최적해가 보장되는 구조이기 때문에
이 문제는 그리디 알고리즘으로 해결할 수 있습니다.
왜 정렬이 중요할까?
이 문제에서 핵심은 동전 배열을 큰 단위부터 작은 단위 순서로 확인하는 것입니다.
큰 동전을 먼저 최대한 사용해야
전체 동전 개수를 줄일 수 있기 때문입니다.
즉, 이 문제에서는 단순히 배열이 주어졌다고 해서 끝이 아니라,
어떤 순서로 선택할 것인지가 중요합니다.
다만 모든 문제에서 “정렬만 하면 그리디가 된다”라고 생각하면 안 됩니다.
정렬은 그리디 구현에 자주 사용되는 도구일 뿐이고,
핵심은 여전히 그 선택이 항상 정답이 되는지입니다.
📌 결론
그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하며
빠르게 정답을 구해 나가는 알고리즘입니다.
정리해 보면 다음과 같습니다.
- 그리디는 현재 단계에서 최선의 선택을 반복하는 방식입니다.
- 구현은 비교적 단순한 경우가 많습니다.
- 하지만 항상 정답을 보장하는 것은 아닙니다.
- 따라서 왜 이 선택이 맞는지에 대한 정당성이 반드시 필요합니다.
- 문제에 따라 정렬이 중요한 역할을 하기도 합니다.
즉, 그리디 알고리즘의 핵심은
단순히 “가장 큰 것부터 고른다”가 아니라,
그 선택이 끝까지 이어져도 전체 최적해가 된다는 점을 증명할 수 있어야 한다는 것입니다.
