완전 탐색
완전 탐색은 가능한 모든 경우의 수를 전부 확인하여 문제를 해결하는 방법
완전 탐색의 장단점
장점
- 구현이 단순하고 이해하기 쉽다
- 모든 경우를 확인하므로 반드시 정답을 찾을 수 있다
- 문제를 처음 접근할 때 좋은 시작점이 됨
단점
- 모든 경우를 확인하므로 실행 시간이 오래 걸림
- 경우의 수가 많아지면 현실적으로 해결이 어려움
반복문을 이용한 완전 탐색
반복문을 이용한 완전 탐색은 for문이나 while문을 사용하여 가능한 모든 경우를 순차적으로 탐색하는 방법
- 문제에서 주어진 범위나 조건을 파악
- 해당 범위 내의 모든 경우를 반복문으로 확인
- 각 경우마다 문제의 조건을 만족하는지 검사
그리디 알고리즘
그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 하는 방법 -> 각 단계에서 최적이라고 생각되는 것을 선택하는 것
그리디 알고리즘의 장단점
장점
- 구현이 비교적 단순하고 실행 속도가 빠름
- 직관적이어서 이해하기 쉬움
단점
- 항상 최적의 해를 보장하지는 않음
- 각 단계에서의 최적의 선택이 최적 해결책이 아닐 수 있음
- 적용할 수 있는 문제의 유형이 한정적
그리디 알고리즘의 두 가지 필수 조건
- 탐욕 선택 속성
- 각 단계에서 선택한 방법이 이후의 결정과 상관없이 최종 답의 최적성을 유지해야 함("각각의 선택"에 초점)
- 최적 부분 구조
- 전체 문제의 최적해가 문제를 나눈 각 부분 문제의 최적해를 결합해서 얻을 수 있어야 함("문제의 구조"에 초점)
그리디 알고리즘 증명 방법
- 수학적 증명 - 가장 확실한 증명 방법이지만 난이도 높음
- 작은 예시로 검증 - 다양한 크기의 입력값으로 직접 테스트
- 반례 찾기 - 그리디 알고리즘이 실패하는 경우 찾기
- 기존 문제와의 비교 - 이미 증명된 문제들과 비교 분석
완전탐색 vs 그리디 알고리즘 비교
완전 탐색을 사용하는 경우
- 문제의 입력 크기가 작을 때
- 정확한 최적해가 필요할 때
- 다른 알고리즘을 적용하기 어려운 경우
그리디 알고리즘을 사용하는 경우
- 문제의 크기가 클 때
- 실행 시간이 중요한 경우
- 부분적인 최적 해가 전체 최적 해로 이어지는 문제일때
