우주의 IT 소행성

안녕하세요. 오늘은 백준 알고리즘 1966번 프린터 큐를 풀어보았습니다.

먼저 입/출력을 받을 변수와 대략적인 코드 진행의 가이드라인을 그려보겠습니다.

입력 : 테스트케이스의 수, 문서의 개수, 원하는 문서의 인덱스, 중요도

출력 : 원하는 문서의 인쇄 순서

대략 2~3가지의 해결 방법이 떠오르는데, 이번 풀이에서는 우선순위를 리스트에 저장 해두었다가

중요도를 비교하여 제일 높은 중요도일 경우 추가하고, 아닐 경우 맨 뒤로 보내는 방법으로 풀이해보겠습니다.

priority 리스트에 우선순위를 입력하고

queue 덱에 원하는 문서의 인덱스, 그 문서의 우선순위를 튜플로 삽입합니다.

그 뒤 반복을 통해 현재 큐의 우선순위가 제일 높은 우선순위일 경우:

우선순위 리스트 priority에서 현재 우선순위를 제거해줍니다.

현재 큐의 우선순위가 제일 높은 우선순위가 아닐 경우:

queue의 맨 뒤에 현재 큐를 추가하고

현재 큐를 삭제시켜줍니다.

이렇게 priority가 빌 때 까지 연산을 반복하면 원하는 결과가 정렬되겠습니다.

그 후 queue에서 원하는 인덱스를 찾아 출력해주면 끝입니다.

<풀이 코드>

from collections import deque
import sys
loop = int(sys.stdin.readline())
for _ in range(loop):
    doc_count, index = map(int, sys.stdin.readline().split())
    priority = list(map(int, sys.stdin.readline().split()))
    queue = deque([(i, priority[i])for i in range(doc_count)])

    idx = 0
    while idx < doc_count:
        if queue[idx][1] == max(priority):
            priority.remove(queue[idx][1])
            idx += 1
        else:
            queue.append(queue[idx])
            queue.remove(queue[idx])

    for i in range(doc_count):
        if queue[i][0] == index:
            print(i + 1)
            break

What does not destroy me, makes me stronger. - Friedrich Nietzsche

아직 모자라지만, 항상 배우고, 나아가려합니다.

오타 / 오류 / 개선점 / 질문 환영합니다 ^^

오늘은 가장 기초적인 알고리즘 중 하나인 이분 탐색 (이진 탐색)에 대해서 알아보겠습니다.

이분 탐색에 앞서 순차 탐색에 대해서 복습을 해볼 텐데요.

N개의 데이터가 들어있는 어떤 데이터의 모음 DATA가 있을 때 DATA의 0번째 데이터부터 N번째 데이터까지 모두 방문하여 탐색하는 것을 순차 탐색이라고 합니다.

# 리스트에서 주어진 1개의 값을 찾는 소스코드
data = [12, 255, 156, 8798, 15, 487, 212, 11, 98, 9, 878, 999, 445, 54563, 546779, 78]
print("탐색할 데이터는 : , end='')
target = int(input())

for i in data:
	if i == target:
    	print(target, "을 찾았습니다!")
    	break

당연히 N개의 데이터가 들어있으니 탐색에도 N번만큼의 시간이 소요되겠습니다.

그렇다면 데이터가 1억 개가, 10억 개가, 아니 1조 개가 넘게 유입되어도 과연 순차 탐색으로 탐색을 해낼 수 있을까요?

정답은 "아니오" 입니다.

실제 코딩 테스트나 실무에서 사용하게 되는 알고리즘은 항상 최적의 시간 복잡도를 가져야 합니다.

1조 개의 데이터를 1조 번만큼 탐색하지 않고 더 적은 횟수를 탐색하는 알고리즘이 있다면 정말 좋겠습니다.

그런 알고리즘이 바로 오늘 배울 이분 탐색 알고리즘입니다.

이분 탐색 알고리즘이란?

- 탐색 범위를 절반으로 줄여나가면서 탐색하는 알고리즘

조건 : 배열 내부의 데이터가 오름차순으로 정렬되어 있어야 함

사용 시점 (보편적) : 1000만 이상의 데이터 탐색할 때, 정렬되어 있는 데이터를 탐색할 때

장점

- 매우 빠르게 데이터를 찾을 수 있음

- 탐색 범위를 절반씩 좁혀나가며 데이터를 탐색함

- O(logN)의 시간 복잡도를 가짐

이분 탐색은 탐색 범위의 시작점, 끝점, 중간점 세 점 간의 비교로 원하는 데이터를 빠르게 찾아내는 알고리즘입니다.

이분 탐색에 대해서 간단히 알아보도록 하겠습니다.

먼저 1부터 100까지 오름차순으로 정렬된 리스트가 있다고 가정합시다.

이 리스트에서 이분 탐색을 이용해 67을 탐색해봅시다.

시작점 = start = 1

끝 점 = end = 100

중간점 = mid = (시작점 + 끝점) // 2 = 50

타겟(target)인 67이 중간점보다는 크고 끝 점보다는 작습니다.

오름차순으로 정렬되어있는 리스트이기 때문에 중간점부터 끝점 사이에는 50 ~ 100까지의 숫자만 들어있으므로

우리는 시작점 ~ 중간점 ( 1 ~ 50 )를 탐색할 필요가 없습니다.

따라서

시작점 = 50

끝 점 = 100

중간점 = 75로 수정을 해 줍니다.

이번에는 타겟이 시작점보다 크고 중간점 보다 작습니다 (start <= target <= mid)

따라서

시작점 = 50

끝 점 = 75

중간점 = 62로 수정을 해 줍니다.

계속해서 타겟을 찾을 때 까지 탐색 범위를 좁혀줍니다.

축하드립니다! 계속해서 반복하다보니 중간점에 우리가 그토록 찾던 타겟이 나타났습니다!

이처럼 탐색 범위를 절반의 절반으로 줄여가는 방법을 이분 탐색이라고 합니다.

1 ~ 100까지 전체 데이터의 개수는 100개 이지만 이분 탐색을 이용해 총 7번의 탐색으로 원소를 찾았습니다.

만약 순차 탐색이였다면 더 많은 시간이 소요되었을 것입니다.

이제 이분 탐색을 파이썬으로 구현해보겠습니다.

재귀 함수로 구현한 이분 탐색법

def binary_search(array, target, start, end):
	if start > end:
    	return None
    mid = (start + end) // 2
    if array[mid] == target:
    	return mid
    elif array[mid] > target:
    	return binary_search(array, target, start, mid - 1)
    else:
    	return binary_search(array, target, mid + 1, end)

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

반복문으로 구현한 이분 탐색법

def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start + end) // 2
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1
    return None

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

질문, 추가, 오류, 오타, 지적 환영합니다.