완전 탐색을 쌈싸먹기 전, 관련 개념을 알아보자 🧐
비트 마스크
bit 연산을 이용해 부분 집합을 나타내는 방법
집합을 배열의 인덱스로 표현할 수 있기 때문에 상태 다이나믹을 할 때 자주 사용한다.
STL의 bitset을 이용해서 더 쉽게 사용할 수 있다!
종류
- and (&) : 둘 다 1일 때 1
- or (|) : 둘 중 하나라도 1이면 1
- not (~) : 0이면 1, 1이면 0
- xor (^) : 같으면 0, 다르면 1
비트 연산
- 두 수 A와 B를 비트 연산 하는 경우, 가장 뒤의 자리부터 하나씩 연산을 수행한다.
- not 연산의 경우
- 자료형에 따라 결과 달라진다. 비트가 자료형에 따라 달라지니까!
- 8비트 자료형, 32비트 자료형, unsigned, signed...
- 자료형에 따라 결과 달라진다. 비트가 자료형에 따라 달라지니까!
- shift left (<<), shift right (>>)
- A << B : A를 왼쪽으로 B비트만큼 민다. A * 2^B와 동일
- 1 << 1 : 10이니까 2
- A >> B : A를 오른쪽으로 B비트만큼 민다. A / 2^B와 동일
- 10 >> 2 : 10이니까 2
- (A+B)/2 = (A+B) >> 1
- A << B : A를 왼쪽으로 B비트만큼 민다. A * 2^B와 동일
비트 마스크
- 정수로 집합(S)을 나타낼 수 있다.
- {1, 3, 4, 5, 9] = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9 = 1000111010
- 어떤 수(i)의 포함 여부를 확인하기 위해 & 연산을 이용한다.
- S & (1 << i)
- 0이 포함되어 있는지 검사
- 570 & 2^0 = 570 & (1<<0) = 1000111010 & 1 = 0
- 1이 포함되어 있는지 검사
- 570 & 2^1 = 570 & (1<<1) = 1000111010 & 10 = 10 = 2
- 2가 포함되어 있는지 검사
- 570 & 2^2 = 570 & (1<<2) = 1000111010 & 100 = 000 = 0
- 어떤 수(i)를 새로 추가하기 위해 | 연산을 이용한다.
- S | (1 << i)
- 2 추가하기
- 570 | 2^2 = 570 | (1<<2) = 1000111010 | 100 = 1000111110 = 574
- 만약 이미 존재하는 수를 새로 추가한다면? 그대로!
- 1 추가하기
- 570 | 2^1 = 570 | (1<<1) = 1000111010 | 10 = 1000111010 = 570
- 어떤 수(i)를 제거하기 위해 ~ 연산을 이용한다.
- S & ~(1 << i)
- 1 제거하기
- 570 & ~2^1 = 570 & ~(1<<1) = 570 & ~(10) = 1000111010 & ~(01) = 1000111010 & 1111111101 = 1000111000 = 568
- 어떤 수(i)를 토글하기 위해 ^ 연산을 이용한다.
- S ^ (1 << i)
- 전체 집합 : (1<<N) - 1
- 공집합 : 0
문제 예제 (1) : 백준 집합
내 풀이
- 고냥 저항없이 위에서 공부한대로 코드를 짰다.
- 그랬더니 시간 초과~~~😇
- 입력은 버퍼로 받았으니 아마 출력하는 부분이 문제겠지 싶어서 StringBuilder를 사용하도록 코드를 수정해줬다.
- 수정해주니 통과했다. 굿굿 앞으론 스트링빌더를 걍 습관처럼 써줘야지
순열
1~N까지로 이루어진 수열.
크기는 항상 N이며, 겹치는 숫자가 존재하지 않아야 한다.
다음 순열
순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법
다음 순열 찾는 법 (O(n))
예시 순열 : 7 2 3 6 5 4 1
- A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾는다.
- 가장 큰 i니까 오른쪽에서 부터 체크!
- 즉 순열의 마지막 수에서 끝나는 가장 긴 감소 수열 찾기.
- A[i-1] = 3, A[i] = 6. i = 3
- 감소수열은 6 5 4 1
- 즉 순열의 마지막 수에서 끝나는 가장 긴 감소 수열 찾기.
- 가장 큰 i니까 오른쪽에서 부터 체크!
- j >= i 면서 A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다.
- 가장 큰 j니까 오른쪽에서 찾아야!
- A[j] = 4. j = 5
- A[i-1]과 A[j]를 swap한다
- 7 2 4 6 5 3 1
- A[i]부터 순열을 뒤집는다.
- 7 2 4 1 3 5 6
다음 순열에서 제일 첫 번째 순열은 오름차순, 제일 마지막 순열은 내림차순이다.
따라서 다음 순열을 구할 때, 특정 인덱스에서 사전 순 다음 값의 조건은
- 현재 값보다 크면서
- 현재 값 다음 인덱스의 수들 중 제일 작은 값이어야 한다
을 충족해야 한다.
문제 예제 (2) : 백준 다음 순열
내 풀이
- 이번에도 저항없이... 위에서 공부한 다음 순열 구하는 방식을 그대로 코드로 구현했다.
- System.out을 이용한 경우
- StringBuilder를 이용한 경우
문제 예제 (3) : 백준 이전 순열
내 풀이
- 다음 순열 구했던거랑 반대로 구하면 된다.
- 맞았당ㅎ.ㅎ
문제 예제 (4) : 백준 모든 순열
내 풀이
- 다음 순열 구했던걸 응용하면 된다.
- 맞았다
문제 예제 (5) : 백준 순열의 순서
내 풀이
- 두번째 입력의 첫번째 수가 1이면 k번째 순열을, 2면 뒤이어 입력한 순열이 몇 번째 순열인지 찾으면 된다.
- 완전 아무 생각 없이 풀면, 위에서 풀었던 다음 순열을 응용하면 된다.
- 순서 변수 하나 만들어서, 다음 순열 함수가 호출될 때마다 카운트하는 방식.
- 근데 이게 좋은 풀이일까? 🤔
- 아아아아아주 오래 전 공부했던 확통 지식을 되살려보면, 순열의 개수는 팩토리얼로 구했다.
- ex. 1~N으로 이루어진 순열의 크기는 N!
- 요건 각 자리에 올 수 있는 숫자의 개수로 만든 공식이다.
- N= 5일 때, 맨 처음에 올 수 있는 수는 1, 2, 3, 4, 5니까 5, 두번째 올 수 있는 수는 앞에 나온 수 제외하고 전부니까 5, ... 하는 식으로.
- 요걸 잘 응용하면 되지 않을까?
- 왜냐하면 문제 조건에서 순열의 순서는 사전순 (오름차순)이라고 했으니까!
- 예를 들어 N=3일 때 { 1 2 3 } 의 순서를 찾아보자.
- 각 자리수에 올 수 있는 첫번째 숫자들이 배치되어 있으니, 0 x 0 x 0 = 0. 첫번째 순열을 고려해서 +1해주면 k = 1.
- 이번엔 { 3 2 1 }
- 첫번째 자리수에 3은 세번째로 올 수 있는 수다. 따라서 2! x 2 = 4
- 두번째 자리수에 2는 두번째로 올 수 있는 수다. 따라서 1
- 세번째 자리수에 1은 처음으로 올 수 있는 수다. 따라서 0
- 4 + 1 + 1(첫번째) = 6
- 실제로 순열을 전부 나열해보면 아래와 같으므로 6번째 순열이 맞다.
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
- 옹 일단 순서는 구할 수 있겠다! 그럼 이제 순서가 주어졌을 때 순열을 찾는 방법을 고민해보자.
- 위에서 생각한 순서 찾는 로직을 응용하면 된다. 주어진 숫자가 전체 수 N에서 몇 번째 순서에 위치해있는지를 알면 쏘~~~이지
- ex. 1~N으로 이루어진 순열의 크기는 N!
호그와트 장학생