완전탐색

• 모든 경우의 수를 시도해 보는 방법
• 상대적으로 구현이 간단하고, 해가 존재한다면 항상 찾게 된다
• 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우에 유용하다

순차 탐색

// 완전 탐색 알고리즘

itn sequentialSearch(int[] arr, int n, int x) {
	for(int i=0; i<n; i++) {
    	if(arr[i] == x)
        	return i; // 찾는 값을 반환
    }
  return -1; // 없다는 의미로 -1 반환
}

경우의 수

• 순열
• 선택 순서가 결과에 영향을 미치는 경우
• 조합
• 선택 순서가 결과에 영향을 주지 않는 경우

// {1,2,3,4} 가 주어진 경우, 만들 수 있는 가장 큰 두자리 수를 구하라
 >> 이럴 경우 순열로 구함
 public class Main {
	static int N = 4;
	static int[] Nums = {1,2,3,4};
	// cnt - 선택된 숫자의 갯수, used - (비트)사용된 숫자, val - 중간결과
	static int solve(int cnt, int used, int val) {
		if(cnt == 2) return val; // 재귀 호출 종료
		// 재귀호출
		int ret = 0;
		for(int i=0; i<N; i++) {
			if((used&1 << i) != 0) continue; // 사용된 숫자가 없다면
			ret = Math.max(ret, solve(cnt +1, used | 1 << i, val *10 +Nums[i]));
		}
		return ret;
	}
	public static void main(String[] args) {
		System.out.println(solve(0,0,0)); // 가장 큰 값인 43반환
	}

}

// 두 수를 더했을 때 가장 큰 합을 구하라
 >> 조합으로 경우의 수 나열
 public class Main {
	static int N = 4;
	static int[] Nums = {1,2,3,4};
	// 조합은 순서가 중요하지 않음
	// pos - 현재 위치, cnt - 선택된 갯수, val - 중간결과
	static int solve(int pos, int cnt, int val) {
		if(cnt == 2) return val; // 재귀 호출 종료
		// 재귀호출
		
		// 경우의 수 제외
		if(cnt == 2) return val;
		if(pos == N) return -1;
		
		int ret = 0;
		ret = Math.max(ret, solve(pos+1, cnt+1, val+Nums[pos]));
		ret = Math.max(ret, solve(pos+1, cnt, val);
		return ret;
	}
	public static void main(String[] args) {
		System.out.println(solve(0,0,0)); // 7 반환
	}

}