[알고리즘] 정렬 / Sorting / 삽입 정렬(Insertion Sorting)

Insertion Sort (삽입 정렬)

: human-like

1. 처음 주어지는 것: 빈 리스트 & 정렬해야 하는 카드들
2. 원리: index 순서대로 읽어가며 이미 정렬된 value들과 크기 비교하여 적절한 위치에 삽입함

• 새로운 빈 리스트를 하나 생성하는 것 대신(메모리 많이 잡아 먹음)
• ⇒ in-place기법 (주어진 표를 변형 + 원본이 훼손됨)

def insertion_sort(list):
	for i in range(i, len(list)):
    	key = list[i]
        j = i-1
        while j >=0 and key < list[j]:
        	list[j+1] = list[j]
        	j -= 1
        list[j+1] = key

1. sorted된 아이템들 중에 현재 Key와의 비교가 이루어질 위치 탐색: O(N) -> binary search 통해 O(logN)
2. shift : O(N)
3. 각 key에 대한 location 최종 삽입: O(1) (이미 1, 2단계로 location이 최종 선택된 상태)
4. 1~3의 단계를 N(=len(list)) 만큼 반복

=> Overall complexity: O(N^2)

 

 

관련 문제: 백준 11399 (ATM)

https://www.acmicpc.net/problem/11399

11399번: ATM

 

문제 개요

N명, i번 사람이 돈을 인출하는데 P_i분 소요

줄을 서는 순서에 따라 돈을 인출하는 데 각 사람이 인출하는 데 필요한 시간의 합이 달라짐

 

Input

줄을 서 있는 사람 수 N (ex. 5)

각 사람이 돈을 인출하는 데 걸리는 시간 P (ex. 3 1 4 3 2)

 

Output

각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값 (ex. 32)

 

 

문제 풀이

 

Pseudo Code

: for문으로 key를 하나씩 지정

각 key의 위치를 while문 통해 탐색

그렇게 필요한 위치를 하나씩 탐색.

비록 시간 복잡도는 n^2

 

(3, 1, 4, 3, 2)

1 2 3 4 5 => (3, 1, 4, 3, 2) => 39분 (작은 값을 마냥 앞에 배치한다고 개선되지 않음)

2 5 1 4 3 => (1, 2, 3, 3, 4) => 32분

 

결론: value의 오름차순 소팅! (삽입정렬로 해결)

 

import sys

for t in range(2):
    if t == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = list(map(int, sys.stdin.readline().split()))

for i in range(1, n):
    key = inputs[i]
    j = i-1
    while j>=0 and key < inputs[j]:
        inputs[j+1] = inputs[j] //swap
        inputs[j] = key //swap
        j -=1 //최종 목적지까지 계속 탐색

answer = [0]
for x in inputs:
    answer.append(x+answer[-1])

print(sum(answer))