[코딩테스트][알고리즘] 1. Brute Force(브루트포스 , 완전탐색)

brute force는 완전 탐색이라고도 불리며, 모든 경우의 수를 직접 대입해보는 방법으로 가장 간단하게 문제를 풀 수 있는 방법이다. 풀이법이 잘 생각나지 않는 문제라면, 완전 탐색을 이용해 코딩을 한 후 최적화하는 과정을 사용한다면 문제를 해결에 도움을 받을 수 있을 것이다.

 

완전 탐색의 시간 복잡도는 주로 O(N!), O(2^N)이다.

시간 복잡도를 알고 있으면, 문제의 조건을 보고 필요한 알고리즘을 유추하는 방법도 있다고 하니 시간 복잡도에 대해 알아놓으면 좋을 것 같다.

 

완전 탐색은 반복문을 이용하는 방법, 재귀 함수를 이용하는 방법이 있는데 보편적으로 사용되는 것은 재귀 함수라고 한다. 반복문의 경우 길이가 변하는 문제를 다룰때 구현이 복잡해진다는 단점이 있다. 초보자의 경우에는 재귀함수가 직관적으로 보이지 않을 수 있지만 경험이 쌓이다 보면 반복문보다 더 직관적으로 보인다고 하니 재귀 함수에 익숙해지도록 노력해봐야겠다. 

 

brute force 를 연습하기 위한 추천문제들이다.

1. https://www.acmicpc.net/step/22 (백준 단계별로  풀어보기)

2. https://www.acmicpc.net/problem/6603          

풀이 => https://www.acmicpc.net/source/17849836
3. https://www.acmicpc.net/problem/15654       

풀이 => https://www.acmicpc.net/source/17856279

4. https://www.acmicpc.net/problem/15655

5. https://www.acmicpc.net/problem/12100

풀이 => https://www.acmicpc.net/source/17864219

6. https://www.acmicpc.net/problem/15683

7. https://www.acmicpc.net/problem/14888