[Java] 비트 마스킹, Next_Permutation

1. 비트연산 연산자 설명 예시 & 비트 AND 연산 5 & 3 = 1 ^ 비트 XOR(배타적 OR) 연산 5 ^ 3 = 6 ~ 비트 NOT 연산 (1의 보수) ~5 = -6 > 2 = 1 >>> 부호 없는 오른쪽 시프트 연산 -5 >>> 2 = 1073741822 2. 비트마스킹 가. 순열 nPn → n! 이다. (보통 10!을 넘어서면 힘들다.) 비트마스킹을 사용해서 공간복잡도를 줄일 수 있다. 기존에는 boolean[] 또는 int[] 를 사용해서 방문 체크를 수행했다. 비트마스킹을 활용하면 int 하나에도 모두 저장할 수 있다. input[] // 숫자 배열 numbers[] // 순열 저장 배열 perm(cnt, flag) if cnt == N 순열 생성 완료 else for i from 0 t..

2024.02.18