-

저번 시간에 이론으로만 봤던, 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은 앞에 더 큰 항목이 없으니 그대로 있고 이동 또 이동 이렇게 하면 정렬이 끝납니다. 매우 쉽게 이해하셨을 것이라고 생각합니다. 그러면 이 과정을 코드로 표현하고, 시간복잡도를 알아보겠습니다.

버블소트의 구현과, 빅오에 대해 알아보겠습니다. 아래와 같이 코드로 한번 구현해봤습니다. 얘의 출력 과정을 알아보면 아래와 같이 찍힙니다. 처음 버블 소트를 봤다면, 머리속에서 코드가 출력되는 부분이 시뮬레이션 잘 안될 수 있습니다. 아래의 출력물을 참고하시면 더 좋을 듯 합니다. ----------- i = 0 j = 0 list[j] = 64 list[j+1] = 34 j = 1 list[j] = 64 list[j+1] = 25 j = 2 list[j] = 64 list[j+1] = 12 j = 3 list[j] = 64 list[j+1] = 22 j = 4 list[j] = 64 list[j+1] = 11 j = 5 list[j] = 64 list[j+1] = 90 ----------- i = 1 ..

처음으로 해볼 정렬은 버블 정렬 bubble sort 입니다. 버블 정렬하면 저는 현아의 퍼블팝밖에 생각이 안나네요... https://www.youtube.com/watch?v=bw9CALKOvAI 자, 버플팝이 중요한게 아니라 버블 정렬을 해보겠습니다. 버블 정렬의 이론은, 옆에 있는 원소와 비교해서 정렬해주는 알고리즘입니다. 거품이 비비듯이 움직인다고 해서 버블소트라는 이름을 가지고 있는 것으로 알고 있습니다. 오른쪽에 있는 애가, 왼쪽에 있는 애보다 작으면, 위치를 바꿔줍니다. 예를 들면, 아래와 같은 애들을 순서대로 정렬하고 싶은데, 버블 소트를 이용해서 한번 해 보겠습니다. 과정들을 쭉 지켜보시면 버블 소트가 어떻게 동작하는지 알 수 있을 겁니다. 일단 1라운드 이렇게 앞의 2개 비교해서 바꿔..

알고리즘 성능 분석할 때, 빅오표현법(Big-O notation)이라는 것을 사용합니다. 모든 개발자들이 코드를 짤 때, 코드가 빨리 실행이 되는 것을 원하겠죠? 빠르게 실행되는 알고리즘을 짜기 위한 시간 측정 방법입니다. 빅오에 대해 처음 들어보시는 분들은 이해가 잘 안되실 수도 있으니 아래의 예시를 들어 놨습니다. 위의 코드를 보면 big_o1 이라는 애를 실행하면, 연산이 딱 1번 됩니다. 때문에 이 아이의 시간복잡도 big-0는 O(1) 입니다. 아래 코드도 또 보겠습니다. 위의 big_oN이라는 함수는 arr라는 것의 크기 만큼 실행되기 때문에 얘의 big-o는 O(N)입니다. 또 여기에 중첩반복문을 통해서 O(N * N) 즉 O(N^2) 을 아래와 같이 만들 수도 있습니다. 그리고 여러가지 정..

자료구조와 알고리즘에 대한 정의부터 하고 가겠습니다. 일단 위키에서는 이렇게 설명하고 있습니다. 자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.[1][2][3] 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.[4] 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. (출처 - https://ko.wiki..