목차
1. 슬라이딩 윈도우 실전문제
2. 스택과 큐
3. 스택과 큐 실전문제
출처
Do it! 알고리즘 코딩테스트 with Python
1. 슬라이딩 윈도우 실전문제
https://www.acmicpc.net/problem/11003
처음풀이
import sys
input = sys.stdin.readline
N,L = map(int,input().split())
n_list = list(map(int,input().split()))
answer = []
for i in range(N):
d_list = []
j = i
while((j+1-L)<=(i)):
if(j+1-L>=0):
d_list.append(n_list[j+1-L])
j +=1
else:
j +=1
answer.append(min(d_list))
print(*answer)
또 시간초과... 크게 틀린 부분은 없어 보이는데 백준에 있는 문제는 시간초과가 너무 많이 난다.. 내가 아직 알고리즘을 잘 몰라서가 이유이기 때문에 알고리즘 스터디를 끝내고 나면 많이 성장해 있길 바란다.
해설을 보고나니 납득이 갔다. N과 L의 최댓값이 오백만이나 되기 때문에 내 코드는 오백만 번이나 리스트를 만드는 과정을 반복했기 때문이다. 따라서 2가지 아이디어로 문제에 접근해야 한다.
첫 번째, 최솟값 가능성 없는 데이터 삭제
두 번째, window 크기 밖 데이터 삭제
무슨 뜻이냐면 구하는 범위(윈도우)안에서 새로 들어온 데이터보다 기존에 있던 데이터가 크다면 그 데이터는 최솟값이 될 가능성이 없으니 삭제하고 순서와 값을 같이 저장해 순서에 L값을 빼 범위 밖 데이터 또한 삭제한다는 뜻이다.
코드로 보는것이 이해가 더 빠르기 때문에 바로 해설코드를 첨부하겠다.
해설코드
import sys
from collections import deque
input = sys.stdin.readline
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=' ')
2. 스택과 큐
2.1 스택
삽입과 삭제 연산이 후입선출(LIFO: Last-inFirst-out)로 이뤄지는 자료구조
top : 삽입과 삭제가 일어나는 위치
s.append(data) : s 리스트의 top 위치에 새로운 데이터를 삽입
s.pop() : s 리스트의 top 위치에 있는 데이터를 삭제하고 확인
s[-1] : s 리스트의 top 위치에 있는 데이터를 단순 확인
2.2 큐
삽입과 삭제 연산이 선입선출(FIFO: First-inFirst-out)로 이뤄지는 자료구조
rear : 큐에서 가장 끝 데이터를 가리키는 영역
front : 큐에서 가장 앞의 데이터를 가리키는 영역
s.append(data) : s 리스트의 rear 부분에 새로운 데이터를 삽입
s.popleft() : s 리스트의 front 부분에 있는 데이터를 삭제하고 확인
s[0] : s 리스트의 큐의 맨 앞(front)에 있는 데이터를 단순 확인
사실 스택과 큐는 익숙하지만 그만큼 중요하고 코딩테스트에서 단골손님으로 등장하는 만큼 많은 문제를 풀고 익숙해져야 할 필요가 있다. 바로 실전문제를 통해 연습해 보자.
3. 스택과 큐 실전문제
https://www.acmicpc.net/problem/17298
코드풀이
import sys
input = sys.stdin.readline
A = int(input())
a_list = list(map(int,input().split()))
answer = [-1]*A
stack = []
for i in range(A):
while stack and a_list[stack[-1]]<a_list[i]:
answer[stack.pop()] = a_list[i]
stack.append(i)
print(*answer)
'파이썬 코딩테스트' 카테고리의 다른 글
알고리즘 스터디 6일차 (0) | 2023.08.20 |
---|---|
알고리즘 스터디 5일차 (0) | 2023.08.20 |
알고리즘 스터디 4일차 (0) | 2023.08.19 |
알고리즘 스터디 2일차 (0) | 2023.08.15 |
알고리즘 스터디 1일차 (0) | 2023.08.14 |