JinWoo Kim

백문이 불여일견, 백견이 불여일행.

3 minute read

코딩테스트 연습

1. 가희와 프로세스 1

  • 가희는 스케쥴러를 구현하라는 과제를 받았습니다. 스케쥴러가 실행시킬 프로세스를 선택하는 기준은 아래와 같습니다.

    • 우선 순위 값이 제일 큰 프로세스
    • 우선 순위 값이 제일 큰 프로세스가 여러 개라면, id가 가장 작은 프로세스

  • 가희가 만든 스케쥴러는 다음 알고리즘으로 실행됩니다.

    1. 실행시킬 프로세스를 기준에 따라 선택합니다. 선택된 프로세스의 id를 ids라 합니다. ids를 실행시킵니다.
    2. 1초가 지난 후, 프로세스 id가 ids인 프로세스를 제외한 나머지 프로세스들의 우선 순위가 1 상승합니다.
    3. 프로세스 id가 ids 인 프로세스의 실행을 마치는 데 필요한 시간은 1 감소합니다.

  • 실행 시간이 남은 프로세스가 있다면 1로 돌아가고, 그렇지 않으면 종료합니다.

  • 동시에 실행되는 프로세스는 1개이고, 1초일 때 가희가 만든 스케쥴러는 최초로 선택한 프로세스를 실행시키는 작업을 합니다.

  • 가희는 1초일 때 부터 T초일 때 까지, 스케쥴러가 선택한 프로세스의 id를 알고 싶습니다. 가희를 도와주세요.

입력

  • 첫 번째 줄에 T, n이 주어집니다.

  • 두 번째 줄 부터 n+1번째 줄까지 다음과 같은 형식으로 주어집니다.

    Ai Bi Ci

  • 이것은 i번째 process의 id가 Ai이고, 프로세스 id가 실행을 마치는 데 필요한 시간이 Bi초이고, 초기 우선 순위가 Ci임을 의미합니다.

출력

  • T개의 정수를 T개의 줄에 출력합니다.

  • i번째 줄에는 가희가 만든 스케쥴러가 i초가 되었을 때 선택한 프로세스의 id를 출력해 주세요.

풀이

# your code goes here

import sys

# 첫 번째 줄에 T, n이 주어집니다.

T, n = list(map(int,sys.stdin.readline().split()))

# 두 번째 줄 부터 n+1번째 줄까지 다음과 같은 형식으로 주어집니다
# Ai Bi Ci
# 이것은 i번째 process의 id가 Ai이고, 프로세스 id가 실행을 마치는 데 필요한 시간이 Bi초이고, 
# 초기 우선 순위가 Ci임을 의미합니다.

A = [] # 프로세스 id
B = [] # 프로세스 실행 시간
C = [] # 프로세스 초기 우선순위

for i in range(0,n):
	Ai, Bi, Ci = list(map(int,sys.stdin.readline().split()))
	
	A.append(Ai)
	B.append(Bi)
	C.append(Ci)
	

cnt = 0 # 스케줄러 작동 시간
while(True):
	
	# --프로세스 선택--
	idx = 0 # 다음 작업을 진행할 프로세스의 인덱스
	max_C = -1 # 최대 우선순위값
	min_A = 10000001 # 최소 id값
	for i in range(0,len(A)):
		# 우선 순위 값이 제일 큰 프로세스
		if C[i] > max_C:
			max_C = C[i]
			idx = i
		# 우선 순위 값이 제일 큰 프로세스가 여러 개라면, id가 가장 작은 프로세스
		elif C[i] == max_C:
			if min_A > A[i]:
				min_A = A[i]
				max_C = C[i]
				idx = i
	
	# -- 프로세스 실행 --
	
	
	# 실행시킬 프로세스를 기준에 따라 선택합니다. 선택된 프로세스의 id를 ids라 합니다. ids를 실행시킵니다.
	
	
	# 1초가 지난 후, 프로세스 id가 ids인 프로세스를 제외한 나머지 프로세스들의 우선 순위가 1 상승합니다.
	T -= 1
	C = [x + 1 for x in C]
	C[idx] -= 1
	# 프로세스 id가 ids 인 프로세스의 실행을 마치는 데 필요한 시간은 1 감소합니다.
	B[idx] -= 1
	# 매초 실행하는 프로세스의 id를 출력한다
	if cnt > 0:
		print(A[idx])
	# 프로세스의 남은 실행시간이 0이라면 완료되었으므로, 제거합니다.
	if B[idx] == 0:
		del A[idx]
		del B[idx]
		del C[idx]
	# 실행 시간이 남은 프로세스가 있다면 1로 돌아가고, 그렇지 않으면 종료합니다.
	if T < 0:
		break
	
	cnt += 1

채점 결과

  • 오답(시간 초과)
  • 배열을 사용한 방법으로는 시간제한을 넘길수 없었으므로, 사용된 개념에 대해 공부하기로 했다.

해당 문제에 사용되는 개념

  • 우선순위 큐

개념 정리

우선순위 큐

  • 일반적인 FIFO(선입선출) 형식의 자료구조인 큐와 달리, 들어간 순서에 상관없이 무조건 우선순위가 높은 데이터가 먼저 나오는 자료구조.

  • 우선순위 큐는 힙(Heap)을 통해 구현한다.

우선순위 큐를 힙으로 구현하는 이유

  • 배열 및 연결 리스트로 구현할때
    • 우선순위가 큰 값을 순서대로 삽입할때, 데이터 반환은 맨 앞의 인덱스를 활용.
    • 우선순위가 중간인 값을 삽입할때, 뒤의 데이터를 전부 한칸씩 밀어야 한다.
    • 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)
  • 힙으로 구현할때
    • 힙은 삭제/삽입이 전부 부모와 자식 노드의 비교를 통해 이루어짐.
    • 즉, 이진 트리의 높이가 하나 높아질때마다 저장 가능한 자료의 개수는 2배, 비교 연산 횟수는 1회 증가.
    • 따라서 삭제와 삽입 모두 최악의 경우 시간복잡도는 O(log2n)이다.

힙에서의 데이터 저장, 삭제

저장

  • 최소 힙을 기준으로 한다.

이미지

  • 이미지 출처 : https://i.imgur.com/VeuoJbK.png

삭제

이미지2

  • 이미지 출처 : https://imgur.com/6dimHpq.png

구현

  • python의 내장모듈인 heapq모듈을 통해 간편하게 최소힙을 구현할수 있다.

    • 단, 최대 힙의 경우, 별도의 추가 구현이 필요하다.

  • heapq모듈을 임포트한 후, 다음과 같은 함수를 활용할수 있다.

    • 기존 리스트를 최소 힙 구조로 변환

        heapq.heapify(list)

    • 최소 힙에 원소 추가

        heapq.heappush(heap, 추가할 원소)

    • 힙에서 최소값 삭제

      • heappop() 함수를 사용하여 가장 작은 값을 삭제할수 있다.

      • 이때, 원소를 삭제할 대상 리스트를 인자로 넘길경우 삭제된 가장 작은값을 리턴.

        heapq.heappop(heap)
  heapq.heappop()

    • 최소 힙에서 최소값 확인

      • 단순히 최소값을 확인만 하는 경우, heap[0]을 통해 확인 가능하다.

      • 단, N번째 큰/작은 값을 확인하는 경우 별도의 구현이 필요하다.

구현 - 응용

  • 최대 힙 및 우선순위 힙의 구현

    • heapq 모듈은 최소 힙만 구현해두었으므로, 별도의 구현이 필요하다.

    • 힙에 튜플을 원소로 추가/삭제하는 경우 튜플 내에서 제일 앞의 값을 기준으로 최소 힙을 구현한다.

      • (-원소, 원소)의 값을 가지는 튜플을 추가하여 최대힙 구현.

      • (우선순위, 원소)의 값을 가지는 튜플을 추가하여 우선순위 힙 구현.

    • 그 후, 힙에서 값을 읽어올때는 각 튜플에서 인덱스 1에 있는 값을 가져오면 된다.

  • K번째 최소/최대값의 구현

    • 힙을 구현한 후, heappop()을 K번 실행한 루트노드가 K번째 최소/최대값이 된다.

  • 힙 정렬

    • 힙을 구현한 후, heappop()으로 나오는 값들을 리스트에 추가하여 정렬한다.

      • 이때 시간복잡도는 O(NlogN)으로, 버블/선택정렬의 O(N^2)보다 훨씬 빠르다.

You May Also Enjoy