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

## 1. 힙

### 1.1 리스트

### 1.2 순차 리스트

# Heap

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

### 최대 힙(max heap)

- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 > 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 큰 노드

### 최소 힙(min heap)

- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 < 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 작은 노드

### 활용

1. 원소 넣을때

배열이라면 최대값인 1000 저장할 때 큰 순서로 정렬하려고 하면 맨 앞부터 1000번 비교해야 함

그런데 만약 최대 힙을 사용하면

→ 완전이진트리의 모양을 유지하도록 넣어줌 (왼쪽→오른쪽 자식 순서로 부모노드가 자식노드보다 큰지 확인하고 스왑 작업을 하면서)

→ 약 10번만 비교하면 됨 (logN)

2. 루트노드 삭제할 때

완전이진트리는 유지해야함 그러므로 마지막 리프노드를 루트로드로 가져온다

그 다음 크기 비교하며 스왑 작업 반복 (logN)

⇒ **힙으로 구현된 것이 우선순위 큐**이다.

기본은 Natural ordering 으로 최소힙으로 관리되고 있다.

순서 관리하는 기준을 변경하고 싶다면 comparable과 comparator를 사용한다.

## 힙의 활용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)메서드

compareTo : 철수한테 너랑 길동이랑 싸우면 누가 이기냐고 물어보는 거

- 음수결과, 0결과 : 오름차순 정렬에 쓰인다면 그대로 둠
- 양수결과 : 오름차순 정렬에 쓰인다면 두 원소의 자리를 바꿈(교환)
1. 오름차순 : 내꺼 - 남의 거
2. 내림차순 : (남의 거 - 내 거) 혹은 (내꺼- 남의 거)에 -1 곱한 값을 오름차순 정렬하는 애한테 넘기면 내림차순 정렬하게 됨

# 순열을 생성하는방법 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()


>> : 남는 왼쪽 비트를 부호비트로 채움 (0이면 0으로 1면 1로)

>>>: 남는 왼쪽 비트를 무조건 0으로 채움(마치 탱크..)


### 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();
		}
	}

}

## 분할 정복

### 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. 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

# 이번 주 문제
## 정사각형 방(그래프)
- 문제의 조건을 활용하여, 탐색할 범위 제한 가능
- 이미 탐색된 값을 저장하여 다른 위치에서 탐색할 때 활용 가능.
- 재귀의 리턴 값을 활용하여 연산 가능
## 스택 계산기(스택)
- 스택을 이용한 우선순위에 따른 데이터 처리 방법
- infix에서 postfix로의 전환 방법

## 암호문(연결리스트)
- 연결리스트 구현 연습해보기
- 연결리스트의 중간(처음,끝X) 삽입 메서드를 활용 가능
## 한빈이와 spot mart(완전탐색)
- 정렬하여 그리디적으로 접근가능
- 과자르 2봉지만 고르느 것이므로 재귀 말고 for문으로도 간딘히 구현 가능
## 요세푸스(연결리스트)
- 제거한 사람의 다음을 head로 하고 제거한 사람의 이전 사람들을 연결리스트의 마지막 노드부터 순서대로 추가하는 작업을 한 명도 남지 않을 때 까지 반복
- 각 노드의 링크 간 연결에 유의
- 사람 수 보다 순서 K가 큰 경우 K-사람수 를 K가 사람 수보다 작거나 같을 때까지 반복
## 색종이(2차원배열?)
- 도화지의 상태를 표현하는 2차원 배열 생성
- 입력 받은 색종이의 왼쪽 아래 위치로부터 가로, 세로로 10만큼의 영역을 1로 저장
- 1의 합을 구하면 색종이의 넓이