1. Insertion sort $a_{k}$원소 이전의 $a_{k-1}$까지는 전부 정렬돼있음. $a_k$를 $a_0$~$a_{k-1}$까지의 올바른 자리에 삽입하기. 정렬되어 있는 배열에 나를 삽입하기. 수행시간 Best: O(n) → 완전 정렬돼있을 때. 각 원소마다 자기 하나 왼쪽의 원소랑이랑만 딱 한번 비교 수행. 이미 자기 왼쪽 배열의 최대(k-1)보다 자기가 큼으로 삽입이 일어나지 않음. Worst: O($n^2$) → k번의 원소마다, k-1번의 삽입을 위한 비교가 일어남. 코드 target이 현재 값. num[cur]가 num[i-1]부터 num[0]까지 내려가면서, target보다 큰 값이 없을 때까지 cur를 감소시킴. num[cur]가 target보다 작다면 루프 멈추고, num[c..