[ 알고리즘 ] 스택/큐 이론

자료구조

 

선형구조

데이터를 저장하기 위한 기본적인 형태로 데이터가 일렬로 나열되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미한다.

선형구조에는 큐(Queue), 스택(Stack), 덱(Deque) 이 있다.

큐는 선입선출, 스택은 후입선출, 덱은 양쪽 끝에서 삽입과 삭제가 가능한 형태의 구조를 가진다.

• 큐: 선형구조의 형태이며 데이터를 일시적으로 쌓아두기 위한 자료구조 중 하나로 선입선출(FIFO, First-In-First-Out)의 특성을 의미한다.
  큐에서의 삽입과 추출 과정은 front와 rear포인터를 기준으로 작동한다. 데이터가 저장되는 곳은 rear부분이며 데이터가 추출하는 부분은 front에서만 수행한다.
• 스택: 데이터를 일시적으로 쌓아두기 위한 자료구조 중 하나로, 후입선출(LIFO, Last-In-First-Out)의 특성을 가지는 자료구조를 의미합니다.
  스택은 주로 깊이 우선탐색(DFS:Depth First Search), 백트래킹 종류의 코딩테스트에 사용 된다.
• 덱: '양쪽 끝에서 삽입과 삭제가 가능'한 자료구조를 의미한다. 덱(Deque)은 스택과 큐의 기능을 모두 가지고 있는 자료구조이며, 양쪽 끝에서 삽입과 삭제가 가능하다. 따라서 선입선출(FIFO)과 후입선출(LIFO) 개념이 모두 적용가능하다. 

 

문제1)

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 

예를 들면,
arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

 

코드1)

def solution(arr):
    answer = [arr[0]]
    for i in range(1,len(arr)):
        if arr[i]!=answer[-1]:
            answer.append(arr[i])

    return answer

배열 초기화 -> 배열 arr을 순회하면서 현재 원소와 answer 배열의 마지막 원소를 비교 -> 현재 원소와 answer 배열의 마지막 원소가 다르다면, 현재 원소를 answer에 추가

answer[-1] 는 배열의 마지막 요소를 의미한다.

 

• range의 사용 예시

# 0~5까지 숫자 생성
for i in range(6)
#결과: 0,1,2,3,4,5

# 2부터 8까지 숫자 생성
for i in range(2,9)
#결과: 2,3,4,5,6,7,8

# 2부터 15까지 숫자 생성. 간격 3
for i in range(2, 16, 3)
#결과: 2, 5, 8, 11, 14

# 1부터 10까지의 제곱수를 생성하는 리스트
list_a= [x**2 for x in range(1,11)]
print(list_a)
#결과: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

# 5부터 20까지의 숫자 중 짝수만 포함하는 리스트
list_b=list(range(5+(5%2),21,2))
print(list_b)
#결과: [6, 8, 10, 12, 14, 16, 18, 20]

 

 

문제2)

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

 

코드2)

    def solution(progresses, speeds):
    answer = []
    days = []  # 각 기능이 배포되기까지 걸리는 일수를 저장할 리스트
    
    # 각 기능이 배포되기까지 걸리는 일수를 계산하여 days 리스트에 저장
    for progress, speed in zip(progresses, speeds):
        day = 0
        while progress < 100:
            progress += speed
            day += 1
        days.append(day)
    
    # 배포되어야 하는 기능의 수를 세어서 결과 배열에 추가
    while days:
        count = 1
        current_day = days.pop(0)
        while days and current_day >= days[0]:
            count += 1
            days.pop(0)
        answer.append(count)
    
    return answer

• while days: 문-> days 리스트가 빈 리스트가 될 때까지 반복. 즉, 모든 기능이 배포될 때까지 반복.
• count 변수는 현재 배포되어야 할 기능의 수. 초기값은 1로 설정. 왜냐하면 첫 번째 기능은 무조건 배포되어야 하기 때문.
• current_day 변수에는 첫 번째로 배포될 기능이 배포되는데 걸리는 일수가 저장. 이 값은 days 리스트의 첫 번째 요소를 가져와서 저장합니다. 그리고 이 값을 pop(0)을 사용하여 days 리스트에서 제거.
  pop(0)은 리스트에서 첫 번째 요소를 제거하고 그 값을 반환하는 메서드
• 내부의 while 루프는 current_day 값보다 작거나 같은 값이 있는 동안 반복. 이 루프는 현재 배포될 기능과 동일한 날에 배포될 수 있는 모든 기능의 수를 세기 위해 사용.
• 내부의 while 루프에서는 먼저 count 값을 1로 초기화. days 리스트의 첫 번째 요소가 current_day보다 작거나 같은 경우에는 기능이 함께 배포될 수 있으므로 count 값을 증가시키고, days 리스트에서 해당 요소를 제거.
• 내부의 while 루프가 종료되면, count 변수에는 현재 배포될 기능의 수가 저장. 이 값을 answer 리스트에 추가.

 

문제3) 스택 사용

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 

예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

코드3)

def solution(s):
    stack = []  # 괄호를 저장할 스택

    # 문자열 s의 각 문자에 대해 반복
    for char in s:
        # 여는 괄호일 경우 스택에 추가
        if char == '(':
            stack.append(char)
        # 닫는 괄호일 경우 스택이 비어있거나 맨 위에 있는 괄호가 여는 괄호가 아니면 올바르지 않은 괄호
        elif char == ')':
            if not stack or stack[-1] != '(':
                return False
            stack.pop()  # 맨 위에 있는 여는 괄호 제거

    # 모든 문자를 확인한 후에도 스택이 비어있지 않으면 올바르지 않은 괄호
    return len(stack) == 0