알고리즘 문제 해결 전략 - 6장 무식하게 풀기(brute-force)

무식하게 풀기(brute-force)

- 완전 탐색(exhaustive search) : 가능한 방법을 전부 만들어 보는 알고리즘



1. 반복문

-  입력 개수가 적다면 간결하고 단순하지만 골라야 하는 원소의 수가 늘어날수록 코드가 길고 복잡해지는데다, 골아야 할 원소의 수가 입력에 따라 달라질 수 있는 경우에는 사용할 수 없다.

2. 재귀 함수(recursive function) 혹은 재귀 호출(recursion)

- 재귀 호출은 위와 같은 문제의 경우에 단순한 반복문보다 간결하고 유연한 코드를 작성할 수 있도록 해줍니다.

※ 기저 사례(base case)
모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 합니다. 쪼개지지 않는 가장 작은 작업들을 가리켜 기저 사례(base case)라고 합니다.


ex1) n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
if) n==7, m==4

ex1-1) 반복문 이용









ex1-2) 재귀 함수 이용

ex2) 보글 게임: 주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 문제






reference) 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략