-

이번 시간에는 삽입 정렬에 대해 알아보겠습니다. 알고리즘에는 많은 유형이 있지만 주로 탐색과 정렬하는 것들이 많습니다. 탐색을 하기 전에는 미리 정렬을 해야 합니다. 정렬된 자료를 탐색하는 강력한 알고리즘이 있거든요. 정렬하는 방법도 여러가지가 있습니다. 그 중에 오늘은 삽입 정렬 차례입니다. 삽입 정렬이란 여러 개의 섞인 숫자가 있을 때, 그 숫자를 작은 순서부터 큰 순서로 정렬하는 겁니다. 삽입 정렬은 첫 숫자는 놔두고, 두 번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣습니다. 세 번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣습니다. 이렇게 끝까지 계속하면 정렬됩니다. 쉽게 설명하자면 오른손에 쥔 정렬되지 않은 카드를 왼손에 ..

이번 시간에는 시간의 복잡도를 설명하겠습니다. 시간의 복잡도는 알고리즘을 수행하는 데 평균적으로, 또는 최악의 경우 얼마만큼의 시간이 걸리는 지 보여줍니다. 반대의 개념으로 공간의 복잡도도 있는데, 알고리즘이 얼마만큼의 메모리를 잡아먹는 지 보여줍니다. 공간의 복잡도는 알고리즘을 짜는데 있어 크게 고려하는 부분이 아닌데다가 보통은 시간의 복잡도를 더 중요하게 여기기 때문에 시간의 복잡도를 주로 다루겠습니다. 그리고 그냥 복잡도라고 해도 시간의 복잡도라고 생각하시면 편할 것 같습니다. 복잡도를 계산하는 과정은 정말 어려우니 여기서는 생략하겠습니다. 대학교에서 배우는데 학원에서는 가르쳐주지 않습니다. 우리는 간단히 복잡도를 표시하는 방법과 그것이 시사하는 바를 알아보려고 합니다. 복잡도는 주로 빅오 표기법을..

문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participantcompletionreturn ["leo", "kiki"..