[백준/23630/파이썬] 가장 긴 부분 수열 구하기 풀이 (비트마스킹, Python + 수열까지 구하는 코드 포함)

[백준/23630/파이썬] 가장 긴 부분 수열 구하기 풀이

(비트마스킹, Python)

백준 23630 파이썬 가장 긴 부분 수열 구하기 python

 

 

 

1. 문제

https://www.acmicpc.net/problem/23630

---

2. 문제 풀이

 

1. 비트마스킹을 이용하여 푸는 문제이다.

→ 전체 부분 수열 조합을 구해서 보지 않고, 비트별로 공통된 1이 있는 자리의 수들만 뽑는 아이디어로 해결한다

---

2. AND 연산을 했을 때, 결과가 0이 되지 않도록 하기 위해서는, 선택된 수들의 모든 비트 중 적어도 하나는 공통적으로 1이어야 한다.

---

3. 따라서 각 비트 위치(0~20)에 대해, 해당 비트가 1인 수가 몇 개 있는지를 세기 위해 길이 21짜리 count 배열을 만든다.
(예: [0, 0,..., 0], 길이 21)

 

※ 길이가 21인 이유?

N은 1,000,000가 최대이다.

N을 2진수로 바꾸면 0b11110100001001000000 이므로, 0을 포함해서 총자릿수가 21개로 나온다. 

 

---

4. 부분 수열 A에 있는 값들을 모두 순회하면서, 각 수의 2진수 표현에서 1~20까지 AND 연산을 해서,

1이 나오면 카운트 배열의 해당 인덱스에 1을 더한다. 

 

※  참고로,

만약 수열 A에 현재 비교값이 4이면 2진수로 바꾸면 100이 되고

1~20번째 자릿수까지 and연산을 했을 때 

100의 2번째 자리 1과 같이 '1'인 비트 자리만 살아남게 되므로

count배열 [2] 번째에 값을 +1 하게 된다.

countList = [0, 0, 1, 0, 0, 0, ..., 0]  # index 2번만 1

 

---

5. 최종적으로 count 배열에서 가장 큰 값을 출력한다.

이는 공통적으로 1이 있는 비트 위치 중, 가장 많은 수가 가진 비트이므로

해당 비트를 1로 가지고 있는 수들로 이루어진 부분 수열은 AND 연산 시 절대로 0이 되지 않으며,

가장 긴 부분 수열의 길이가 된다.

 

 

※ 예시 (챗지피티)

A = [6, 3, 5]

비트로 보면:
6 = 110
3 = 011
5 = 101

비트 위치별로 1이 몇 번 나왔는지 보자

비트 위치 (0부터 시작)
------------------------
0번 비트 (가장 오른쪽) → 6(X), 3(O), 5(O) → 2개
1번 비트 → 6(O), 3(O), 5(X) → 2개
2번 비트 → 6(O), 3(X), 5(O) → 2개

세 개 다 2개씩 나왔어

즉, 2개 이상에서 살아있는 비트가 있는 곳이 있어요.
그럼 그 비트에 1이 있는 애들끼리 묶으면 AND가 0이 안 됨!

count 배열 : [2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
(0,1,2 번째 비트가 1인 수가 각각 2개씩 있다는 뜻)

 

 

---

3. 코드

3-1. 정답 코드 (조건을 만족하는 개수만 출력)

from sys import stdin

N = int(stdin.readline()) # * 수열 A의 길이
# 수열 A의 각원소 Ai가 공백으로 주어진다.
aList = list(map(int, input().split()))
countList = [0 for _ in range(21)] # * 개수를 셀 0 ~ 20까지 길이 (N이 최대 1,000,000 이므로)

# 2. A를 순회하면서 1을 카운트에 넣어준다.
for a in aList:
  for i in range(21) : # 0~20번 비트만 확인 
    if a & (1 << i): # 현재 번호랑 1~20까지 맞는게 있다면
      countList[i] += 1 # 추가 
print(max(countList)) # 가장 많이 나온 비트 수 출력

 

 

---

3-2. 조건을 만족하는 수열까지 출력하는 코드

언젠가 다른 코딩테스트를 치면, 조건을 만족하는 수열까지 출력하라는 문제가 나올 수도 있을 것 같아서 추가해 보았다.

// ... 위의 코드와 동일 ... // 

# -------------
# * 만약 수열까지 출력하고 싶다면?

max_count = max(countList)
target_bit = countList.index(max_count) # 가장 많이 등장한 비트 인덱스 구하기
result = []

# 3. 해당 비트가 1인 숫자들만 추출한다.
for a in aList:
  if a & (1 << target_bit):
    result.append(a)

print(result)

1. 가장 많이 등장한 비트의 인덱스를 구한다. ( = 가장 1이 많은 비트의 자리를 구한다)

2. 부분수열을 순회하면서, 해당 숫자와 구해놓은 자릿수와 and를 해서 1이 나온다면, 포함되는 수열이 된다.

 

---

 

4. 마무리

비트마스킹 문제가 아직 생소해서 어려웠다.

더 공부가 필요한 것 같다.

 

---

 

읽어주셔서 감사합니다~

도움이 되셨다면 공감 부탁드립니다 😊

피드백도 환영입니다!