32. 동적 계획법 3
CLASS 3 ESSENTIAL
집합에 원소를 추가/삭제 등의 연산을 구현하는 문제입니다. 다만 문제의 조건이 원소는 1에서 20까지의 수만 주어지고, 연산 3,000,000개를 1.5초안에 모두 연산해야한다는 점입니다. 집합의 특성 상 한 원소가 여러 개 존재할 수 없다는 점을 이용해서 1에서 20까지의 각 원소가 집합에 존재하는지를 1비트에 저장하는 방법을 이용할 수 있습니다. 이렇게 하면 총 필요한 데이터의 크기는 20비트로 int 변수 하나에 다 담을 수 있습니다. 배열을 사용하지 않는 이유는 all 연산과 empty 연산 때문인데, 배열을 이용하여 구현하면 20번의 연산이 필요한 것을 int 변수 하나를 사용하면 단 한 번의 연산으로 구현이 가능합니다. 나머지 연산은 비트 연산자를 이용하여 구현할 수 있습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-12-19 15:38:06 |