개복치개발자

힙소트의 경우, big-O는 O(NlogN) 입니다. 왜 NlogN일까요? Heapify 해주는데 logN, 정렬하는데 N, 곱해서 NlogN입니다. 자, 얘를 한번 구현해보겠습니다. 그 전에 파이썬 반복문 하나 보고 가겠습니다 :) for i in range(10, -1, -1) : print(i) 10 9 8 7 6 5 4 3 2 1 0 for i in range(10, -1, -2) : print(i) 10 8 6 4 2 0 for i in range(10, -2, -1) : print(i) 10 9 8 7 6 5 4 3 2 1 0 -1 -- 자, 일단 파이썬 반복문 어떻게 동작되는지 확인했습니다. heapify와, heap sort를 코딩으로 구현해봤습니다. 물론 이것도 코드만으로 머릿속에서 다 ..

이번에는 Heap Sort에 대해서 알아봅니다. Heap을 Sorting 한다 인데, Heap 이라는 것이 무엇일까요? 이거는 아닙니다.. Heap이라는 애는 최댓값 및 최소값을 빨리 찾아내기 위해 고안된 완전이진트리 형태의 자료구조 입니다. 뭔가 말이 어려운데, 그냥 아래의 트리 같은 형태로 자료 쌓아놓고, 최대값이나 최소값 빨리 찾는 것입니다. 자, 그렇다면 동작 방법을 한번 알아볼까요? 이와 같은 배열이 있습니다. [4, 10, 3, 5, 1] 얘를 이진 트리 형태로 만들어볼게요 왼쪽 오른쪽 왼쪽 오른쪽 이렇게 순서대로 배치했습니다. 그 다음 최대값을 찾아내는 과정을 진행해줘야 하는데, 이걸 heapify라고 합니다. 자, heapify가 어떻게 진행되는지 한번 보겠습니다. 가장 큰 애(최대값)이 ..

Pivot을 기준으로 작은 것은 왼쪽, 큰 것은 오른쪽으로 정렬해가는 과정을 보겠습니다. 아래의 순서대로 순서가 체인지가 됩니다. 이렇게 바꾸고 나서, pivot의 위치도 변경해줍니다. 자, 이렇게 하면 pivot을 기준으로 작은 것은 왼쪽으로 몰았고, 큰 것은 오른쪽으로 몰았습니다. 여기에서 pivot값인 70을 기준으로 작은 것들 중 또 pivot을 정하고 큰 것들 중 또 pivot을 정해서 반복해줍니다. 왼쪽 것에 대한 pivot은 50이 되겠고, 오른쪽 것에 대한 pivot은 80이 되겠죠? ----- 자, 이제 코드를 한번 쳐 보겠습니다. 코드를 쳐서, 주석을 달아봤습니다. 이 2개를 프린터 찍어보면 잘 나오는 것을 확인하실 수 있습니다. list = [10, 80, 30, 90, 40, 50,..

퀵소트에 동작방식과 big O에 대해서 알아보겠습니다. 퀵소트는 뭔가 이름만 들었을 때 굉장히 빠른 것 같습니다. 얘는 pivot이라는 좀 특이한 방식을 사용하고, 시간복잡도가 n log n ~ n^2 입니다. 어떻게 동작하는지, 한번 아래의 그림을 보겠습니다. 만약 맨 오른쪽 애를 pivot이라고 설정하면, pivot을 기준으로 작은애들은 왼쪽, 큰 애들은 오른쪽으로 옮겨줍니다. 이 과정을 다 쪼개질 때 까지 반복해줍니다. 자, 시간복잡도를 알아보겠습니다. merge sort와 같이 n long n 이 나옵니다. (반으로 쪼개고 - log n , 정렬하기 n) 다만 조금 특이한 것이 worst case라는 것이 있습니다. 위와 같이 이미 정렬된 배열의 경우에는, 배열을 쪼개는 것이 의미가 없어지기 때문..

저번 시간에 이론으로만 봤던, Merge Sort를 실제로 코드로 구현해보겠습니다. 저번 시간에 머지 소트를 잠깐 설명했는데, 좀 더 자세히 설명드리겠습니다. 이 머지 소트가 모든 것을 다 나누고나서 합치는것이 아니라, 나누는 중간에 합칩니다.. 이게 무슨 뜻이냐 하면.. 아래의 그림으로 순서를 보겠습니다. 이런 순서대로 sort가 동작합니다. 자, 그렇다면 얘를 따라서 코딩을 해보겠습니다. 코드는 몇줄 되지도 않는데, 얘를 한번에 이해하기는 조금 힘듭니다. 일단 머지소트를 실행합니다. list = [38, 27, 43, 3, 9, 82, 10] mergeSort(list) 때문에 , 로그를 찍히는 것을 보시는게 가장 이해가 빠르실 듯 합니다. 아래와 같이 나오는 것을 보실 수 있으실 겁니다. 이 부분에..

Merge Sort 는 이름에서 풍겨오는 기운이, 뭔가를 합친다 라는 것 같습니다. 지금까지 일자로 나열된 형태의 데이터를 정렬하는 것과는 조금 다른 방식으로 정렬합니다. 일단 합치기 위해서는 쪼깨는? 작업 부터 합니다. 아래와 같이 생긴 애가 있습니다. 위의 아이를 절반씩 계속 쪼개줍니다. 자, 그 다음 정렬하면서 합쳐줍니다. 이렇게 합칠 수 있는데, 자 여기까지 보시면 저렇게 쪼개고 합치는 과정을 이해하셨을 것이라 생각합니다. 근데 이렇게 복잡한 방식으로 정렬을 왜 하는가? 에 대한 의문이 드실 수 있습니다. 그 이유는 이전에 봤던 정렬들보다 빠릅니다. 이 정렬의 시간복잡도를 보겠습니다. 일단 분할 / 합병 2가지로 나눕니다. 분할 아래와 같이 8개가 있는 리스트를 분할합니다. 크기가 8인 리스트를 ..

Selection Sort의 코드와 빅오를 알아보겠습니다 :) 자료구조를 처음에 배웠을 때는 굉장히 하기 싫었는데, 오랜만에 다시보니 재미있네요 모두 즐겁게 코딩 했으면 좋겠습니다. 자, 코드를 한번 쳐 보겠습니다. 생각보다 너무 쉬워서, 설명한 것이 별로 없기는 합니다만 조금 의문이 드실 수 있는 부분이 if list[min_index] > list[j] : 이 부분이 의문이 드실 수 있을 것 같아서, 한번 찍어봤습니다. 아래와 같은 코드로 찍어봤고 결과는 아래와 같이 나오는데 min_index의 값이 수정되어 가는 것을 볼 수 있습니다. 시간복잡도는 (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉,O(n2) 입니다.

Selection Sort 라는 이름처럼 골라서 정렬하는 것입니다. 원리는 매우 단순합니다. 왼쪽부터, 리스트에 있는 가장 작은 애랑 순서를 바꿔줍니다. 일단 아래와 같은 리스트가 있다고 하면, 가장 왼쪽의 64를 가장 작은 11과 바꿔줍니다. 자 1라운드 돌아갑니다. 그리고 25부터, 2라운드가 돌아갑니다. 그 다음 3번째 것 부터, 3라운드 돌아갑니다. 그 다음 4라운드는 정렬이 되어있기 때문에, 놔둡니다. 이렇게 절차가 진행이 됩니다. 자 이 것을 코드로 한번 구현해보겠습니다.

Insert Sort에 구현과 함께 Big-O를 알아보겠습니다. insert sort를 코드로 구현해봤습니다. 설명과 주석으로 한방에 이해하시는 분은 굉장히 훌륭하신 것 같습니다. 저는 이 로직을 print로 찍어봤습니다. 일단 코드를 포인트마다 출력되게 찍었고 얘를 출력해보면 아래와 같이 나옵니다. 저기 list : [] 라고 찍히는 부분에서, list에 있는 값을 하나씩 밀고, key의 값이 들어갈 위치를 찾아서 넣어주는 과정을 유심히 보시면 이해가 가장 빠르실 것 같습니다. 시간복잡도의 경우 2가지로 나뉘는데 best와 worst가 있습니다. 만약 [1,2,3,4,5] 라고 생긴 애가 있다면 중간에 list : 부분의 이동이 없기 때문에, O(n)이 가능하지만, 반대의 경우 O(n^2)이 됩니다.

insert sort를 알아보겠습니다. bubble sort 같은 경우에, 왼쪽에 있는 애를 오른쪽으로 계속 미는 느낌이었다면 insert sort 같은 경우에는 오른쪽애 있는 애를 왼쪽으로 민다는 느낌인 것 같습니다. 한번 아래의 예시를 보겠습니다. 자 얘를 가 보겠습니다. 2번째 애 부터 시작합니다. 13은 앞에 더 큰 항목이 없으니 그대로 있고 이동 또 이동 이렇게 하면 정렬이 끝납니다. 매우 쉽게 이해하셨을 것이라고 생각합니다. 그러면 이 과정을 코드로 표현하고, 시간복잡도를 알아보겠습니다.