Coding Test/알고스팟
[C++] 알고스팟/비트마스크 - 졸업 학기
Junchoi
2020. 3. 29. 17:14
문제 링크
https://algospot.com/judge/problem/read/GRADUATION
algospot.com :: GRADUATION
졸업 학기 문제 정보 문제 1학년은 노는 게 남는 거란 선배의 말을 철석같이 믿고, 전공 과목은 다 수강철회하고 교양 과목은 다 F 받는 방탕한 1학년을 보냈던 태우는 이제 와서 자신의 행동을 후회하고 있습니다. 졸업 전에 채워야 할 학점이 너무 많기 때문입니다. 졸업 필수 학점을 채우려면 전공 과목 N 개 중 K 개 이상을 수강해야 합니다. 그런데 각 과목은 해당 과목의 선수과목을 미리 수강했어야만 수강할 수 있으며, 각 학기마다 모든 과목이 개설되는
algospot.com
졸업에 필요한 과목을 듣는데 다녀야 할 최소 학기를 구하는 문제입니다.
전공과목, 학기에 대한 정보가 주어졌을 때 이 값들을 비트 마스크를 사용하여 값을 저장하고 변경함으로써 실행 시간을 줄일 수 있습니다.
문제를 풀기전에 기본적으로 알아두면 좋은 비트 연산자와 비트마스크 입니다.
비트 연산자
| 코드 | 설명 | 예시 |
| a & b | a, b의 AND 연산 | 4 & 2 = 100 & 010 = 000 |
| a | b | a, b의 OR 연산 | 4 | 2 = 100 | 010 = 110 |
| a ^ b | a, b의 XOR 연산 | 4 ^ 2 = 100 ^ 010 = 110 |
| ~a | a의 NOT 연산 | ~4 = ~100 = 011 |
| a << b | a를 왼쪽으로 b비트 시프트 | 4 << 2 = 10000 |
| a >> b | a를 오른쪽으로 b비트 시프트 | 4 >> 2 = 1 |
비트마스크
| 코드 | 설명 | 예시 |
| a |= (1 << b) | 정수 a의 b번 비트를 켬 | 1000 |= (1 << 2) = 1100 |
| if( a & (1 << b) ) |
정수 a의 b번 비트가 켜있는지 확인 (포함 시 1<<b, 아닐 시 0) |
1000 & (1 << 2) = 0 1000 & (1 << 3) = 8 |
| a &= ~(1 << b) | 정수 a의 b번 비트를 끔 | 111 &= ~(1 << 0) = 110 |
| a ^= (1 << b) | 정수 a의 b번 비트를 토글 | 111 ^= (1 << 1) = 101 |
| (a & -a) |
a의 최소원소 반환 (10100 의 최소 원소 = 100 = 4) |
( 10100 & -10100) = 100 |
| a &= (a-1) | a의 최소원소 지우기 | 10100 &= (10100 - 1) = 10000 |
주어지는 입력 값이 많아 헷갈리므로 각 입력 값들의 의미를 자세히 파악해야 합니다.
아래는 첫번째 테스트케이스에 사용되는 입력 값들입니다.
구현 코드