https://www.acmicpc.net/problem/24023
문제 이해
문제 요약
- 목표: 주어진 배열
A에서 연속된 구간을 선택하여, 그 구간의 모든 원소에 대해 비트 OR을 수행했을 때 정확히K가 되는 구간을 찾는 것입니다. 만약 여러 구간이 존재하면 아무거나 하나를 출력하고, 존재하지 않으면1을 출력합니다. - 입력:
- 첫 번째 줄: 배열의 크기
N과 목표 OR 값K(1 ≤ N ≤ 200,000,1 ≤ K ≤ 2^{30}-1) - 두 번째 줄: 배열
A의N개의 정수 (1 ≤ A_i ≤ 2^{30}-1)
- 첫 번째 줄: 배열의 크기
- 출력:
- 조건을 만족하는 구간이 존재하면, 그 구간의 시작 인덱스
s와 끝 인덱스e를 출력 (1기반 인덱스) - 존재하지 않으면
1을 출력
- 조건을 만족하는 구간이 존재하면, 그 구간의 시작 인덱스
예제 분석
예제 입력 1:
5 7
8 1 2 5 9
예제 출력 1:
2 4
- 설명: 배열
[1, 2, 5]의 비트 OR은1 | 2 | 5 = 7입니다.
예제 입력 2:
5 6
2 7 4 1 4
예제 출력 2:
-1
- 설명: 어떤 연속된 구간의 비트 OR도
6이 되지 않습니다.
해결 방법
접근 방식
이 문제는 연속된 구간의 비트 OR을 효율적으로 계산하고, 그 중 원하는 값 K가 되는 구간을 찾는 문제입니다. 배열의 크기가 최대 200,000이므로, 시간 복잡도가 O(N^2)인 브루트 포스 방식은 비효율적입니다. 대신, 동적 계획법(DP)을 사용하여 각 위치에서 가능한 비트 OR 결과를 추적하는 효율적인 방법을 사용합니다.
동적 계획법(Dynamic Programming) 적용
- DP 배열 정의:
dp[i]:i번째 원소까지 고려했을 때, 구간의 비트 OR 결과가 특정 값인 경우를 추적합니다.- 하지만 모든 가능한 OR 값을 추적하는 것은 비효율적이므로, 각 단계에서 현재 위치에서 가능한 모든 OR 값을 추적합니다.
- 현재 가능한 OR 값 추적:
- 이전 단계(
i-1)에서 가능한 모든 OR 값에 현재 원소A[i]를 OR하여 새로운 OR 값을 생성합니다. - 또한, 현재 원소
A[i]자체로 새로운 구간을 시작할 수도 있습니다.
- 이전 단계(
- 효율성:
- 비트 OR의 특성상, 각 단계에서 가능한 OR 값의 수는 제한적입니다 (최대 30개,
2^{30}까지). - 따라서, 각 단계에서 가능한 OR 값을 효율적으로 관리할 수 있습니다.
- 비트 OR의 특성상, 각 단계에서 가능한 OR 값의 수는 제한적입니다 (최대 30개,
- 구간 찾기:
- 각 OR 값과 함께 해당 OR 값을 만들기 위한 구간의 시작 인덱스를 추적합니다.
- 원하는 OR 값
K가 발생하면 해당 구간의 시작과 끝 인덱스를 기록합니다.
알고리즘 단계
- 초기화:
- 이전 단계에서 가능한 OR 값과 그에 해당하는 구간의 시작 인덱스를 저장할
prev_or를 초기화합니다. - 결과를 저장할 변수
result를(-1, -1)로 초기화합니다.
- 이전 단계에서 가능한 OR 값과 그에 해당하는 구간의 시작 인덱스를 저장할
- 배열 순회:
- 배열을 처음부터 끝까지 순회하면서, 각 위치에서 가능한 모든 OR 값을 계산하고 추적합니다.
- 각 단계에서:
current_or를 새롭게 계산한 OR 값과 그에 해당하는 시작 인덱스를 저장합니다.current_or에K가 포함되어 있으면, 해당 구간의 시작과 현재 인덱스를result에 저장합니다.
- 결과 출력:
result가 업데이트되었으면 해당 구간을 출력하고, 그렇지 않으면1을 출력합니다.
def find_subarray_with_or(N, K, A):
MOD = 10**9 + 9
prev_or = dict()
result = (-1, -1)
for i in range(N):
current_or = dict()
# 현재 원소 자체로 시작하는 구간
current_or[A[i]] = i
# 이전 단계에서 가능한 모든 OR 값에 현재 원소를 OR
for or_val, start_idx in prev_or.items():
new_or = or_val | A[i]
# 이미 기록된 OR 값이 있으면 더 이른 시작 인덱스를 유지
if new_or not in current_or or current_or[new_or] > start_idx:
current_or[new_or] = start_idx
# 현재 단계에서 OR 값이 K인 경우를 확인
if K in current_or:
s = current_or[K] + 1 # 1-based indexing
e = i + 1
result = (s, e)
break # 원하는 구간을 찾았으므로 종료
prev_or = current_or
return result if result != (-1, -1) else -1
def main():
import sys
import sys
input = sys.stdin.readline
N_K = input().split()
while len(N_K) < 2:
N_K += input().split()
N, K = map(int, N_K)
A = []
while len(A) < N:
A += list(map(int, input().split()))
res = find_subarray_with_or(N, K, A)
if res == -1:
print(-1)
else:
print(res[0], res[1])
if __name__ == "__main__":
main()
코드 분석
1. 함수 정의
def find_subarray_with_or(N, K, A):
MOD = 10**9 + 9
prev_or = dict()
result = (-1, -1)
for i in range(N):
current_or = dict()
# 현재 원소 자체로 시작하는 구간
current_or[A[i]] = i
# 이전 단계에서 가능한 모든 OR 값에 현재 원소를 OR
for or_val, start_idx in prev_or.items():
new_or = or_val | A[i]
# 이미 기록된 OR 값이 있으면 더 이른 시작 인덱스를 유지
if new_or not in current_or or current_or[new_or] > start_idx:
current_or[new_or] = start_idx
# 현재 단계에서 OR 값이 K인 경우를 확인
if K in current_or:
s = current_or[K] + 1 # 1-based indexing
e = i + 1
result = (s, e)
break # 원하는 구간을 찾았으므로 종료
prev_or = current_or
return result if result != (-1, -1) else -1
주요 변수
prev_or: 이전 단계에서 가능한 모든 OR 값과 그에 해당하는 구간의 시작 인덱스를 저장하는 딕셔너리.current_or: 현재 단계에서 가능한 모든 OR 값과 그에 해당하는 구간의 시작 인덱스를 저장하는 딕셔너리.result: 조건을 만족하는 구간의 시작과 끝 인덱스를 저장하는 튜플. 초기값은(-1, -1)로 설정하여, 조건을 만족하는 구간이 없을 경우1을 출력할 수 있도록 합니다.
단계별 동작
-
현재 원소로 시작하는 구간 추가:
current_or[A[i]] = i- 현재 원소
A[i]자체로 시작하는 구간의 OR 값과 시작 인덱스를current_or에 저장합니다.
- 현재 원소
-
이전 단계 OR 값과 현재 원소의 OR 계산:
for or_val, start_idx in prev_or.items(): new_or = or_val | A[i] if new_or not in current_or or current_or[new_or] > start_idx: current_or[new_or] = start_idx- 이전 단계에서 가능한 모든 OR 값
or_val에 현재 원소A[i]를 OR하여 새로운 OR 값new_or를 계산합니다. new_or가 이미current_or에 존재하지 않거나, 더 이른 시작 인덱스를 가지고 있다면 업데이트합니다.
- 이전 단계에서 가능한 모든 OR 값
-
조건 만족 여부 확인:
if K in current_or: s = current_or[K] + 1 # 1-based indexing e = i + 1 result = (s, e) break- 현재 단계에서 OR 값이
K인 경우를 확인합니다. - 해당 구간의 시작 인덱스
s와 끝 인덱스e를 계산하여result에 저장하고, 더 이상의 탐색을 종료합니다.
- 현재 단계에서 OR 값이
-
다음 단계로 이동:
prev_or = current_or- 현재 단계의 OR 값을 다음 단계의 이전 OR 값으로 설정합니다.
2. 메인 함수
def main():
import sys
import sys
input = sys.stdin.readline
N_K = input().split()
while len(N_K) < 2:
N_K += input().split()
N, K = map(int, N_K)
A = []
while len(A) < N:
A += list(map(int, input().split()))
res = find_subarray_with_or(N, K, A)
if res == -1:
print(-1)
else:
print(res[0], res[1])
if __name__ == "__main__":
main()
주요 동작
- 입력 처리:
- 첫 번째 줄에서
N과K를 입력받습니다. - 두 번째 줄에서 배열
A의N개의 원소를 입력받습니다. - 입력이 여러 줄에 걸쳐 주어질 수 있으므로, 필요한 만큼 입력을 반복적으로 받습니다.
- 첫 번째 줄에서
- 함수 호출 및 결과 출력:
find_subarray_with_or함수를 호출하여 결과를 얻습니다.- 결과가
1이면1을 출력하고, 그렇지 않으면 구간의 시작과 끝 인덱스를 출력합니다.
시간 복잡도 분석
알고리즘 단계별 분석
- 배열 순회:
- 반복문:
for i in range(N) - 시간 복잡도:
O(N)
- 반복문:
- OR 값 계산 및 갱신:
- 내부 반복문:
for or_val, start_idx in prev_or.items() - OR 값의 개수: 각 단계에서 가능한 OR 값의 수는 최대 30개 (비트 수)
- 시간 복잡도:
O(30)→O(1)(상수 시간) - 전체 시간 복잡도:
O(N) * O(1) = O(N)
- 내부 반복문:
- 조건 확인 및 조기 종료:
- 구간을 찾으면 즉시 종료하므로, 최악의 경우 전체 배열을 순회합니다.
전체 시간 복잡도
- 총 합계:
O(N) - 설명: 배열을 한 번 순회하며, 각 위치에서 상수 시간 내에 가능한 OR 값을 갱신하고 조건을 확인합니다.
공간 복잡도 분석
주요 자료구조
prev_or와current_or딕셔너리:- 각 딕셔너리는 가능한 OR 값과 그에 해당하는 시작 인덱스를 저장합니다.
- OR 값의 개수: 최대 30개
- 공간 복잡도:
O(30)→O(1)(상수 공간)
- 기타 변수:
result: 튜플- 기타 변수: 상수 공간 사용
- 공간 복잡도:
O(1)
전체 공간 복잡도
- 총 합계:
O(1) - 설명: 사용되는 딕셔너리의 크기가 상수로 제한되어 있어, 전체적으로 상수 공간을 사용합니다.
알고리즘 및 자료구조 설명
알고리즘: 동적 계획법 (Dynamic Programming)
- 특징:
- 재사용: 이전 단계에서 계산된 결과를 재사용하여 효율성을 높입니다.
- 점화식 기반: 현재 상태를 이전 상태들로부터 유도합니다.
- 이 문제에서의 적용:
- 각 위치에서 가능한 모든 OR 값을 추적하여, 새로운 OR 값을 효율적으로 계산합니다.
- 비트 OR의 특성상, 각 단계에서 가능한 OR 값의 수는 제한적이므로, 효율적인 계산이 가능합니다.
자료구조: 딕셔너리 (Dictionary)
prev_or와current_or:- 역할: 이전 단계와 현재 단계에서 가능한 모든 OR 값과 그에 해당하는 구간의 시작 인덱스를 저장합니다.
- 장점:
- 빠른 접근: 키를 통한
O(1)시간 내의 접근이 가능합니다. - 중복 방지: 동일한 OR 값을 여러 번 계산하지 않도록 관리합니다.
- 빠른 접근: 키를 통한
