# 2월 3주차 내용 정리 취합 (5조 - 정준영, 최지혜)

## 1. 힙

: **완전 이진 트리**에 있는 노드 중에서 **키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해**서 만든 **특별한 자료구조**

## 힙의 활용 - 우선순위 큐(Priority Queue)

### 우선순위큐를 구현하는 가장 효율적인 방법이 힙을 사용하는 것이다

- 노드 하나의 추가/삭제의 시간복잡도가 O(logN)이고 최대값/최소값을 O(1)에 구할 수 있다(반복문 아니고 최초 한 번, pop아니고 peek만 하는 경우에 한함)
- 완전 정렬보다 관리 비용이 적다

### 배열을 통해 트리 형태를 쉽게 구현할 수 있다.

교재 오타수정 2n, 2n+1 (지수아님)

### java.util.PriorityQueue : 원소가 Comparable 인터페이스를 구현하거나 Comparator를 구현한 별도의 클래스 사용하는 방법

- Heqp 자료구조
- 최대 Heap
- 최소 Heap

### java.util.PriorityQueue()

원소들의 natural ordering에 따라 heap 유지

따라서 반드시 모든 원소는 comparable 인터페이스를 구현해야함 ( compareTo(T t) 메서드 재정의함으로서)

- 마치 equals처럼 비교대상 중 하나는 메서드 호출하는 애이기 때문에 매개변수는 하나임 두개가 아님

String, Integer 등 8개의 Wrapper class는 이미 comparable 하기 때문에 사용하면 됨 다르게 비교하고 싶으면 comparator 사용

### java.util.PriorityQueue(Comparator comparator)

명시된 Comparator의 구현에 따라 원소들의 순서를 유지

comparator : 비교 도우미

compare(T t1, T t2)메서드

## 순열을 생성하는방법 4가지

1. for 문 (앞에서 함)
2. 재귀 - isSelected 배열 사용 (앞에서 함)
3. 재귀 w/ 비트마스킹 - 비트연산자(&, | , <<)를 사용 (새로운 방법!)
4. Next permutation (새로운 방법!)

### 3. 재귀 w/ 비트마스킹

input[]
numbers[]

perm(cnt, flag)
	if cnt == N : 순열생성완료
	else
		for i from 0 to N-1
			if (flag & 1<<i) != 0 then continue
			numbers[cnt] <- input[i]
			perm(cnt+1, flag | 1<<i) //flag와 1<<i 작업하여 매개변수로 보낸거지 flag에 대입한 것은 아니므로 되돌리는 코드는 필요 없음!!
		end for
end perm()

### 1<<ㅁ 의 활용

: 1을 원하는 위치(ㅁ)로 만들기

- 1<<ㅁ 와 어떤 값을 **&연산**

→ **연산 결과가 0인지 OR 0이 아닌지**에 따라

→ 어떤 값의 **ㅁ위치 비트가 0인지 OR 1인지를 판단**할 수 있음

- 1<<ㅁ 와 어떤 값을 **| 연산**

→ 어떤 값의 **ㅁ위치 비트를 1로 바꿀** 수 있음**(=마킹, 세팅)**

⇒ 방문관리(true/false) 등에 활용 가능함

### 소스코드

int k = 0xa5; // 1010 0101
		
		// k 비트열의 상태 중 오른쪽에서 1만큼 떨어진 비트 확인 (맨끝 : 0만큼 떨어짐)
		System.out.println(k & 1<<1); //0
		
		// k 비트열의 상태 중 오른쪽에서 2만큼 떨어진 비트 확인 
		System.out.println((k & 1<<2) + " // "
				+Integer.toBinaryString(k & 1<<2)); //4(1이 아님!!), toBinaryString()메서드는 앞 0은 생략함
		
		// k 비트열의 상태 중 오른쪽에서 1만큼 떨어진 비트를 1로 만들기
		System.out.println((k | 1<<1) + " // "
				+ Integer.toBinaryString(k | 1<<1)); //2

## 4. Next Permutation

: 재귀호출 횟수도 적고, 모 회사에서 구현문제로 나온 적 있음, 조합에도 활용될 수 있음

- 현 순열에서 사전 순으로 다음 순열 생성
- 알고리즘

: 아래 과정을 반복하여 사전식으로 다음으로 큰 순열 생성(가장 큰 내림차순 순열을 만들 때까지 반복)

1. 뒤 쪽부터 탐색하며 교환위치(i-1, 꼭대기에서 처음 꺾인 점) 찾기 ( i: 꼭대기, 가장 큰 수) (안꺾이고 걍 쭉 올라간다 → 마지막 순열이다)
2. 뒤 쪽부터 탐색하며 교환위치i-1와 교환할 큰 값 위치j 찾기 (마지막 순열 제외하면 항상 존재함. 꼭대기도 포함되니까)
3. 두 위치 값 교환
4. 꼭대기 위치i 부터 맨 뒤까지 오름차순 정렬
- NextPermutation 사용 전 숫자 배열을 오름차순으로 정렬하여 가장 작은 순열 한 번은 처리해야 함

예) 현재 순열 32541일 때

- 꼭대기 찾기 : 5 (←오른쪽부터 탐색)
- 541 내림차순이라는 건 5,4,1 얘네들로 만든 건 다 만들었다는 뜻임
- 5 앞인 2가 바꿀 위치 중 하나임 (←오른쪽부터 탐색)
- 2보다 큰 수 중 가장 작은 수인 4 (←오른쪽부터 탐색)를 2와 바꾸면 됨

⇒ 34521

- 541 오름차순 정렬 (양 끝, 다음 양 끝을 서로 swap 반복)

⇒ 34125

### 소스 코드

package com.ssafy.exhaustive;
/* nPn 만 가능함!! */
import java.util.Arrays;
import java.util.Scanner;

public class P4_PerutationNPTest {
	static int N;
	static int[] input;
	
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		input = new int[N];
		
		for(int i=0;i<N;i++) input[i] = sc.nextInt();

		Arrays.sort(input); // 오름차순 정렬하여 가장 작은 순열의 상태로 만듦
		
		do{
			System.out.println(Arrays.toString(input));
		}while(np());
	}

	public static boolean np(){

		int i = **N-1**;
		while(i>0 && input[i-1] >= input[i]) --i; //1. 꼭대기와 바꿀 애1 찾기
		
		//(1) i>0 조건으로 while문 빠져나온 경우 : 더 이상 앞자리가 없음, 현 순열이 가장 큰 순열 즉 마지막 순열임.
		if(i==0) return false;
		//(2) input[i-1] >= input[i] 조건으로 while문 빠져나온 경우 : i-1가 바꿀위치 중 하나임
		
		int j = **N-1**;
		while(input[i-1]>=input[j]) --j; //2.바꿀 애 2 찾기
		
		swap(i-1,j); //3. 바꾸기
		
		//4. 오름차순 정렬하기
		int k = **N-1**;
		while(i<k) { 
			swap(i++,k--);
		}
	
		return true;
	}
	private static void swap(int i, int j) {
		int temp = input[i];
		input[i] = input[j];
		input[j] = temp;
	}
}

- 호출횟수에 있어 유리한 측면이 있음( 딱 순열 가지수 만큼 호출)
- 시뮬레이션에 접목 시 재귀가 아닌 do while문을 활용함으로써 시뮬레이션 코드에 집중할 수 있음

## 조합을 생성하는 방법
- 서로 다른 n 개의 원소 중 r개를 순서 없이 골라낸 것을 조합(combination)이라고 한다
- 수식

nCr = $n!/(n-r)!r!$

nCr = n-1Cr-1 + n-1Cr

예) {1,2,3,4} 중 원소 3개 포함하는 모든 조합 생성하기

### 1 .반복문을 통한 조합 생성

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

### 2. 재귀 호출을 이용한 조합 생성

input[]
numbers[] : 조합이 저장될 배열

comb(cnt, start)
	if cnt == r : 조합 생성 완료
	else
		for i from **start** to n-1
			numbers[cnt] <- input[i]
			comb(cnt+1, **i+1**) //start+1 아니고 i+1 임
		end for
end comb

### 3. NP 를 활용한 생성

1. 크기 n 인 정수배열 만든다
2. 뒤쪽부터 r개만큼 1로 채움( 0: 그 인덱스에 해당하는 값을 선택안함, 1: 선택함)
3. 이 배열을 NP 돌리며 인풋배열과 &연산

예) {1,2,3,4} 중 2개 순서없이 선택

package com.ssafy.exhaustive;

import java.util.Scanner;

public class C2_NPTest {
	static int N,R;
	static int[] input;
	static int[] P;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();
		
		input = new int[N];
		P = new int[N]; //N크기의 flag 배열
		
		for(int i =0;i<N;i++) {
			input[i] = sc.nextInt();
		}
		
		//뒤부터 r개만큼 1채우기
		int cnt=0;
		while(++cnt<=R) P[N-cnt]=1;
		
		//np로 조합만들기
		do {
			for(int i =0;i<N;i++) {
				if(P[i] ==1) System.out.print(input[i]+" ");
			}
			System.out.println();
			
		}while(np(P));
	}
	public static boolean np(int[] arr){

		int i = N-1;
		while(i>0 && arr[i-1] >= arr[i]) --i; //1. 꼭대기와 바꿀 애1 찾기
		
		//(1) i>0 조건으로 while문 빠져나온 경우 : 더 이상 앞자리가 없음, 현 순열이 가장 큰 순열 즉 마지막 순열임.
		if(i==0) return false;
		//(2) input[i-1] >= input[i] 조건으로 while문 빠져나온 경우 : i-1가 바꿀위치 중 하나임
		
		int j = N-1;
		while(arr[i-1]>=arr[j]) --j; //2.바꿀 애 2 찾기
		
		swap(arr, i-1,j); //3. 바꾸기
		
		//4. 오름차순 정렬하기
		int k = N-1;
		while(i<k) { 
			swap(arr, i++,k--);
		}
	
		return true;
	}
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

## 부분집합의 생성 방법
- 집합에 포함ㄷ괸 원소들을 선택하는 것이다
- 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분집합을 찾는 것이다

예 > 배낭 짐싸기

- N개의 원소를 포함한 집합
- 자기 자신과 공집합을 포함한 **모든 부분집합(Power set)의 개수는 $2^n$개**
- 원소의 수가 증가하면 부분집합의 개수는 **지수적으로 증가**

**부분집합은 N개 중 0개부터 N개까지 모든 개수를 뽑는 조합의 경우의 합과 같다.

예) {1,2,3} 의 모든 부분집합(Power set) 생성

### 1. 반복문

for i in 1 -> 0 (1: 선택, 0:비선택)
	selected[1] <- i
	for j in 1 -> 0
		selected[2] <- j
			for k in 1 -> 0
				selected[3] <- k
					for m in 1->3
						if selected[m] == 1 : 뽑은 아이들
							print m
				...
		...
...

### 2. 재귀

input[]
isSelected[] : 부분집합에 포함/비포함 여부를 저장한 배열

subset(int cnt) (cnt:현재까지 처리한 원소의 개수)
	if cnt == N : 부분집합 완성
	else
		isSelected[cnt] <-true
		subset(cnt+1)
		isSelected[cnt] <-false
		subset(cnt+1)
end subset()

package com.ssafy.exhaustive;

import java.util.Scanner;

public class S1_SubSetTest {
	static int N, totalCnt;
	static int[] input;
	static boolean[] isSelected; // 부분집합에 포함비포함 여부를 저장한 배열
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		input = new int[N];
		isSelected = new boolean[N];
		for(int i=0;i<N;i++) {
			input[i] = sc.nextInt();
		}
		subset(0);	
		System.out.println("총 경우의 수 : " + totalCnt);
	}
	private static void subset(int cnt) {//(cnt:현재까지 처리한 원소의 개수)
		if (cnt == N) {// : 부분집합 완성
			++totalCnt;
			for(int i=0;i<N;i++) {
				System.out.print((isSelected[i]?input[i]:"X")+" ");
			}
			System.out.println();
			return;
		}
		
		else {
			isSelected[cnt] = true;
			subset(cnt+1);
			isSelected[cnt] = false;
			subset(cnt+1);
		}
	}
}

### 3. 바이너리 카운팅을 통해 사전적 순서로 부분집합 생성

- 원소 수에 해당하는 N개의 비트열을 이용
- n번 째 비트값이 1이면 n번 째 원소가 포함되었음을 의미한다
- 결론

원소 4개일 때,

0~$2^4$의 10진수를 2진수로만 바꾸면

⇒ **이미 비트마스킹을 할 준비가 다 되어있음**( |연산으로 마킹은 안해도 됨 &연산으로 판단만 하면 됨)

** 재귀가 아닌 반복문으로 구현한다는 차이가 있음(메모리 측면에서 이점), 호출 횟수는 재귀와 같다

소스코드

package com.ssafy.exhaustive;

import java.util.Scanner;

public class S2_BinaryCountingTest {
	static int N;
	static int[] input;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		input = new int[N];
		for(int i=0;i<N;i++) {
			input[i] = sc.nextInt();
		}

		generateSubset(1<<N); //2의 N승
	}
	private static void generateSubset(int caseCnt) {
		
		for(int flag=0; flag<caseCnt; flag++) { // i : 비트마스크되어있는 수
			System.out.print("flag : " + flag+", subset : ");
			for(int j=0;j<N;j++) {	//맨 뒤부터 "N개"의 비트열을 확인
				if((flag & 1<<j) != 0) {
					System.out.print(input[j]+" ");
				}else {
					System.out.print("X ");
				}
			}
			System.out.println();
		}
	}

}

## 문제제시 : 거스름돈 줄이기

- 손님이 지불한 금액에서 물건값을 제외한 차액(거스름돈)을 지불하는 문제를 생각해보자.
- 어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?

# 탐욕법(greedy)

### 탐욕 알고리즘

- 최적해를 구하는 데 사용되는 **근시안적**인 방법
- 최적화(optimization) 문제란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제
- 일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 greedy 접근이 된다
- 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
- 각선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서 **그것이 최적이라는 보장은 없다. ⇒ "검증"이 필요!!**
- 일단, 한 번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며 또한 제한적인 문제들에 적용된다.

### 최적해를 반드시 구한다는 보장이 없다

- 거스름돈 문제에서 단위 큰 돈 개수부터 계산 가능한 이유 : 각 단위가 다른 단위의 배수임이 검증되었기 때문임
- 그렇지 않은 경우 :

거스름돈 800원인데

500원짜리 동전 400원짜리 동전 100원짜리 동전 있으면

(500원X1+100원X3) 4개 보다 (400원X2)2개가 최소개수임

## 문제제시 : 배낭 짐싸기(Knapsack)

- 도둑은 부자들의 값진 물건들을 훔치기 위해 보관창고에 침입하였다.
- 도둑은 훔친 물건을 배낭에 담아올 계획이다. 배낭은 담을 수 있는 물건의 총 무게(W)가 정해져있다.
- 창고에는 여러 개(n)의 물건들이 있고 각각의 물건에는 무게와 값이 정해져 있다.
- 경비원들에게 발각되기 전에 배낭이 수용할 수 있는 무게를 초과하지 않으면서 값이 최대가 되는 물건들을 선택해야 한다.
- Knapsack 문제유형
- **0-1 Knapsack** : 물건을 통째로 담아야 하는 문제(대부분)
- Fractional Knapsacl : 물건을 쪼개 부분적으로 담는 것이 허용되는 문제

### 0-1 Knapsack 에 대한 완전 검색 방법

- 완전 검색으로 물건들의 집합 S에 대한 **모든 부분집합**들을 구한다
- 부분집합의 총 **무게가 W를 초과하는 집합들은 버리고, 나머지 집합에서 총 값이 가장 큰 집합을 선택**할 수 있다.
- 물건의 개수가 증가하면 시간복잡도가 지수적으로 증가한다 (원소 n개의 부분집합 개수 = $2^n$)

⇒ n이 11보다 커지면 사실상 불가능하다. 이 방법 말고 다른 방법은 없을까?

### 0-1 Knapsack 에 대한 탐욕적 방법 1

- 값이 비싼 물건부터 채운다
- W = 30kg 제한
- 탐욕적 방법의 결과 : 물건 1 → 25kg, 10만원
- 최적해 : 물건2, 물건3 → 20kg, 14만원
- 결론 : 최적해를 구할 수 없다.

### 0-1 Knapsack 에 대한 탐욕적 방법 2

- 무게가 가벼운 물건부터 채운다
- W = 30kg 제한
- 탐욕적 방법의 결과 : 물건2, 물건3 → 14만원
- 최적해 : 물건1 → 15만원
- 결론: 최적해를 구할 수 없다.

### 0-1 Knapsack 에 대한 탐욕적 방법 3

- 무게 당 값이 가장 높은 순서로 물건을 채운다
- W = 30kg 제한
- 탐욕적 방법 : 물건1, 물건3 → 190만원
- 최적해 : 물건2, 물건3 → 200만원
- 역시 최적해를 구할 수 없다...

### ⇒ 그런데 만약 Fractional Knapsack 문제라면??

세 번째 탐욕적 방법을 사용하면 최적해를 구할 수 있다.

물건1(50만원) → 물건 3(140만원) → 물건2의 절반(30만원) = 30kg, 220만원

## 문제제시 : 회의실 관리

- 김대리는 소프트웨어 개발팀들의 회의실 사용신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다.
- 회의는 시작시간과 종료시간이 있으며 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다.
- 가능한 **많은** 회의가 열리기 위해서는 회의들을 어떻게 배정해야 할까?
- 입력 예
- 회의개수
- (시작시간, 종료시간)

⇒ 회의의 종료시간이 빠른 순으로 넣어보자

### 활동 선택 문제(Activity-selection problem)

****꼭 입력을 들어온 순서대로 처리할 필요가 있는지 안 그래도 되는지 따져본다.**

→ 1. 종료시간이 빠른 순으로, 그리고 같다면 (중요!)2. 시작순서가 빠른 순으로 **정렬**

**그리디로 풀면 코드 간결

**if else 너무 많다면 그건 그리디로 풀 수 있는 문제가 아닐 가능성이 크다**

### 탐욕 알고리즘의 필수 요소 (=검증해야 하는)

- 탐욕적 선택 속성
- 최적 부분 구조
- 최적화 문제를 정형화해라

→ 하나의 선택을 하면 풀어야 할 다른

- [원문제의 최적해 = 탐욕적 선택 + 하위문제의 최적해]임을 증명해라

### 탐욕 알고리즘의 예

- 대표적인 탐욕 기법의 알고리즘들 → 3월에 다시
- Prim
- Kruskal
- Dijkstra

## 분할 정복

### 1.분할 정복 기법 설계 전략
- 분할(Dvide): 해결할 문제를 여러 개의 작은 부분으로 나눈다.
- 정복(Conquer) : 나눈 작은 문제를 해결한다.
- 통합(Combine) : (필요하다면) 해결된 해답을 모은다.

### 2. 분할 정복 기반의 알고리즘
- 거듭 제곱

Recursive_Power(x,n)
    IF n==1 : RETURN x
    IF n is even
        y <- Recursive_Power(x, n/2)
        RETURN y*y
    ELSE
        y <- Recursive_Power(x, (n-1)/2)
        RETURN y*y*x

### 3. 이진 검색(Binary Search)
- 자료의 가운데 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
- 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가며 보다 빠르게 검색을 수행한다.

- 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
- 검색 과정
- 1. 자료의 중앙에 있는 원소를 고른다.
- 2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
- 3. 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 끝낸다.
- 4. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
- 5. 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

- 이진 검색 반복 구조

binarySearch(S[], n, key)
    Start <- 0
    end <- n-1
    
    WHILE start <= end
        mid <- (start + end)/2
        IF S[mid] == key
            RETURN mid
        ELIF S[mid] < key
            start <- mid + 1
        ELIF S[mid] > key
            end <- mid -1
    END WHILE
    RETURN -1

- 이진 검색 재귀 구조

binarySearch(S[], start, end, key)
    IF start > end
        RETURN -1
    ELE
        mid <- (start + end)/2
        IF S[mid] == key
            RETURN mid
        ELIF S[mid] > key
            RETURN binarySearch(S[], start, mid - 1, key)
        ELSE
            RETURN binarySearch(S[], mid + 1, end, key)

- 이진 검색 API
- java.util.Arrays.binarySearch
- int binarySearch(int[] a, int key)
- int binarySearch(int[] a, int fromIndex, int toindex, int key)

## 백트래킹(Backtracking)

### 1.백트래킹이란?
- 퇴각 검색.
- 모든 조합을 시도하여 문제의 해를 찾는 방법.
- 해를 얻을 때까지 모든 가능성을 시도한다.
- 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 선택지 중에 해결책이 있다.
- 여러가지 선택지들이 존재하는 상황에서 하나의 가지를 선택한다.
- 선택이 이루어지면 새로운 선택지들의 집합이 생성된다.
- 일반적으로 재귀 함수로 구현된다.

### 2. 당첨 리프 노드 찾기
- 루트에서 갈 수 있는 노드를 선택한다.
- 꽝 노드까지 도달하면 최근의 선택으로 되돌아와서 다시 시작한다.
- 더 이상의 선택지가 없다면 이전의 선택지로 돌아와서 다른 선택을 한다.
- 루트까지 돌아갔을 경우 더 이상 선택지가 없다면 찾는 답이 없다.

### 3. 백트래킹 기법
- 모든 후보를 검색하지 않는다.
- 어떤 노드의 유망성을 점검한 뒤 유망하지 않다고 판단되면 그 노드의 부모 노드로 돌아가 다음 자식 노드로 간다.
- 유망하다 : 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 있는 노드
- 가지치기 : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.

### 4. 백트래킹 절차
- 1. 상태 공간 트리의 깊이 우선 탐색을 실시한다.
- 2. 각 노드가 유망한지 점검한다.
- 3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 다른 노드로의 검색을 계속한다.

### 5. 백트래킹 알고리즘

backtrack(node v)
    IF promising(v) == false then return
    IF there is a solution at v
        write the Solution
    ELSE
        FOR each child u of v
            backtrack(u)

### 6. 백트래킹과 완전탐색(DFS)과의 차이
- 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다.(Pruning, 가지치기)
- 완전 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단한다.
- 완전 탐색을 가하기에는 경우의 수가 너무나 많다.
- (예를 들어, N! 가지의 경우의 수를 가진 문제에 대해 완전 탐색 가하면 당연히 처리 불가능한 문제)
- 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수 시간을 요하므로 처리 불가능할 수 있다.

### 7. 백트래킹 정리
- 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 방법.
- 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것.
- DFS로 모든 경우ㅢ 수를 탐색하는 과정에서 조건이 될 수 있는 상황을 정의하여 체크하고, 그러한 상황인 경우 탐색을 중지시킨 후 그 전으로 돌아가서 다시 탐색한다.

# 이번 주 문제
## 캐슬디펜스
- 메서드 분리하고 짜집기 하는 방식 사용하면 디버깅 용이
- 메서드 리턴타입 적절히 활용
##
- 스택을 이용한 우선순위에 따른 데이터 처리 방법
- infix에서 postfix로의 전환 방법