Python으로 최대 Bitwise AND와 Bitwise OR 합을 갖는 부분 수열 찾기

n개의 원소로 이루어진 배열이 주어졌을 때, 두 개의 부분 수열(서로 같아도 달라도 무방합니다)을 선택하여 첫 번째 부분 수열의 모든 원소에 대한 비트 AND 연산 결과와 두 번째 부분 수열의 모든 원소에 대한 비트 OR 연산 결과의 합이 최대가 되도록 만들어야 합니다.

예를 들어 입력이 A = {4, 6, 7, 2}라면 출력은 14가 됩니다. 7 하나만 선택했을 때 최대 AND 값인 7을 얻을 수 있고, 모든 원소를 선택했을 때 최대 OR 값인 (4 | 6 | 7 | 2) = 7을 얻을 수 있기 때문입니다. 따라서 최종 결과는 7 + 7 = 14입니다.

핵심 아이디어

이 문제는 비트 연산의 성질을 이용하면 매우 간단하게 해결할 수 있습니다.

• 최대 AND 값: AND 연산은 원소를 추가할수록 결과가 작아지거나 같아질 뿐 커지지 않습니다. 따라서 단일 원소만 선택하는 것이 가장 유리하며, 최대 AND 값은 곧 배열의 최댓값과 같습니다.
• 최대 OR 값: OR 연산은 원소를 추가할수록 켜지는 비트가 늘어나 값이 커지거나 같아집니다. 따라서 배열의 모든 원소를 OR한 값이 최대 OR 값이 됩니다.

알고리즘 단계

• and_max := 배열의 최댓값
• or_max := 0
• i를 0부터 배열 크기까지 반복:
  • or_max := or_max OR arr[i]
• and_max + or_max 반환

구현 예제

다음 Python 코드를 통해 더 잘 이해할 수 있습니다.

def get_max_sum(arr):
    and_max = max(arr)
    or_max = 0
    for i in range(len(arr)):
        or_max |= arr[i]
    return and_max + or_max

a = [4, 6, 7, 2]
print(get_max_sum(a))

입력

[4, 6, 7, 2]

출력

14

복잡도 분석

배열을 한 번만 순회하면서 최댓값과 OR 누적값을 계산하므로 시간 복잡도는 O(n), 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 배열의 크기가 커져도 효율적으로 동작하는 최적의 해법입니다.