[백준/23630/파이썬] 가장 긴 부분 수열 구하기 풀이 (비트마스킹, Python + 수열까지 구하는 코드 포함)
[백준/23630/파이썬] 가장 긴 부분 수열 구하기 풀이(비트마스킹, Python) 1. 문제https://www.acmicpc.net/problem/236302. 문제 풀이 1. 비트마스킹을 이용하여 푸는 문제이다. → 전체 부분 수열 조합을 구해서 보지 않고, 비트별로 공통된 1이 있는 자리의 수들만 뽑는 아이디어로 해결한다 2. AND 연산을 했을 때, 결과가 0이 되지 않도록 하기 위해서는, 선택된 수들의 모든 비트 중 적어도 하나는 공통적으로 1이어야 한다.3. 따라서 각 비트 위치(0~20)에 대해, 해당 비트가 1인 수가 몇 개 있는지를 세기 위해 길이 21짜리 count 배열을 만든다.(예: [0, 0,..., 0], 길이 21) ※ 길이가 21인 이유?N은 1,000,000가 최대이..
2025. 6. 12.
