[Algorithm] 이중 포문 조정 - 구간합

개요

시간복잡도 줄이는 법을 학습하면서 해본 정리

코드트리를 참고하였다!

 

---

어떤 배열에서 특정 합을 만족하며 가장 크기가 큰 구간의 크기를 찾기 위해 완전탐색을 하면 다음과 같다.

 

완전탐색 - O(N**3)

# 이 배열에서 특정 구간을 골라서, 
# 합이 10이 넘지 않아야 하고,
# 배열의 크기가 가장 커야 한다. 이때의 배열 크기는?

arr = [0,6,3,2,4,9,1]
n = len(arr)
target=10

# 무식하게 구해보기
for i in range(1, n+1):
    for j in range(i, n+1):
        total = 0
        for k in range(i, j+1):
            total += arr[k]
        
        if total <= target:
            ans = max(ans, j-i+1)

 

이 코드의 복잡도는 O(N**3)이다.

복잡도를 줄여보자.

 

---

 

구간 내 시작점과 끝 활용 - O(N**2)

# 일단 모든 구간 탐색
for i in range(1,n+1):
    total=0
    for j in range(i,n+1):
        total += arr[j]
    
    # 특정합이 타겟합을 넘었을 때
    if total > target : break

    ans = max(ans, j-i+1)

 

 

*이 경우, j는 i 값이 달라질 때마다 i에서 새로 시작하므로 후퇴하는 경우가 많이 발생하게 된다. ➡️ 시간복잡도는 O(N**2)

 

 

# while로 표현해보면
total=0
j=0

for i in range(1,n+1):
    while j+1 <= n and total + arr[j+1] <= target:
        total += arr[j+1]
        j += 1
    
    ans = max(ans, j-i+1)
    
    # 다음 구간으로 넘어가기 전에 arr[i]의 값은 해당 구간에서 제외한다.
    total -= arr[i]

 

투 포인터는 이렇게 i, j가 한 방향으로 전진하면서 연산을 수행하는 형태를 갖는다. ➡️ 시간복잡도는 O(N)

 

이 i, j 전진 테크닉은 실제로 이중 포문으로 작성되어 있지만, i와 j가 한 방향으로 진행되기 때문에 시간 복잡도는 두 for loop의 곱이 아니라 합으로 나타내진다.

 

---

구간 내 특정 합이 존재하고, 중복되는 값 Counting

같은 숫자가 3개 이상 있지 않은 경우 중, 가장 큰 구간의 크기

### 같은 숫자가 3개 이상 있지 않은 경우 중, 가장 큰 구간의 크기
n,s=map(int,input().split())
arr=[0] + list(map(int,input().split()))


# 각 숫자마다 몇 번씩 나왔는지 카운팅하는 배열을 추가적으로 만들어 관리한다.
## cnt_arr의 인덱스는 숫자 정보, value는 해당 숫자가 등장한 개수
cnt_arr=[0]*4


ans=0
j=0
for i in range(1,n+1):
    while j+1 <= n and cnt_arr[arr[j+1]] != 2:
        cnt_arr[arr[j+1]]+=1
        j+=1
    
    ans=max(ans,j-i+1)
    # 하나 제거
    cnt_arr[arr[i]] -= 1