알고리즘2 [Python] Merge Sort: 병합 정렬 안녕하세요. 우주신 입니다. 오늘은 병합 정렬(Merge Sort)에 대해 포스팅하겠습니다. 병합 정렬은 정렬되지 않은 전체 데이터를 하나의 단위로 분할한 후에 분할한 데이터들을 다시 병합하며 정렬하는 방식 입니다. 즉, Divide: n개의 데이터를 n/2개 데이터로 나누고 2개의 리스트에 넣습니다.Conquer: 2개의 리스트들의 데이터가 하나가 될 때까지 재귀적으로 나눕니다.Combine: 각각의 2개의 리스트를 병합 합니다. 시간 복잡도는 최악의 경우 O(nlogn)로 이전 포스팅에서 소개했던 insertion sort보다 효율적인 알고리즘 입니다. 코드를 통해 자세히 보겠습니다. 우선, 데이터를 리스트로 입력 받겠습니다.입력 받은 데이터를 띄어쓰기 기준으로 구분하여 이를 정수형으로 리스트에 저장.. 2018. 3. 30. [Python] Insertion Sort: 삽입정렬 안녕하세요. 우주신 입니다. 오늘은 삽입 정렬(Insertion Sort)에 대해 포스팅하겠습니다. 알고리즘을 배울 때, 가장 먼저 접하게 되는 친숙한 삽입 정렬입니다.삽입 정렬은 말 그대로 데이터의 삽입을 통해 정렬을 완성하는 알고리즘 입니다.현재 위치에서, 이미 정렬된 이전 배열들의 데이터를 차례대로 비교하여 자신의 위치를 찾아 그 위치에 삽입하는 방식 입니다. 시간 복잡도는 최악의 경우 O(n^2)이고, 최선의 경우(이미 정렬되어 있는 경우)에는 O(n) 이므로 Big-O (n^2) 입니다. 5 3 4 6 1 2 5 3 4 6 1 2 3 5 4 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 1 3 4 5 6 2 1 2 3 4 5 6 파이썬 코드를 통해 자세히 알아보겠습니다. 우선, 데이터를 .. 2018. 3. 29. 이전 1 다음
