[큐] 코딩테스트 문제 TIL (프로세스) - 프로그래머스

말하는 감자·2024년 9월 12일

data structure generator iterator programmers python queue 이터레이터 자료구조 제너레이터 코딩테스트 코딩테스트 준비 큐 파이썬 프로그래머스

코딩테스트 유형별 풀이

목록 보기

24/67

오늘 문제는 오랜만에 큐 자료구조 유형의 문제입니다.

1. 오늘의 학습 키워드

큐
이터레이터
제너레이터

2. 문제: 프로세스 (프로그래머스)

단계: Lv. 2
출처: https://school.programmers.co.kr/learn/courses/30/lessons/42587

문제 설명

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다. 2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다. 3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다. 3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

priorities의 길이는 1 이상 100 이하입니다.
- priorities의 원소는 1 이상 9 이하의 정수입니다.
- priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
- priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

입출력 예

priorities	location	return
[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.

3. 나의 풀이

문제 이해 및 접근

이 문제는 큐 자료구조를 활용하여 운영체제의 프로세스 관리를 모델링한 문제입니다. 주어진 우선순위에 따라 프로세스를 실행하며, 특정 프로세스가 몇 번째로 실행되는지를 계산하는 것이 목표입니다. 우선순위가 높은 프로세스가 먼저 실행되므로, 이를 처리하기 위해 큐(Queue)를 사용하여 프로세스들을 관리합니다.

접근 방법

큐 자료구조 사용: 먼저, 주어진 프로세스들의 우선순위를 인덱스와 함께 큐에 저장합니다.
우선순위 검사: 큐에서 프로세스를 꺼낼 때, 현재 프로세스보다 우선순위가 높은 프로세스가 큐에 남아 있으면, 현재 프로세스를 다시 큐의 끝으로 보냅니다.
실행 순서 저장: 만약 현재 프로세스가 우선순위가 가장 높다면, 이를 실행하여 종료 목록에 저장합니다.
목표 프로세스 찾기: 저장된 종료 목록에서 목표 프로세스가 몇 번째로 실행되었는지 확인합니다.

코드 설명

from collections import deque

def solution(priorities, location):
    # 큐에 프로세스의 인덱스와 우선순위를 함께 저장
    queue = deque((i, p) for i, p in enumerate(priorities))
    ans = []

    # 큐가 빌 때까지 반복
    while queue:
        process = queue.popleft()  # 큐에서 가장 앞의 프로세스를 꺼냄

        # 현재 프로세스보다 우선순위가 높은 프로세스가 있는지 확인
        if any(process[1] < q[1] for q in queue):
            queue.append(process)  # 우선순위가 높은 프로세스가 있으면 다시 큐 끝에 넣음
        else:
            ans.append(process)  # 그렇지 않으면 실행하여 종료 목록에 저장

    # 종료된 목록에서 목표 프로세스가 몇 번째로 실행되었는지 반환
    return next((idx + 1 for idx, i in enumerate(ans) if i[0] == location), None)

풀이 과정

큐 초기화: queue는 (인덱스, 우선순위) 형태의 튜플로 저장됩니다. deque를 사용하여 효율적으로 프로세스를 처리할 수 있습니다.
우선순위 처리: queue.popleft()를 통해 현재 프로세스를 꺼낸 후, any() 함수로 나머지 프로세스 중 우선순위가 더 높은 것이 있는지 확인합니다.
- 만약 현재 프로세스보다 우선순위가 높은 프로세스가 있으면, 다시 큐에 넣습니다.
- 그렇지 않으면, 현재 프로세스를 실행하여 종료 목록인 ans에 저장합니다.
실행 순서 확인: 종료된 프로세스 목록에서 목표 프로세스가 몇 번째로 실행되었는지 확인하여 반환합니다.

시간 복잡도

큐에 있는 모든 프로세스를 한 번씩 확인하므로, 시간 복잡도는 $O(n^2)$ 입니다. any() 함수에서 매번 큐를 확인하기 때문입니다.
입력 크기가 최대 100이므로, 시간 복잡도 $O(n^2)$ 도 충분히 허용되는 범위입니다.

4. 제너레이터와 이터레이터에 대한 설명

이 코드에서 사용된 제너레이터와 이터레이터의 개념은 특히 마지막 return 부분에서 중요한 역할을 합니다.

1. 이터레이터란?

이터레이터(iterator)는 값을 하나씩 차례대로 반환할 수 있는 객체입니다. 파이썬의 이터레이터는 for 루프, next() 함수 등을 통해 사용됩니다. 이터레이터는 메모리 효율적으로 큰 데이터 구조를 처리할 수 있으며, 한 번에 하나의 값만 메모리에 적재합니다.

2. 제너레이터란?

제너레이터(generator)는 이터레이터의 일종으로, 값을 한 번에 하나씩 생성합니다. 제너레이터는 yield 키워드나 제너레이터 표현식으로 만들 수 있습니다. 제너레이터는 필요한 순간에 값을 생성하므로, 메모리 사용이 적고 성능 효율이 높습니다.

3. 코드에서 제너레이터 사용 설명


return next((idx + 1 for idx, i in enumerate(ans) if i[0] == location), None)

이 부분은 제너레이터 표현식을 사용한 것으로, 특정 조건을 만족하는 값을 찾을 때 매우 유용합니다.

enumerate(ans)는 ans 리스트의 인덱스와 값을 함께 반환하는 이터레이터입니다.
(idx + 1 for idx, i in enumerate(ans) if i[0] == location)은 제너레이터 표현식으로, ans 리스트에서 인덱스 location에 해당하는 프로세스를 찾으면 그 순번(idx + 1)을 반환합니다.
next() 함수는 제너레이터에서 값을 하나씩 꺼내오며, 첫 번째로 조건을 만족하는 값을 반환합니다. 조건을 만족하는 값이 없으면, 기본값인 None을 반환합니다.

제너레이터와 이터레이터를 사용한 이유

이 문제에서 제너레이터 표현식을 사용한 이유는:

메모리 효율성: ans 리스트가 매우 크더라도, 제너레이터는 필요할 때마다 값을 하나씩 생성하여 메모리 사용을 최소화합니다.
즉시 반환: 조건을 만족하는 값을 찾으면 즉시 반환하고, 더 이상 계산을 진행하지 않으므로 불필요한 연산을 줄일 수 있습니다.

5. 이터레이터, 제너레이터 예시

이터레이터 (Iterator)

이터레이터(iterator)는 파이썬에서 순차적인 데이터를 하나씩 차례대로 접근할 수 있는 객체입니다. 이터레이터는 값들을 반복해서 접근할 수 있게 해주며, 한 번에 하나의 값만을 반환합니다. 이터레이터는 주로 for 루프나 while 루프와 함께 사용되며, next() 함수를 통해 다음 값을 반환합니다.

이터레이터의 두 가지 중요한 메서드:

__iter__(): 이터레이터 객체 자체를 반환합니다.
__next__(): 이터레이터에서 다음 값을 반환합니다. 더 이상 반환할 값이 없을 때 StopIteration 예외를 발생시킵니다.

이터레이터 예시

# 리스트를 이터레이터로 변환
my_list = [1, 2, 3]
my_iter = iter(my_list)  # 이터레이터 생성

# 이터레이터에서 값을 하나씩 꺼냄
print(next(my_iter))  # 1
print(next(my_iter))  # 2
print(next(my_iter))  # 3

# 더 이상 꺼낼 값이 없으면 StopIteration 예외 발생
print(next(my_iter))  # StopIteration 예외

제너레이터 (Generator)

제너레이터(generator)는 이터레이터를 생성하는 함수로, 파이썬의 특별한 함수 형태입니다. 제너레이터는 일반 함수처럼 정의되지만, 값을 반환할 때 return 대신 yield를 사용합니다. 제너레이터는 값을 미리 메모리에 저장하지 않고 필요할 때마다 하나씩 값을 생성하는 방식이기 때문에, 메모리 효율성이 뛰어납니다.

제너레이터의 특징:

yield 키워드: 값을 반환하고, 함수의 상태를 유지한 채로 다음 호출을 기다립니다.
메모리 절약: 한 번에 하나의 값만을 생성하기 때문에, 대량의 데이터를 처리할 때 유용합니다.
next(): 제너레이터는 이터레이터와 동일하게 next() 함수로 다음 값을 반환합니다.

제너레이터 예시

# 제너레이터 함수 정의
def my_generator():
    yield 1
    yield 2
    yield 3

# 제너레이터 객체 생성
gen = my_generator()

# 제너레이터에서 값을 하나씩 꺼냄
print(next(gen))  # 1
print(next(gen))  # 2
print(next(gen))  # 3

# 더 이상 꺼낼 값이 없으면 StopIteration 예외 발생
print(next(gen))  # StopIteration 예외

제너레이터 표현식

제너레이터는 리스트 컴프리헨션과 비슷한 방식으로 제너레이터 표현식을 사용할 수 있습니다. 하지만 제너레이터는 한 번에 하나씩만 값을 생성합니다.

gen_exp = (x * x for x in range(3))  # 제너레이터 표현식

print(next(gen_exp))  # 0
print(next(gen_exp))  # 1
print(next(gen_exp))  # 4

이터레이터와 제너레이터의 차이점

구현 방식:
- 이터레이터는 __iter__()와 __next__() 메서드를 구현한 객체입니다.
- 제너레이터는 yield 키워드를 사용하는 함수로, 자동으로 __iter__()와 __next__()를 구현합니다.
메모리 효율성:
- 이터레이터는 값들을 미리 준비된 데이터 구조에서 하나씩 반환합니다.
- 제너레이터는 필요할 때마다 값을 동적으로 생성하므로 더 메모리 효율적입니다.
사용 편의성:
- 이터레이터는 일반적으로 클래스나 복잡한 구조에서 사용되며, __iter__()와 __next__() 메서드를 수동으로 정의해야 합니다.
- 제너레이터는 함수 형태로 쉽게 작성할 수 있으며, yield를 사용해 값을 생성합니다.

요약

이터레이터는 데이터를 하나씩 순차적으로 반환하는 객체이며, __iter__()와 __next__() 메서드를 사용합니다.
제너레이터는 이터레이터를 생성하는 특별한 함수로, yield 키워드를 통해 값을 하나씩 반환하며, 메모리 효율이 뛰어납니다.

마무리

이번 문제는 큐 자료구조를 활용하여 프로세스의 우선순위 처리를 구현하는 문제였습니다. 큐를 사용하여 프로세스를 효율적으로 관리하고, 우선순위에 따라 프로세스를 실행하는 방식은 운영체제에서 실제로 사용되는 방식과 유사합니다. 또한, 이터레이터와 제너레이터를 활용해 결과를 효율적으로 찾아내는 방법을 학습할 수 있었습니다.

더 나은 개발자가 될거야!!

말하는 감자

할 수 있다

이전 포스트

[그리디] 코딩테스트 문제 TIL (거스름돈) - 백준 5585번

다음 포스트