[TIL] JAVA - 28일차

알고리즘 설계 기법

• 완전탐색 (Brute Force) : 반드시 답을 찾을 수 있다 .시간이 오래걸린다.
• 탐욕기법 (Greedy) : 아이디어 , 답이 아닐 수 있다.
• 백트래킹 (Back tracking) : 시간 절약 ( 가망없는애 컷)
• 분할정복 ( Divide & Conquer) :
• 동적계획법 (DP)

int[] a = {1,3,5,2,4,6,0}
int key = 4;

//완전탐색
for (int i = 0 ; i < a.length ; i++){
	if (a[i] == key)
    	System.out.print("존재");
}

순열 nPr

비트 마스킹

& 해당자리 비트상태 확인
| 해당 비트를 1로 세팅
>> 왼쪽 자리를 부호비트로 채움
>>> 왼쪽 자리를 0으로 채움
1<<n 1을 원하는 위치로 옮기고 싶을 때

public class 실험실 {

	public static void main(String[] args) throws Exception {
		int k = 0xa5; // 1010 0101
		//k 비트열의 상태중 오른쪽에서 1만큼 떨어진 비트 확인
		System.out.println(k & 1<<5 );  //1010 0101 & 0010 0000(뒤에 0 이 5개)   =  32
		System.out.println(Integer.toBinaryString(k & 1<<5 ));
		
		//k비트열의 오른쪽에서 1만큼 떨어진 자리 1비트로 만들기
	}

}

NextPermutation

현 순열에서 사전순으로 다음 순열 생성
사용 전에 숫자배열을 오름차순으로 정렬하여 가장 작은 순열 한번 처리

1. 뒤쪽부터 탐색하며 교환위치(i-1) 찾기 (i: 꼭대기)
2. 뒤쪽부터 탐색하며 교환위치(i-1)와 교환할 큰 값 위치(j) 찾기
3. 두 위치 값 (i-1 , j ) 교환
4. 꼭대기위치(i)부터 맨 뒤까지 오름차순 정렬

ex) 3 2 5 4 1

1) 만약 꺾이는 부분이 없다? = 가장 큰 순열이다. 5에서 2로 가면서 꺾이기 때문에 2 뒤는 가장 큰 순열이고 2를 그 다음 큰 수와 SWAP하기 위해 저장한다.

2) 1에서 찾았던 2를 기준으로 2보다 뒤에있으면서 2보다 큰 수를 찾아서 SWAP한다

3) 2와 4를 SWAP 하였지만 4의 뒷부분이 아직 내림차순을 가지고 있으므로 오름차순으로 재배치한다.

재배치 방식)

import java.util.Arrays;
import java.util.Scanner;

public class 실험실 {
	static int N;
	static int[] input;

	public static void main(String[] args) throws Exception {
		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; //꼭대기 찾기
		
		//더이상 앞자리가 없는 상황 (가장 큰 순열이다 , 내림차순이다)
		if(i == 0) return false;
		
		//꼭대기를 찾았으면
		int j = N-1;
		while(input[i-1] >= input[j]) --j;
		
		//SWAP
		swap(i-1,j);
		
		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;
	}
	
}