브루트 포스 vs 그리디 알고리즘 (개념, 특징, 문제)

“브루트 포스” 알고리즘 이름을 처음 들었을 때는 이름부터 포스가 느껴졌습니다… ㅎ

하지만 한글로는 “완전 탐색” 말 그대로 for 문으로 순회하면서 확인, 연산하는 프로세스를 의미합니다.

“브루트 포스 알고리즘”이라는 개념을 몰라도 코딩 기초 과정에서 자연스레 사용했던 알고리즘이였던 것….!

그럼 이런 간단한 알고리즘은 사용하면 안되는 알고리즘일까요?

그리고 그리디 알고리즘은 무엇일까요? 브루트 포스랑 비슷한 알고리즘 일까요?

브루트 포스 (완전 탐색)

앞서서 모든 사례를 순회하면서 문제를 푸는 방식이라고 말씀드렸는데요. 가장 많이 드는 예가 암호 해독입니다.

위키에서 설명한 브루트 포스 예시입니다.

예를 들어, 4자리 숫자로 된 핸드폰의 암호는 0000, 0001, 0002… 9999까지 총 1만 개(10⁴)의 조합 중 하나이므로, 이를 하나씩 대입해 보면 핸드폰의 암호를 통과할 수 있게 된다. 한 번 암호를 입력해 보는 데 5초가 걸린다면, 5만 초, 즉 14시간이면 충분하고, 이를 사람 손이 아닌 컴퓨터로 처리할 수 있다면 1초 이내로 찾아낼 수 있게 되는 것이다.

브루트 포스 사용 이유

작은 input에서의 효율성

• 무차별 대입 알고리즘은 초보적인 것처럼 보일 수 있지만, 특히 작은 입력을 처리할 때 그 효율성은 타의 추종을 불허합니다.

단순성과 명확성

• 무차별 대입 알고리즘은 종종 간단하고 이해하기 쉽습니다. 문제 설명을 단계별 솔루션으로 직접 변환합니다.

초기 벤치마크

• 무차별 대입 솔루션은 보다 최적화된 알고리즘에 대한 벤치마크 역할을 할 수 있습니다.
• 먼저 무차별 솔루션을 구현함으로써 개발자는 문제의 구조에 대한 통찰력을 얻은 다음 보다 효율적인 전략을 탐색할 수 있습니다.

브루트 포스의 단점

대량 입력의 비효율성

• 입력 크기가 크게 커지면 무차별 대입 솔루션이 실용적이지 않게 됩니다. 대규모 데이터 세트의 경우 철저한 검색의 시간 및 공간 복잡성이 엄청나게 커질 수 있습니다.

복잡한 문제에는 적합하지 않음

• 복잡한 구조의 문제나 고급 최적화 기술이 필요한 문제의 경우 무차별 대입이 가장 적합하거나 효과적인 접근 방식이 아닐 수 있습니다.

브루트 포스 문제

https://www.acmicpc.net/problem/2566

https://www.acmicpc.net/problem/2563

2798번: 블랙잭 (acmicpc.net)

그리디 알고리즘 ?

본질적으로 그리디 알고리즘은 전역적으로 최적의 솔루션으로 이어질 것이라는 희망을 가지고 각 단계에서 가능한 최선의 선택을 하는 패러다임입니다.

향후 결과를 고려하지 않고 우선 각 단계에서 가능한 최선의 선택을 한다는 게 가장 핵심 개념인 것 같습니다.

하지만 각 단계에서는 최적의 선택이지만 이를 반복하더라도 전체적(global)으로는 최적의 해가 아닐 수 있다는 점에 유의 해야 할 것 같습니다

그리디 알고리즘 장점

최적의 해를 보장할 수 없음에도 Greedy 알고리즘을 사용하는 이유는 해당 알고리즘의 계산 속도가 매우 빠르기 때문입니다.

그리디 알고리즘 특징

greedy choice property

각 단계에서 선택하는 사항은 향후 선택에 영향을 주지 않습니다.

예를 들어 계단을 이용해서 정상에 오르는 게 목표라면 당장은 내려가는 계단보다 오르는 계단만 선택하면 되는 것 입니다.

정상을 위해 앞의 앞 계단, 앞의 앞의 앞 계단은 무엇일지 이런 것은 생각하고 선택하지 않는 경우 입니다.

optimal substructure

문제의 각 작은 부분에 대한 최상의 솔루션이 최상의 전체 솔루션으로 이어집니다.

예를 들어 자동차 여행을 한다고 가정하면, 모든 교차로에서 가장 빨라 보이는 길을 선택한다면, 결과적으로 전체적으로 빠른 경로를 제공하는 경우여야 합니다.

그리디 알고리즘, DP, 백트래킹

공부를 하다 보면 이후에 나오는 DP, 백트래킹과 유사한 점이 있어서 처음 접하면 약간의 혼동이 옵니다.
(자세한 정리는 뒤에 DP와 백트래킹을 공부하면서 진행 예정…)

현재 알고 있는 수준에서 DP, 백트래킹과 비교했을 때, 그리디 알고리즘만의 우선 특징을 정리해보았습니다.

메모리 사용량

• 백트래킹과 DP는 선택사항 저장, 재사용을 위해 메모리를 사용하지만 그리디는 그때 그때 최적의 해를 선택하기 때문에 최소한의 메모리가 필요하다는 점

최적성

• 그리디는 각 단계에서 지엽적으로 최적의 선택을 하다보니 최종적으로 글로벌한 최적해로 이어지지 않을 수도 있다는 점

그리디 문제

11399번: ATM (acmicpc.net)

1931번: 회의실 배정 (acmicpc.net)

11047번: 동전 0 (acmicpc.net)

2875번: 대회 or 인턴 (acmicpc.net)

10610번: 30 (acmicpc.net)

1783번: 병든 나이트 (acmicpc.net)

11000번: 강의실 배정 (acmicpc.net)

1969번: DNA (acmicpc.net)

1700번: 멀티탭 스케줄링 (acmicpc.net)

참고하면 좋은 글