Algorithm Study (완전탐색)

취업준비를 하면서 알고리즘 공부의 필요성(코딩테스트)를 느꼈고,

연구실 후배들과 알고리즘 스터디를 진행했다.

 

0주차 계획 수립을 마치고 1주차 스터디를 진행한다.

이론 진행을 우선 하기로 의논되었고, 첫주에는 완전탐색, 정렬, 문자열에 대해 공부했다.

 

1. 완전탐색

가장 단순한 알고리즘이다.

무식하게 푼다(Brute Force) 라는 말이 있다.

해당 방법은 컴퓨터의 빠른 연산 속도를 이용해 경우의 수를 모두 나열하여 답을 찾는 방법이다.

 

예) 10명을 일렬로 줄 세울때, 사이가 나쁜 두 사람이 붙어있지 못하게 하는 경우

1. 10명을 일렬로 세우는 모든 방법을 찾는다(10! 약 360만 가지)
2. 그중 두사람이 붙어있는 경우를 제외한다.

책 '알고리즘 문제해결 전략' 에서는 이와같은 완전탐색 기법을 알고리즘의 기본이라고 설명한다.

 

2. 완전탐색(재귀호출)

완전 탐색을 재귀호출을 이용하여 진행한다.

재귀함수의 종료 조건인 '기저 사례(base case)'가 있어야 한다.

 

예) 1부터 n까지의 합을 반환하는 sum 함수가 있다.

'알고리즘 문제해결 전략' 코드 6.1

14번째 줄 sum 함수는 자연수 n이 주어지면 1부터 n까지의 합을 구하는 함수이다.

24번째 줄 recursiveSum 함수는 sum 함수를 재귀함수로 구현 한 것이다.

이때 26번째 줄 if(n == 1)이 recursiveSum 함수의 기저사례가 된다.