완전 탐색(Brute Force)

: 문제에서 가능한 모든 경우의 수를 생성하고, 조건을 만족하는지 하나씩 검사하여 해결하는 방식

• Generate-and-test 방식, “Just do it”
• 특징
  • 거의 모든 문제에서 적용 가능 (만약 모든 경우의 수가 크게 제한되지 않는다면)
  • 문제 접근(설계) 시간이 비교적 빠름
  • 경우의 수가 많은 경우, 계산 시간이 기하급수적으로 늘어날 수 있음
  • 무조건 완전 탐색 시, 시간 초과 가능성. 문제 규모(입력 크기)에 따라 적절한 최적화/자료구조 설계가 필요
• 완전 탐색은 문제 해법 설계시 출발점으로서 자주 사용되며, 추가 기법(가지치기/메모이제이션 등)으로 최적화하는 접근이 일반적이다.

반복과 재귀

반복(Iteration)과 재귀(Recursion)는 유사한 작업을 수행할 수 있음

1. 반복은 수행하는 작업이 완료될 때까지 계속 반복
   • 루프 (for, while 구조)
   • 반복문은 코드를 n번 반복시킬 수 있음
2. 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법
   • 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합
   • 재귀호출은 n중 반복문과 같은 효과

• 재귀를 위해 이해하면 좋은 함수 특징

  1. KFC 함수 호출할 때, int 타입 객체를 전달하면 값만 복사됨

  2. BTS 함수가 끝나면, Main으로 되돌아 오는 것이 아니라, 해당 함수를 호출했던 곳으로 돌아옴

     

• 재귀호출의 기본

  • 무한 재귀호출을 막는 역할 (if문)

    → 기저조건 (base case)

완전탐색 (Brute-Force)

: 모든 가능한 경우를 모두 시도를 해보아 정답을 찾아내는 알고리즘

대표적인 문제 해결 기법 비교

1. 완전 탐색(Brute Force)
   • 모든 경우를 나열 & 테스트
   • 구현 난이도가 낮고 확실한 정답 도출
   • 경우의 수가 큰 문제에는 시간 초과 위험
2. 탐욕(Greedy)
   • 매 순간 최적이라고 생각되는 해를 선택
   • 전역적 최적해를 보장하지 못할 수 있음
3. 분할 정복(Divide and Conquer)
   • 문제를 더 작은 하위 문제로 나누어 해결한 뒤, 결합
   • 예: 병합 정렬, 퀵 정렬
4. 동적 프로그래밍(DP)
   • 이전에 계산한 결과(부분 문제)를 메모하여 중복 계산 방지
   • 현재에서 가장 좋아 보이는 것을 선택하는 것이 아닌, 과거의 데이터를 이용하여 현재의 데이터를 만들어내는 문제해결기법
   • 최적화 문제에 자주 사용