[Python] Queue, Stack 개념 및 알고리즘 문제 풀기

1. Queue와 Stack

1.1 Stack

1.1.1 스택 구조

• 스택은 LIFO 또는 FILO 데이터 관리 방식을 따름
  • LIFO : 마지막에 넣은 데이터를 가장 먼저 추출
  • FILO : 처음에 넣은 데이터를 가장 마지막에 추출
• 대표적인 스택의 활용
  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
  • 주요 기능
    • push() : 데이터를 스택에 넣기
    • pop() : 데이터를 스택에서 꺼내기

1.1.2. 스택 구조와 프로세스 스택

• 스택 구조는 프로세스 실행 구조의 가장 기본
• 함수 호출 시 프로세스 실행 구조를 스택과 비교해서 이해 필요

def recursive(data):
    if data<0:
        print("ended")
    else:
        print(data)
        recursive(data-1)
        print("returned",data)

recursive(4)

* 프로세스가 동작될 때도 나중에 호출된 함수가 먼저 실행이 된다. 프로세스도 스택처럼 동작한다는 사실을 기억하기!!

1.1.3. 자료 구조 스택의 장단점

장점

• 구조가 단순해서 구현이 쉽다.
• 데이터 저장/읽기 속도가 빠르다.

단점

• 데이터 최대 갯수를 미리 정해야 한다.
• 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능
• 저장 공간의 낭비가 발생할 수 있음
• 미래 최대 갯수만큼 저장 공간을 확보해야 함

스택은 단순하고 빠른 성능을 위해 사용. 보통 배열 구조를 활용해서 구현함

1.2 Queue

1.2.1 큐 구조

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다
• FIFO(First-in, First-out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대이다

1.2.2 파이썬 queue 라이브러리를 활용해서 큐 자료 구조 사용하기

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifroQueue(), PriorityQueue() 제공
  • 프로그램을 작성할 때 프로그램에 따라 적합한 자료구조를 사용
  • Queue(): 가장 일반적인 자료 구조
  • LifroQueue() : 나중에 입력된 데이터가 먼저 출력(스택 구조)
  • PriorityQueue() : 데이터마다 우선순위를 넣어 그에 따라 출력

2. 알고리즘 문제 풀이

2.1 문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100% 일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

2.2 문제 풀이

def check(data1, data2):
    if data1 and data1[0] >= 100:
        del data1[0]
        del data2[0]
        return 1+ check(data1,data2)
    else:
        return 0

def solution(progresses, speeds):
    answer = []
    while progresses:
        progresses = [x+y for x,y in zip(progresses,speeds)]  
        complete_work=check(progresses,speeds)   
        if complete_work >0:
            answer.append(complete_work)
    return answer

1. zip 함수를 사용해서 progresses에 speeds 만큼을 계속 더해주는 것을 하루로 표현했다.
2. check라는 재귀함수를 만들어서 가장 앞에 기능의 작업 진도가 100 이상이 되면 speeds와 함께 리스트에서 제거해주었다.
3. 그리고 재귀함수가 반복될 때마다 1씩 더한 값을 return 해주고 아니라면 0을 return 했다.
4. 작업 진도가 완료되지 않아 complete_work의 값이 0인 경우는 배포에 추가하지 않았다. 

아무래도 나처럼 푼 사람은 없는 것 같다....ㅋㅋㅋㅋ 나름 프로세스 스택을 구현해보려고 재귀 함수를 사용했는데!!
코딩에 정답은 없으니 해결되고 더럽지만 않으면 되지 뭐....