JAVA 코딩테스트 준비하기 - 완전 탐색 -

 

완전 탐색이라 함은 모든 경우의 수를 시도해 보는 방법을 말합니다
상대적으로 구현이 간단하고, 해가 존재한다면 항상 찾게 됩니다.
경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용하며 만약 입력 값의 범위가 크게 되면실행시간이 크기때문에 다른 알고리즘을 사용하거나 최적화를 수행해야합니다.

순차 탐색에 대해서 알아보겠습니다.
순차탐색은 어떤 값을 찾고자 할 때 한 값 씩 다 비교해보는 탐색 알고리즘입니다.
예를 들어 37의 값을 찾고 싶다고 하면 알고리즘에서는 하나씩 다 비교를 해보는 것입니다.
찾고자 하는 값이 없다면 -1이 나오도록 하는 것입니다.

시간복잡도가 O(n)이 됩니다.

다음과 같이 정렬이 되어있는 값이면 이진탐색을 하는 것이 더 효율적 이게 됩니다.
이렇게 이진탐색은 한번 비교할 때마다 탐색의 범위가 반으로 줄기 때문에 효율적이라고 볼 수 있습니다.

경우의 수를 나열하는 방법은 순열이 있습니다
선택 순서 가 결과에 영향을 미치는 경우를 순열로 나열합니다
조합은 선택 순서가 결과에 영향을 주지 않는 경우에 나열하는 것입니다.

예제를 보면 순서에 따라 결과가 달라지면 순열로 결과를 나타내는 것이고
두수를 더했을 때 가장 큰 합을 구하는 것은 덧셈은 교환법칙이 통하기 때문에 순서에 상관없이 조합으로 나타낼 수 있습니다.

예제의 편의를 위해 n=4로 배열을 { 1, 2, 3, 4}로 주어졌습니다.

메서드를 생성하여 재귀호출로 순열을 나열해 볼 것입니다. Cnt는 사용 횟수, used는 사용 숫자, val 두 자리 수를 저장할 것입니다.
선택된 수가 2이면 재귀호출을 종료하는 것을 return으로 나타내겠습니다.
Ret 리턴 값을 0 으로 초기화한다음에

숫자 사용 마킹을 위해 (used & 1 << i != 0 )을 비교하여 사용한 수가 없으면 continue해서 스킵을 하고 하나씩 올려 주기 위해 +1을 해서 재귀호출 해준다. 1이 선택이 되면 2 3 4 를 하나씩 비교해주고 max로 인해서 그중 가장 큰 값을 ret에 저장을 해준다.

이것이 2 3 4 가 모두 반복이 되면 가장 큰 값으로 ret가 설정되어 리턴이 됩니다.

그 다음에 조합 예제를 보겠습니다.
마찬가지로 n과 arr는 고정을 해주었습니다.

순서는 중요하지 않기때문에 순서를 고정하고 사용하고 안하고 로 구분을 해줄 것입니다.
파라미터의 의미가 pos는 현재 위치, cnt 선택된 갯수, val 중간 계산 값입니다

선택된 숫자의 개수가 2개이면 재귀호출을 종료할 것이고요
아니라면 선택하고 포지션이 끝까지 가버렸다면 종료를 위해 -1를 리턴 해줍니다.

선택하고 선택 안하고 의 경우를 표현하여  max로 가장 큰 값을 구해주면 된다.

조합으로 풀 수 있는 경우를 순열로 풀게 되면 시간이 초과될 수 있기 때문에 조합으로 푸는 것을 추천합니다.