알고리즘 스터디 3일차

목차

1. 슬라이딩 윈도우 실전문제

2. 스택과 큐

3. 스택과 큐 실전문제

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

1. 슬라이딩 윈도우 실전문제

https://www.acmicpc.net/problem/11003

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

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)