[ 삽입 정렬 ] 알고리즘

 

 

1.  개념

     

      삽입 정렬 : 이미 정렬된 범위에 정렬되지 않은 데이터를 알맞은 위치에 끼어넣는 정렬

     

      * 시간 복잡도 : O(n²)

           

     삽입 정렬 방법

 

      1) 두번째 인덱스에서 출발한다

 

      2) 현재 선택한 데이터 앞부분은 이미 정렬된 범위이며 정렬된 범위 내에 선택한 데이터를 알맞은 위치에 넣는다

 

      3) 반복  

 

                 

          삽입 정렬이 버블 정렬, 선택 정렬과 다른 점

 

          - 버블 정렬, 선택 정렬 : 첫 번째 인덱스부터 시작 / 삽입 정렬 : 두 번째 인덱스부터 시작

 

          - 버블 정렬, 선택 정렬 : 정렬된 범위 방치 / 삽입 정렬 : 정렬된 범위 계속 이용

 

 

 

 

2.  문제 풀이

 

 

# 1  ATM 인출 시간 계산하기 - 백준 11399번

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

11399번: ATM

 

 

# 최소 시간 합을 구하기 위해서는 인출 시간이 가장 긴 사람을 뒤에 배치해야 하므로 인출 시간을 오름차순으로 정렬해야 한다.

import sys 
input = sys.stdin.readline 

# 입력 받기
n = int(input())
num = [0]
num.extend(list(map(int,input().split())))
sumList = [0]

# 삽입 정렬
for i in range(2,n+1):
    key = num[i]   # 데이터 선택 - 2번째 데이터부터 출발
    for j in range(1,i):  # 1~i : 정렬된 범위 - 선택한 데이터 알맞은 위치에 삽입
        if key < num[j]:
            num[i],num[j] = num[j],num[i]

# 구간 합 구하기

for i in range(1,n+1):
    sumList.append(num[i]+sumList[i-1])

# 답 : 구간 합의 총합
print(sum(sumList))