🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/🍯개념
-
선택문제란 ?🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/🍯개념 2021. 10. 15. 11:07
선택문제 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제 원래라면 단순하게 최소 숫자를 k번 찾거나(Okn), 숫자들을 정렬한 후 K번째 숫자를 찾는다.(Onlogn) 이진탐색으로는 ? 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교하면서, 입력을 1/2로 나눈 두 부분 중 한 부분만을 검색한다. 선택문제는 입력이 정렬되어 있지 않으므로, 입력 숫자들 중에서 (퀵정렬과 같이) 피봇을 선택하여 분할한다. 분할하고 알아야 하는 것은 Small 그룹(피봇보다 작은 숫자그룹)과 Large 그룹(피봇보다 큰 숫자그룹)의 크기(숫자의 개수)이다. - Small 그룹에서 k번째 작은 숫자가 속한 경우 => k번째 작은 숫자를 Small 그룹에서 찾는다. - Large 그룹에서 k번째 작은 숫자가 속한..
-
Quick Sort(퀵정렬)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/🍯개념 2021. 7. 19. 12:24
Quick Sort란? 퀵정렬은 병합정렬과 비슷한 분할 및 정복 방법이다. 차이점은 pivot값을 사용한다는 것이다. 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘이다. (커다란 크기의 입력에서는 Merge Sort보다 평균적으로 성능 더 좋음) 문제를 2개의 부분문제로 분할한다. 각 부분문제의 크기가 일정하지 않은 형태의 분할정복 알고리즘이다. 퀵정렬의 아이디어는, 피봇이라는 배열 원소 값을 기준으로, 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에 놓는다. 퀵정렬의 성능은 피봇선택이 좌우한다. 피봇으로 가장 작은 숫자 또는 가장 큰 숫자가 선택되면, 한 부분으로 치우치는 분할을 야기한다. 최선/평균의 경우 O(nlogn) :..
-
MergeSort(합병정렬)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/🍯개념 2021. 7. 19. 08:29
MergeSort란? 합병정렬은 분할과 정복으로 정렬하는 방법으로서, O(nlogn)로 정렬 속도가 빠르다. 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소한다. 분할하는 부분은 중간 인덱스 계산과 2회의 순환 호출이므로 O(1) 시간이 소요된다. 합병 수행시간은 입력의 크기에 비례한다. 2개의 정렬된 배열 A와 B의 크기가 각각 m과 n이라면, 최대비교횟수 = (m+n-1)으로, 시간복잡도는 O(m+n) => O(n) 층수는 k번 1/2로 분할했으면 k개의 층이 생기는 것이고, 입력의 크기가 n일 때 2^k = n으로부터 k는 logn임을 알 수 있다. 따라서 합병정렬의 시간복잡도는 O(nlogn)이다. 단점! 공간복잡도가 O(n)이다. 2개의 정렬된 부분을 하나로 합병하기 위해, ..