1. 알고리즘 기초
1-2. 완전탐색과 그리디 알고리즘
1. 완전탐색
완전 탐색은 가능한 모든 경우의 수를 전부 확인하여 문제를 해결하는 방법
쉽게 말해 "가능한 모든 방법을 일일이 다 해보는 것"
-
완전 탐색의 장단점
-
장점
- 구현이 단순하고 이해하기 쉽습니다.
- 모든 경우를 확인하므로 반드시 정답을 찾을 수 있습니다.
- 문제를 처음 접근할 때 좋은 시작점이 됩니다.
-
단점
- 모든 경우를 확인하므로 실행 시간이 오래 걸립니다.
- 예: 비밀번호가 4자리면 10000가지, 5자리면 100000가지…
- 경우의 수가 많아지면 현실적으로 해결이 어려울 수 있습니다.
- 모든 경우를 확인하므로 실행 시간이 오래 걸립니다.
-
완전 탐색은 모든 문제 해결의 기본이 되는 좋은 시작점입니다. 하지만 문제의 복잡도가 높아지거나 처리해야 할 데이터의 양이 늘어날수록 실행 시간이 기하급수적으로 증가하게 됩니다. 따라서 코딩 테스트에서는 상황에 맞는 최적화된 알고리즘(그리디, 백트래킹, 동적 계획법 등)을 선택하여 문제를 해결해야합니다. 즉, 완전 탐색은 문제의 크기와 상황을 고려하여 전략적으로 사용해야 합니다.
반복문을 이용한 완전 탐색
- 반복문으로 완전 탐색을 구현하는 방법
반복문을 이용한 완전 탐색은for문이나while문을 사용하여 가능한 모든 경우를 순차적으로 탐색하는 방법 - 기본 구현 방법
- 문제에서 주어진 범위나 조건을 파악
- 해당 범위 내의 모든 경우를 반복문으로 확인
- 각 경우마다 문제의 조건을 만족하는지 검사
- 반복문으로 완전 탐색을 구현하는 방법
2. 그리디 알고리즘 (Greedy Algorithm)
그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 하는 방법
쉽게 말해 "각 단계에서 최적이라고 생각되는 것을 선택하는 것"
-
그리디 알고리즘의 장단점
- 장점
- 구현이 비교적 단순하고 실행 속도가 빠릅니다.
- 직관적이어서 이해하기 쉽습니다.
- 현재 상황에서 가장 좋은 것을 고르는 단순한 전략입니다.
- 단점
- 항상 최적의 해를 보장하지는 않습니다.
- 각 단계에서의 최적의 선택이 전체적인 최적 해결책이 아닐 수 있습니다.
- 적용할 수 있는 문제의 유형이 한정적입니다.
- 장점
-
그리디 알고리즘의 두 가지 필수 조건
-
탐욕 선택 속성
각 단계에서 선택한 방법이 이후의 결정과 상관없이 최종 답의 최적성을 유지해야 합니다.
예시) 회의실 배정 문제
[회의 시간표] A팀: 1시~4시 B팀: 3시~5시 C팀: 5시~7시 [선택 과정] 첫 선택: "가장 빨리 끝나는" A팀 선택 -A팀이 4시에 끝나기 때문에 이후 시간대에 더 많은 회의를 배정할 수 있음 -이 선택이 "최대 회의 수"라는 최종 목표 달성에 최선! -
최적 부분 구조
전체 문제의 최적해가 문제를 나눈 각 부분 문제의 최적해를 결합해서 얻을 수 있어야 합니다.
예시) 거스름돈 문제
[상황] 거스름돈 1260원 (동전: 500원, 100원, 50원, 10원) [해결 과정] 1.가장 큰 단위(500원)로 최대한 거스름돈을 해결 → 500원 2개 사용 2.남은 금액(260원)을 같은 방식으로 해결 - 100원 2개 → 200원 - 50원 1개 → 50원 - 10원 1개 → 10원 각 단계의 "최대한 큰 동전 사용하기"의 결과가 모여서 전체 문제의 "최소 동전 개수"라는 최적해를 만듬
-
- 두 조건의 차이점
탐욕 선택 속성: 문제 해결 과정에서 현재 선택의 정당성을 보장하는 것이 중요합니다.
- "각각의 선택"에 초점최적 부분 구조: 문제를 분할하여 최적해를 조합할 수 있는 구조인지 확인해야 합니다.
- "문제의 구조"에 초점
이 두 조건이 모두 만족되어야 그리디 알고리즘을 사용할 수 있습니다!
만족하지 않으면 다른 알고리즘(완전 탐색, 동적 계획법 등)을 고려해야 해요.
그리디 알고리즘 증명 방법
- 그리디 알고리즘으로 해결할 수 있는지 증명해야 해요.
❗ 문제를 그리디 알고리즘으로 해결할 수 있는지 증명
1. 수학적 증명
-
"가장 확실한 증명 방법이지만, 난이도가 높습니다"
``` [귀류법을 통한 회의실 배정 문제 증명 예시] * 귀류법: 어떤 명제가 참임을 증명하기 위해, 그 명제가 거짓이라고 가정한 후 모순을 이끌어내는 증명 방법입니다. 1단계) 가정 - "가장 일찍 끝나는 회의(A)를 선택하지 않는 최적해가 있다"고 가정 2단계) 최적해 분석 - 최적해의 첫 회의를 B라고 하자 - B의 종료 시간은 A의 종료 시간보다 늦거나 같음 3단계) 교체 가능성 증명 - B를 A로 교체해도: * 회의 시간이 겹치지 않음 (A가 더 일찍 끝나므로) * 나머지 회의 일정에 영향 없음 * 그런데 A를 선택하면 오히려 더 많은 시간을 확보할 수 있음 4단계) 결론 - B를 A로 교체 후 상황 분석 * 최소한 같은 개수의 회의를 진행할 수 있음 * 더 많은 시간이 확보되어 더 많은 회의가 가능할 수도 있음 - 최종 증명 * "A를 선택하지 않는 것이 최적"이라는 가정이 모순 * "가장 일찍 끝나는 회의(A)를 선택하는 것이 최적해"임이 증명됨 ```
2. 작은 예시로 검증
- "다양한 크기의 입력값으로 직접 테스트"
``` [동전 거스름돈 문제 검증] 테스트 케이스 1: 작은 금액 - 상황: 160원 - 과정: 1) 100원 1개 (남은 금액: 60원) 2) 50원 1개 (남은 금액: 10원) 3) 10원 1개 - 결과: 3개의 동전 사용으로 최적해 테스트 케이스 2: 각 동전의 배수 - 상황: 500원 - 결과: 500원 1개로 최적해 테스트 케이스 3: 모든 동전 필요 - 상황: 660원 - 과정: 1) 500원 1개 (남은 금액: 160원) 2) 100원 1개 (남은 금액: 60원) 3) 50원 1개 (남은 금액: 10원) 4) 10원 1개 - 결과: 4개의 동전이으로 최적홰 ```
3. 반례 찾기
-
"그리디 알고리즘이 실패하는 경우 찾기"
``` [잘못된 동전 구성의 반례] 상황: 동전 {500원, 400원, 100원}으로 800원 거슬러주기 그리디 방식: 1) 500원 선택 (남은 금액: 300원) 2) 100원 3개 사용 → 총 4개 동전 사용 최적해: 1) 400원 2개 사용 → 총 2개 동전으로 해결 가능 결론: 이런 반례가 있다면 그리디 접근이 부적절 ```
4. 기존 문제와의 비교
- "이미 증명된 문제들과 비교 분석"
예시) 회의실 배정 vs 활동 선택 문제
1. 공통점
- 시간이 겹치지 않게 선택
- 종료 시간 기준 정렬 사용
2. 차이점
- 회의실: 한 개의 회의실에서 최대 회의 수
- 활동 선택: 여러 활동 중 겹치지 않는 최대 활동 수
3. 결론
- 구조가 같으므로, 같은 그리디 접근 가능💡 Tip!
- 수학적 증명이 아닌 경우 가능한 여러 방법으로 교차 검증할 것
- 반례를 찾으려는 노력이 중요
- 다양한 유형의 그리디 알고리즘 문제를 풀기
03. 완전 탐색 VS 그리디 알고리즘 비교
두 알고리즘의 특징 비교
-
두 알고리즘의 특징을 비교해 볼게요.
항목 완전 탐색 그리디 알고리즘 접근 방식 모든 경우의 수를 탐색 각 단계에서 최적 선택 최적해 보장 항상 보장 특정 조건에서만 보장 상대적 시간복잡도 높음 낮음 적용 범위 문제의 제한 시간 초과가 나지 않는 모든 문제 탐욕 선택 속성과 최적 부분 구조의 조건을 만족하는 문제
❗ 각 문제마다 어떤 알고리즘을 선택해야 할지 완벽한 공식은 없지만, 알고리즘을 유형별로 정확히 배우고 다양한 문제를 풀어보면서 상황에 맞는 최적의 알고리즘을 선택할 수 있습니다.
완전 탐색을 사용하는 경우
- 문제의 입력 크기가 작을 때
- 정확한 최적해가 필요할 때
- 다른 알고리즘을 적용하기 어려운 경우
그리디 알고리즘을 사용하는 경우
- 문제의 크기가 클 때
- 실행 시간이 중요한 경우
- 부분적인 최적해가 전체 최적해로 이어지는 문제일 때
