2021.03.09 TIL 알고리즘 공부

2021.03.09에 배운 지식

-스택

-큐 

 

스택은 한쪽 끝만 열려있는 자료 구조인데, 빨래바구니처럼 내가 차곡차곡 저장해놓고 마지막에 들어갔던 녀석부터 하나씩 빼서 쓸 수 있는 저장소다.

스택을 이용할 땐 주료 stack.append()를 이용해 스택의 맨 마지막에 push를 해주거나 stack.pop()을 이용해 마지막 녀석을 빼주는 식으로 이용한다.

내가 이해한 스택을 사용해보기 위해 백준 알고리즘 예제중 4949번과 1874번을 풀어봤다.

 

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

4949번: 균형잡힌 세상

# 알고리즘 공부 #01주
# 백준 4949

import sys

while True:
    word = sys.stdin.readline()  #문장을 입력 받기
    if word[0] == '.':		#문장이 .만 있다면 작동 종료
        break        
    stack = []	#스택 초기화
    word_result = 1;  #작동이 정상적이었는지 확인을 위한 변수
    for now in word :   #입력받은 문장을 처음부터 한 글자씩 확인하자
        if now == '(' or now == '[' :  # 확인중 (나 [가 들어왔다면
            stack.append(now)           #스택에 쌓아주자 	
        elif now == ')':				# )가 들어왔다면
            if not stack or stack[-1]=='[' :	#가장 최근 스택이 비었거나 [가 있다면
                word_result = 0;                #종료하고 정상적이지 않다는 표시로 변수를 0으로
                break							
            elif stack[-1]=='(':           		#최근 스택이 (라면
                stack.pop();					#최근 스택을 삭제
                word_result = 1;        		#정상적으로 작동중이라는 표시로 변수를 1로
                
        elif now ==']':							#똑같이 ] 가 들어왔다면
            if not stack or stack[-1]=='(':		#가장 최근 스택이 비었거나 (가 있다면
                word_result = 0;                #종료하고 정상적이지 않다는 표시 
                break            		
            elif stack[-1]=='[':        		#최근 스택이 [ 라면    
                stack.pop();					#최근 스택 삭제
                word_result = 1;             	#정상 작동 표시
        if word == '.':							#.이 나오면 종료하고 다시 입력받기
            break   


    if not stack and word_result ==True :     	#정상적으로 구동했거나 스택에 남아있는게 없다면
        print('yes');							#yes
    else :										#없다면 No 출력
        print('no');

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

1874번: 스택 수열

 

# 알고리즘 공부 #01
# 백준 1874

import sys

max_num = int(sys.stdin.readline())  #마지막 수를 입력받기
count = 1 ;				#현재 진행 상황을 카운트하기 위한 변수
stack = [];
result = [];
no_result = True;			#정상 작동을 판별하기 위한 변수

for i in range(max_num) :		#1부터 입력받은 마지막 수까지 차례차례 for문 돌리기
    target_num = int(sys.stdin.readline());	#내가 빼내야 하는 수 입력받기
    while count <= target_num :			#타겟이 현재 카운트보다 작다면(카운트는 1부터 시작)
        stack.append(count);			#해당 타겟까지 스택에 추가해주고 
        result.append('+');				#스택에 쌓았으니 +를 다른 결과 저장소에 넣어준다
        count += 1;
    if stack[-1] == target_num:			#이제 스택의 마지막 수가 타겟과 같아졌으니
        stack.pop();					# 해당 스택을 삭제하고
        result.append('-');				# 결과 저장소에 '-' 입력
    else :
        no_result = False;     			#만약 타겟이 현재 카운트보다 작다면
        								#마지막수가 타겟보다 작다는 뜻이니 작동 실패를 표시
if no_result == False:					#작동 실패했다면 No를
    print('No');
else :
    for i in result :					#성공했다면 결과 저장소를 출력
        print(i);

큐는 원통처럼 구멍이 두 개있는 저장소다.

뒤에다가 차례차례 넣으면 맨 앞에서 넣은 순서대로 뽑아낼 수 있는 원통.

(마치 놀이기구 대기줄이나 초등학교때 쓰던 끼워쓰는 연필처럼)

큐를 사용할땐 dequeue()를 이용해 맨 앞의 데이터를 뽑아주거나 peek()을 이용해 맨 앞의 데이터를 볼 수 있고

isEmpty()로 큐가 비었는지 안비었는지 확인하거나 enqueue(data)를 이용해 맨 뒤에 데이터를 추가할 수 있다.

 

que.poplest()를 이용해도 맨 앞의 데이터를 pop 시킬 수 있는데, 이땐 맨 위에 collections의 deque를 import 해주고 큐를 deque()로 초기화시켜 사용할 수 있다.

deque()는 그냥 큐보다 시간 복잡도면에서 유리하다고 한다.

 

이걸 이해하고 큐 관련된 문제 백준 알고리즘 1021번을 풀어봤다.

큐의 원리는 이해했으나 큐를 이용한 다른 내장된 명령어들은 이때 당시 알지 못해서 내가 이전까지 사용해왔던 명령어들로 문제를 구현했다 ! 

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

1021번: 회전하는 큐

# 알고리즘 공부 #01
# 백준 1021

import sys
import math

num_size, want_size = map(int, sys.stdin.readline().split());
#처음에는 큐의 크기와 뽑아내려고 하는 수의 개수를 받아줍니다.
want_list = list(map(int, sys.stdin.readline().split()));
#뽑아내려고 하는 수의 위치를 입력받아 리스트로 만들어주세요
num_list = []
cnt = 0;
#우리가 사용하기위해 큐의 크기만큼 만들어줄 리스트와 이동 횟수를 저장할 변수를 초기화해주세요
#이제 1부터 입력받은 큐의 크기만큼 리스트로 만들어줍니다
for i in range(1,num_size+1) :
    num_list.append(i);
#두번째로 입력받았던 뽑아내려는 수의 위치를 앞에서 부터 하나하나 돌아가며 for문으로 찾아냅니다
for i in want_list :
    if num_list.index(i)+1 <= math.ceil(len(num_list)/2) : 
        #index를 이용해서 뽑아내려고 하는 수의 위치를 큐 속에서 찾아내고 0부터 시작하기에 1을 더해줬습니다.
        #그리고 현재 큐의 길이를 2로 나눠서 이보다 작거나 같으면 앞으로 가져도록
        #크면 뒤로 빼도록 나눠줍니다. 
        while True :
            #앞으로 이동시키는게 빠를때, 맨 앞의 수가 우리가 찾는 수라면
            #그 수를 리스트에서 지우고 다음 수를 찾기위해 종료
            if num_list[0] == i :  
                del num_list[0];                 
                break
            else :
                #맨 앞의 수가 우리가 찾는 수가 아니라면 
                #맨 앞의 수를 맨 뒤에 추가해주고
                #맨 앞의 수를 삭제합니다, 이동했으니 카운트에 +1하고 계속 진행
                num_list.append(num_list[0]);
                del num_list[0];                
                cnt +=1;
    else :
        while True:
            #뒤로 이동시키는게 빠를때, 맨 뒤의 수가 우리가 찾는 수라면
            #그 수를 리스트에서 지우고 다음 수를 찾기위해 종료. 
            #이때 지민이가 가지고 있는 큐는 앞으로 빼는 기능밖에 없기때문에
            #맨 뒤를 앞으로 보내주고 삭제해야합니다.
            #이 과정을 생략했으니 카운트에 +1을 해줍니다.
            if num_list[-1] == i :
                del num_list[-1];
                cnt += 1;               
                break
            else :
                #맨 뒤의 수가 우리가 찾는 수가 아니라면
                #그 수를 insert를 통해서 맨 첫번째에 끼워넣어주고
                #마지막 수를 지워줍니다.
                #앞으로 보내줬으니 카운트 +1
                num_list.insert(0,num_list[-1]);
                del num_list[-1];              
                cnt += 1;
#for문이 돌면서 우리가 원하던 수를 다 찾았으니 cnt에 적힌 숫자를 출력
print(cnt);