완전탐색

완전탐색

• 많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것이다.
• 순열(Permutation), 조합(Combination), 부분집합(Subsets)
• 조합적 문제에 대한 brute-force 방법.
  • 모든 경우의 수를 테스트하기 때문에 속도는 느려도 해답은 찾아낸다.
  • 입력의 크기를 작게 해서 간편하고 빠르게 답을 구하는 프로그램을 작성한다.
• brute-force
  • "Just - do - it"
  • 문제 해결을 위한 간단하고 쉬운 접근법

검정 등에서 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출 한 후,
성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.

💡재귀 함수 (recursive function)

• 함수 내부에서 직접 혹은 간접적으로 자신을 호출하는 함수
• 기본부분 + 유도파트
• 메서드, 함수에 대한 정의를 명확히 해야 한다.

💡반복 vs 재귀

• 재귀는 문제 해결을 위한 알고리즘 설계가 간단하고 자연스러움.

• 일반적으로 재귀는 반복보다 더 많은 메모리와 연산을 필요로 한다.

• n이 커질수록 재귀알고리즘은 비효율적.

  	재귀	반복
  종료	재귀 함수 호출이 종료되는 베이스 케이스	반복문의 종료조건
  수행시간	(상대적) 느림	빠름
  메모리 공간	(상대적) 많이 사용	적게 사용
  소스 코드 길이	짧고 간결	길다
  소스 코드 형태	선택 구조 (if...else)	반복 구조(for, while)
  무한 반복시	스택 오버플로우	CPU를 반복해서 점유

---

📌순열(Permutation)

• 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것.
• 서로 다른 N개 중 r개를 택하는 순열 = nPr
  • nPr = n (n-1) (n-2) (n-3) ... * (n-r+1)
  • n > 12 인 경우, 시간 복잡도가 폭발적으로 증가한다

◾ 재귀 호출을 통한 순열 생성

perm(cnt) {
	for i from to N
		if v[i] == true continue
		nums[cnt] = numbers[i]
		v[i] = true
		perm(cnt+1)
		v[i] = false
	end for
}

◾ 비트마스킹을 통한 순열 생성

• boolean v 대신 비트정보를 표현하는 정수 flag를 비교해서 순열 생성
• flag를 사용하면 flag를 다시 false로 바꾸는 처리를 할 필요가 없다.

private static void permutation(int cnt,int flag) {

	if(cnt==R) {
		System.out.println(Arrays.toString(numbers));
		return;
	}
		
	for (int i = 0; i < N; i++) {
		if((flag & 1<<i)!=0) continue;
        	// 1 << i = 1을 i만큼 왼쪽으로 shift
			
		numbers[cnt] = input[i];
			
		permutation(cnt+1,flag|1<<i);
			
	}		
}

💡비트연산자

• value << n
  • value를 n비트만큼 왼쪽으로 shift

---

📌조합(Combination)

• 서로 다른 N개의 원소 중 r개를 순서 없이 골라낸 것.
• 조합의 수식
  

◾ 반복문을 통한 조합 생성

for i from 1 to 4
	for j for i+1 to 4
		for k form j+1 to 4
			print i , j ,k

nCr 일 경우, 경우의수가 가장 클 경우는 nCn/2 인 경우!!
→ 내가 문제를 풀 때, n이 엄청 크고 r이 n/2이다면 조합이 아닐 확률이 높다..
→ 풀기 전에 따져보기

◾ 재귀 호출을 이용한 조합 생성

combi(cnt, start) {
	if cnt == r
		//조합 완성 ex)프린트, 계산 ...
	else
		for i from start to n-1
			n[cnt] <- input[i];
			combi(cnt+1,i+1);
		end for
}

◾ 중복조합

• 중복으로 뽑는 것을 허용하는 조합
• n번째 뽑는 수를 n-1번째의 수부터 뽑는다.

combi(cnt,start) {
	if cnt == r
		//조합 완성 ex)프린트, 계산 ...
	else
		for i from start to n-1
			n[cnt] <- input[i];
			combi(cnt+1,i);
		end for
}

---

📌부분집합 (Subset)

• 집합에 포함된 원소들을 선택하는 것.
• 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾기 위해 사용.
  ex) 배낭 짐싸기 (knapsack)
• 집합의 원소가 n개 → 부분집합의 수 2ⁿ개
• 반복문 자체가 가변적일 수 없기 때문에 재귀를 이용해 구현한다.

◾ 재귀 호출을 이용한 부분집합 생성

subset(cnt) {
	if cnt == N
		//부분집합 완성
	else
		V[cnt] = true;
		subset(cnt+1);
		V[cnt] = false;
		subset(cnt+1);
}

• 경우의 횟수만큼 재귀호출이 일어나기 때문에 수를 따져보고 효율적이라면 풀기

◾ 바이너리 카운팅을 통한 사전적 순서로 부분집합 생성

int arr[] = {3, 6, 7, 1, 5, 4};
int n = arr.length;

for (int i = 0; i < (1 << n); i++) 
{
    for (int j = 0; j < n; j++){
        if (i & (1 << j) != 0)
            System.out.print(arr[j]+" ");
    }
    System.out.println();
}

• 부분집합을 생성하기 위한 가장 자연스러운 방법.
• 바이너리 카운팅 : 사전적 순서로 생성하기 위한 가장 간단한 방법
• 원소 수에 해당하는 N개의 비트열을 이용한다.
• n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미한다.
• 처리 횟수는 같지만 재귀하진 않는다.