✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘
소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는Kotlin을 기반으로 작성하였습니다.
완전 탐색(Brute Force)
완전 탐색(Brute Force)은 가능한 모든 경우의 수를 직접 확인하여
정답을 찾는 방식의 알고리즘입니다.
이름 그대로 가능한 선택지를 하나도 빼놓지 않고 전부 확인하기 때문에,
문제를 가장 직관적으로 해결할 수 있는 방법 중 하나입니다.
조금 단순하게 표현하면 “정면 돌파”에 가까운 방식이라고 볼 수 있습니다.
복잡한 규칙이나 최적화 없이, 가능한 경우를 전부 시도해 보며 답을 찾는 것입니다.
정확도 100%
완전 탐색은 가능한 모든 경우를 확인하기 때문에,
구현만 올바르다면 정답을 놓치지 않습니다.
즉, 탐색해야 하는 모든 경우를 빠짐없이 검사하므로
정확도 측면에서는 매우 확실한 방법입니다.
다만 여기서 중요한 점은,
정답을 반드시 찾을 수 있다는 장점이 있는 대신
경우의 수가 많아질수록 시간 복잡도가 매우 커질 수 있다는 것입니다.
언제 사용할까?
일반적으로 완전 탐색은 다음과 같은 경우에 사용할 수 있습니다.
- 정답을 찾기 위해 모든 경우를 직접 확인해야 하는 경우
- 최적화보다도 가능한 모든 경우를 탐색하는 과정 자체가 중요한 경우
예를 들어,
- 가능한 모든 조합을 만들어 봐야 하는 경우
- 조건을 만족하는 모든 경우의 수를 세어야 하는 경우
- 입력 크기가 작아서 전부 확인해도 충분한 경우
에는 완전 탐색이 매우 유용합니다.
특히 문제의 입력 범위가 작다면
오히려 복잡한 알고리즘을 사용하는 것보다
완전 탐색으로 구현하는 편이 더 빠르고 실수도 적을 수 있습니다.
주의할 점
완전 탐색은 단순하고 확실한 방법이지만,
항상 사용할 수 있는 것은 아닙니다.
입력 크기가 너무 크거나,
확인해야 하는 경우의 수가 지나치게 많다면
시간 초과가 발생할 가능성이 큽니다.
예를 들어 예외 처리나 분기가 너무 많아지는 경우에도
구현이 복잡해질 수 있습니다.
따라서 완전 탐색을 사용할 때는 먼저 다음을 확인해야 합니다.
- 입력 크기가 충분히 작은지
- 모든 경우를 확인해도 시간 안에 가능한지
- 문제 자체가 구현 중심인지
즉, 완전 탐색은
“모든 경우를 확인해도 괜찮은 문제”에서 강력한 방법입니다.
또한 많은 경우 반복문과 조건문만으로도 구현할 수 있기 때문에
PS를 처음 공부할 때 접하게 되는 가장 기본적인 알고리즘 중 하나이기도 합니다.
Kotlin에서의 구현
완전 탐색은 보통 반복문, 조건문, 혹은 재귀 함수를 사용해 구현합니다.
가장 단순한 형태는 반복문을 통해 가능한 범위를 전부 확인하는 방식입니다.
예를 들어 배열에서 특정 조건을 만족하는 값을 찾거나,
모든 조합을 하나씩 검사하는 문제에서 자주 사용됩니다.
문제에 따라서는
- 반복문
- 중첩 반복문
- 재귀
- 백트래킹
형태로 확장되어 사용되기도 합니다.
즉, 완전 탐색은 하나의 고정된 구현 방식이라기보다
모든 경우를 빠짐없이 확인한다는 사고방식 자체에 가깝다고 볼 수 있습니다.
📌 결론
완전 탐색은 가능한 모든 경우의 수를 직접 확인하여 정답을 찾는 알고리즘입니다.
직관적이고 확실하다는 장점이 있지만, 경우의 수가 많아질수록 비효율적일 수 있습니다.
정리해 보면 다음과 같습니다.
- 완전 탐색은 가능한 모든 경우를 전부 확인합니다.
- 구현만 올바르면 정답을 놓치지 않습니다.
- 입력 크기가 작을 때 특히 유용합니다.
- 경우의 수가 너무 많아지면 시간 초과가 발생할 수 있습니다.
- 반복문, 조건문, 재귀 등을 통해 쉽게 구현할 수 있습니다.
완전 탐색은 이름만 보면 단순해 보이지만,
PS에서는 매우 자주 등장하는 기본적인 접근 방식입니다.
문제를 보았을 때 “이건 모든 경우를 다 보면 되겠구나”를 빠르게 판단할 수 있다면
문제 해결의 출발점을 훨씬 쉽게 잡을 수 있습니다.
