"Do it! 알고리즘 코딩테스트 with Python" 책에서
03-3 투 포인터~03-4 슬라이딩 윈도우 부분을 풀어볼 것입니다.
03-3 투 포인터
투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화합니다.
문제 006 연속된 자연수의 합 구하기
https://www.acmicpc.net/problem/2018
01단계 문제 분석하기
문제에 주어진 시간 제한은 2초인데 N의 최댓값은 10,000,000으로 매우 크게 잡혀 있으므로 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 합니다. 이때 자주 사용하는 방법이 투 포인터입니다! 연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현할 텐데, 시작 인덱스, 종료 인덱스를 투 포인터로 지정한 후 문제에 접근하도록 하겠습니다.
02단계 손으로 풀어보기
1. 입력받은 값을 N에 저장한 후 코드에서 사용할 변수를 모두 초기화합니다. 즉, count=1, start_index=1, end_index=1, sum=1로 초기화합니다. 결과 변수 count를 1로 초기화하는 이유는 N이 15일 때 숫자 15만 뽑는 경우의 수를 미리 넣고 초기화하였기 때문입니다.
2. 다음에서 보이는 투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우의 수를 구합니다. start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같으며, end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장하는 의미입니다. 같을 때는 경우의 수를 1 증가시키고, end_index를 오른쪽으로 이동시킵니다.
투 포인터 이동 원칙
- sum > N : sum = sum - start_index; start_index++;
- sum < N : end_index++; sum = sum + end_index;
- sum == N : end_index++; sum = sum + end_index; count++;
3. 2단계를 end_index가 N이 될 떄까지 반복하되, 포인터가 이동할 때마다 현재의 총합과 N을 비교해 값이 같으면 count를 1만큼 증가시키면 됩니다.
03단계 슈도코드 작성하기
n변수 저장
사용 변수 초기화(count=1, start_index=1, end_index=1, sum=1)
while end_index != n:
if sum == n: 경우의 수 증가, end_index 증가, sum값 변경
elif sum > n: sum값 변경, start_index 증가
else: end_index 증가, sum값 변경
경우의 수 출력04단계 코드 구현하기
# 연속된 자연수의 합 구하기
n=int(input()) # n 변수 저장
count=1
start_index=1
end_index=1
sum=1
while end_index !=n:
if sum==n: # 정답 케이스
count+=1
end_index+=1
sum+=end_index
elif sum>n:
sum-=start_index
start_index+=1
else:
end_index+=1
sum+=end_index
print(count)문제 007 주몽의 명령
https://www.acmicpc.net/problem/1940
01단계 문제 분석하기
우선 시간 복잡도를 고려해 봅시다. 두 재료의 번호의 합, 즉, 크기를 비교하므로 값을 정렬하면 문제를 좀 더 쉽게 풀 수 있습니다. N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 문제가 없습니다. 일반적으로 정렬 알고리즘의 시간 복잡도는 O(nlogn)입니다. 즉, 정렬을 사용해도 괜찮습니다. 입력받은 N개의 재룟값을 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근해 보겠습니다.
02단계 손으로 풀어보기
1. 재료 데이터를 리스트 A에 저장한 후 오름차순 정렬합니다.(리스트 A선언->오름차순 정렬)
2. 투 포인터 i,j를 양쪽 끝에 위치시킨 후 문제의 조건에 적합한 포인터 이동 원칙을 활용해 탐색을 수행합니다. 다음은 투 포인터 이동 원칙입니다.
투 포인터 이동 원칙
- A[i] + A[j] > M: j--; # 번호의 합이 M보다 크므로 큰 번호 index를 내립니다.
- A[i] + A[j] < M: i++; # 번호의 합이 M보다 작으므로 작은 번호 index를 올립니다.
- A[i] + A[j] == M: i++; j--;count++; # 양쪽 포인터를 모두 이동시키고 count를 증가시킵니다.
3. 2단계를 i와 j가 만날 때까지 반복합니다. 반복이 끝나면 count를 출력합니다.
03단계 슈도코드 작성하기
N(재료의 개수), M(갑옷이 되는 번호)
A(재료 데이터 저장 리스트)
A 리스트 정렬하기
i(시작 인덱스 = 0)
j(종료 인덱스 = N - 1)
count(정답값 = 0)
while i<j:
if 재료 합 < M: 작은 번호 재료를 한 칸 위로 변경
elif 재료 합 > M: 큰 번호 재료를 한 칸 아래로 변경
else 경우의 수 증가, 양쪽 index 각각 변경
count 출력04단계 코드 구현하기
# 주몽의 명령
import sys
input=sys.stdin.readline
N=int(input()) # N(리스트 숫자의 개수)
M=int(input()) # M(두 숫자의 합이 되어야 하는 수)
A=list(map(int,input().split())) # A(리스트 숫자들)
A.sort() # A 리스트 정렬하기
i=0 # i(시작 인덱스=0)
j=N-1 # j(종료 인덱스=N-1)
count=0 # count(정답값=0)
while i<j:
if A[i]+A[j]<M:
i+=1# 작은 번호 재료를 한 칸 위로 변경
elif A[i]+A[j]>M:
j-=1# 크은 번호 재료를 한 칸 아래로 변경
else:
count+=1 # 경우의 수 증가, 양쪽 index 각각 변경
i+=1
j-=1
print(count)문제 008 '좋은 수' 구하기
https://www.acmicpc.net/problem/1253
01단계 문제 분석하기
시간 복잡도부터 생각해 봅시다. N의 개수가 최대 2,000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 합니다. 만약 좋은 수 하나를 찾는데 시간 복잡도가 N^2인 알고리즘을 사용함녀 최종 시간 복잡도는 N^3이 되어 제한 시간 안에 문제를 풀 수 없기 때문입니다. 따라서 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 합니다. 정렬, 투 포인터 알고리즘을 사용하면 됩니다. 단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안 됩니다. 이점을 예외로 처리해야 한다는 것을 염두에 두고 문제에 접근해 보겠습니다.
02단계 손으로 풀어보기
1. 수를 입력받아 리스트에 저장한 후 정렬합니다.
2. 투 포인터 i,j를 배열 A 양쪽 끝에 위치시키고 조건에 적합한 투 포인터 이동 원칙을 활용해 탐색을 수행합니다. 판별의 대상이 되는 수는 K라고 가정합니다.
투 포인터 이동 원칙
- A[i] + A[j] > k : j--; A[i] + A[j] < k: i++;
- A[i] + A[j] == k: count++; 프로세스 종료
3. 2단계를 리스트의 모든 수에 대하여 반복합니다. 즉 K가 N이 될 때까지 반복하며 좋은 수가 몇 개인지 셉니다.
03단계 슈도코드 작성하기
N(데이터 개수)
Result(좋은 수 개수 저장 변수)
A(수 데이터 저장 리스트)
A 리스트 정렬
for N만큼 반복:
변수 초기화(찾고자 하는 값 find=A[k], 포인터 i, 포인터j)
while i<j:
if A[i]+A[j] == find:
두 포인터 i,j가 k가 아닐 때 좋은 수 개수 1 증가 및 while 문 종료
두 포인터 i,j가 k가 맞을 때 포인터 변경 및 계속 수행
elif A[i] + A[j] < find: 포인터 i증가
else: 포인터 j 감소
좋은 수 개수 출력04단계 코드 구현하기
# '좋은 수' 구하기
import sys
input=sys.stdin.readline
n=int(input()) # 수의 개수
A=list(map(int,input().split()))
result=0
A.sort()
for k in range(n):
find=A[k]
i=0
j=n-1
while i<j:
if A[i]+A[j]==find:
if i!=k and j!=k:
result+=1
break
elif i==k:
i+=1
elif j==k:
j-=1
elif A[i]+A[j]<find:
i+=1
else:
j-=1
print(result)03-4 슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결합니다. 투 포인터 알고리즘과 매우 비슷하고 원리도 간단합니다.
문제 009 DNA 비밀번호
https://www.acmicpc.net/problem/12891
01단계 문제 분석하기
P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 합니다. 이때 부분 문자열의 길이가 P이므로 슬라이딩 윈도우의 개념을 이용하면 문제를 쉽게 해결할 수 있습니다. 슬라이딩 윈도우는 크기를 유지한 상태로 이동하면서 조건에 맞는지 탐색합니다. 길이가 P인 윈도우를 지정하여 리스트 S의 시작점에 놓습니다. 그런 다음 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색합니다. 마치 창틀에 창문을 놓고 이동하는 모양 같습니다. 그래서 슬라이딩 윈도우라는 이름이 지어진 것입니다. 리스트 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.
02단계 손으로 풀어보기
1. 리스트 S와 비밀번호 체크 리스트를 저장합니다.
리스트 S: C C T G G A T T G
비밀번호 체크 리스트: A C G T
2 0 1 1
2. 윈도우에 포함된 문자로 현재 상태 리스트를 만듭니다. 그런 다음 현재 상태 리스트와 비밀번호 체크 리스트를 비교하여 유효 비밀번호인지 판단합니다.
3. 윈도우를 한 칸씩 이동하며 현재 상태 리스트를 업데이트합니다. 현재 상태 리스트를 업데이트한 이휴에는 비밀번호 체크 리스트와 비교하여 비밀번호 유효성을 판단합니다. 현재 상태 리스트를 업데이트할 때는 빠지는 문자열, 신규 문자열만 보고 업데이트하는 방식으로 진행합니다.
03단계 슈도코드 작성하기
# 전역변수 선언
checkList(비밀번호 체크 리스트)
myList(현재 상태 리스트)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)
# 함수 선언
myadd(문자 더하기 함수):
myList에 새로운 값을 더하고 조건에 따라 checkSecret값 업데이트
myremove(문자 빼기 함수):
myList에 새로운 값을 제거하고 조건에 따라 checkSecret값 업데이트
# 메인 코드
S(문자열 크기) P(부분 문자열의 크기)
A(문자열 데이터)
checkList 데이터 받기
checkList를 탐색하여 값이 0인 데이터의 개수만큼 checkSecret 값 증가
# 값이 0이라는 것은 비밀번호 개수가 이미 만족되었다는 뜻
P 범위(0 ~ P - 1)만큼 myList 및 checkSecret에 적용하고, 유효한 비밀번호인지 판단
for i를 P에서 S까지 반복:
j선언(i - P)
# 이 부분은 myadd, myremove 함수로 별도 구현
한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열을 처리
유효한 비밀번호인지(checkSecret == 4) 판단해 결괏값을 업데이트
결괏값 출력04단계 코드 구현하기
# DNA 비밀번호(슬라이딩 윈도우)
# 전역 변수 선언
checkList=[0]*4 # 비밀번호 체크 리스트
myList=[0]*4 # 현재 상태 리스트
checkSecret= 0 # 몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수
# 함수 선언
def myadd(c): # 새로 들어온 문자를 처리하는 함수
global checkSecret, checkList, myList
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 checkSecret, checkList, myList
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()) # S(문자열의 길이), P(부분 문자열의 크기)
Result=0
A=list(input()) # A(문자열 데이터)
checkList=list(map(int,input().split())) # checkList(비밀번호 체크 리스트)
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)'스터디 > 2024동계모각코' 카테고리의 다른 글
| [2024 동계모각코] 5주차 결과 (0) | 2025.02.16 |
|---|---|
| [2024 동계모각코] 5주차 목표 (0) | 2025.02.16 |
| [2024 동계모각코] 4주차 목표 (0) | 2025.02.07 |
| [2024 동계모각코] 3주차 결과 (1) | 2025.01.26 |
| [2024 동계모각코] 3주차 목표 (0) | 2025.01.26 |