[알고리즘] 5일차 (DNA 비밀번호, 최솟값 찾기 1) #백준12891번 #백준11003번

03-4 슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제를 해결한다. 투 포인터 알고리즘과 매우 비슷하고 원리도 간단하므로 설명 없이 바로 실전 문제를 풀며 슬라이딩 윈도우 알고리즘 개념과 원리를 공부해보자.

📌 문제 009) DNA 비밀번호

시간 제한 2초, 실버 V, 백준 12891번

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.
하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙을 만들었다.
임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하자. 그리고 부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다고 하자. 이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다. 하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다.
민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분분자열의 길이, 그리고 {‘A’, ‘C’, ‘G’, ‘T’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

입력

첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000)
두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다.
세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다.

9 8 # DNA 문자열의 길이, 부분 문자열의 길이
CCTGGATTG # DNA 문자열
2 0 1 1 # 부분 문자열에 포함돼야 할 A, C, G, T의 최소 개수

출력

첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.

0

1단계 문제 분석

• P와 S 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 풀어야 한다. 부분 문자열 길이가 P이므로 슬라이딩 윈도우 개념을 이용한다.
• 문자열 크기를 유지한 채로 길이가 P인 윈도우를 지정하여 리스트 S의 시작점에 놓는다. 그런 다음 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색한다.
• 리스트 S의 길이만큼 탐색하면 되므로 O(n)의 시간 복잡도로 문제를 해결할 수 있다.

2단계 슈도 코드

checkList(비밀번호 체크 리스트)
myList(현재 상태 리스트)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)

# 함수 선언
myadd(문자 더하기 함수):
	myList에 새로운 값을 더하고 조건에 따라 checkSecret값 업데이트
    
myremove(문자 빼기 함수):
	myList에 새로운 값을 제거하고 조건에 따라 checkSecret값 업데이트

# 메인 코드
S(문자열 크기) P(부분 문자열의 크기)
A(문자열 데이터)
checkList 데이터 받기
checkList를 탐색하여 값이 0인 데이터의 개수만큼 checkSecret 값 증가
# 값이 0이라는 것은 비밀번호 개수가 이미 만족되었다는 뜻
P 범위(0~P-1)만큼 myList 및 checkSecert에 적용하고, 유효한 비밀번호인지 판단

for i를 P에서 S까지 반복:
	j 선언(i - P)
    # 이 부분은 myadd, myremove 함수로 별도 구현
    한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열을 처리
    유효한 비밀번호인지(checkSecret == 4) 판단해 결괏값을 업데이트

결괏값 출력

3단계 코드 구현

checkList = [0] * 4
myList = [0] * 4
checkSecret = 0

# 함수 정의
def myadd(c): # 새로 들어온 문자를 처리하는 함수
    global checkList, myList, checkSecret
    if c == 'A':
        myList[0] += 1
        if myList[0] == checkList[0]:
            checkSecret += 1
    elif c == 'C':
        myList[1] += 1
        if myList[1] == checkList[1]:
            checkSecret += 1
    elif c == 'G':
        myList[2] += 1
        if myList[2] == checkList[2]:
            checkSecret += 1
    elif c == 'T':
        myList[3] += 1
        if myList[3] == checkList[3]:
            checkSecret += 1
            
def myremove(c): # 제거되는 문자를 처리하는 함수
    global checkList, myList, checkSecret
    if c == 'A':
        if myList[0] == checkList[0]:
            checkSecret -= 1
        myList[0] -= 1
    elif c == 'C':
        if myList[1] == checkList[1]:
            checkSecret -= 1
        myList[1] -= 1
    elif c == 'G':
        if myList[2] == checkList[2]:
            checkSecret -= 1
        myList[2] -= 1
    elif c == 'T':
        if myList[3] == checkList[3]:
            checkSecret -= 1
        myList[3] -= 1

S, P = map(int, input().split())
Result = 0
A = list(input())
checkList = list(map(int, input().split()))

for i in range(4):
    if checkList[i] == 0:
        checkSecret += 1

for i in range(P): # 초기 P 부분 문자열 처리 부분
    myadd(A[i])

if checkSecret == 4: # 4 자릿수와 관련된 크기가 모두 충족될 때 유효한 비밀번호
     Result += 1

for i in range(P, S):
    j = i - P
    myadd(A[i])
    myremove(A[j])
    if checkSecret == 4:
        Result += 1

print(Result)

📌 문제 010) 최솟값 찾기 1

시간 제한 2.4초, 플래티넘, 백준 11003번

N개의 수 A1, A2, ..., AN과 L이 주어진다.
Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

12 3
1 5 2 3 6 2 3 7 3 5 2 6

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

1 1 1 2 2 2 2 2 3 3 2 2

1단계 문제 분석

• 숫자 비교, 윈도우 범위 계산이 끝난 덱에서 맨 앞에 있는 노드의 숫자를 출력하면 정답이 된다.
• 최초 (1, 1)이 덱에 추가되면 비교 대상이 없고, 범위도 만족하므로 바로 1을 출력한다.
• (2, 5)는 (1, 1)과 숫자를 비교했을 때 더 크므로 탐색을 멈추고 덱에 추가한다. 인덱스 범위가 1~2여서 윈도우 범위를 만족하므로 다시 1을 출력한다.
• (3, 2)는 (2, 5)와 숫자를 비교했을 때 더 작으므로 (2, 5)를 덱에서 제거한다. (1, 1)은 여전히 (3, 2)보다 숫자가 작으므로 탐색을 멈추고 (3, 2)를 덱에 저장한다. 덱의 상태는 (1, 1), (3, 2)가 되고, 인덱스 범위 1~3 역시 윈도우 범위를 만족하므로 다시 1을 출력한다.
• (인덱스, 값) 형태
• 정렬 알고리즘을 쓰지 않고 슬라이딩 윈도우와 덱을 이용해 정렬 효과를 보는 것이 핵심이다.

2단계 슈도 코드

N(데이터 개수) L(최솟값을 구하는 범위)
mydeque(데이터를 담을 덱 자료구조)
now(주어진 숫자 데이터를 가지는 리스트)

for N만큼 반복: # now 리스트를 탐색 (now[i]를 현재 값으로 세팅)
	덱의 마지막 위치에서부터 현재 값보다 큰 값은 덱에서 제거
    덱의 마지막 위치에 현재 값 저장
    덱의 1번째 위치에서부터 L의 범위를 벗어난 값(now index-L <= index)을 덱에서 제거
    덱의 1번째 데이터 출력

3단계 코드 구현

from collections import deque
N, L = map(int, input().split())
mydeque = deque()
now = list(map(int, input().split()))

# 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임
for i in range(N):
    while mydeque and mydeque[-1][0] > now[i]:
        mydeque.pop()
    mydeque.append((now[i], i))
    if mydeque[0][1] <= i-L: # 범위에서 벗어난 값은 덱에서 제거
        mydeque.popleft()
    print(mydeque[0][0], end=' ')