퀵정렬 설명 → 더보기 더보기 · ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘 · 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다 · 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. · 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 과정 설명 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) ..

※ 12번 문제에 대한 답안은 교재에서 사용하는 pseudocode 형태로 알고리즘을 쓰시오. (2) 과제 제출은 pdf 파일로 만들어서 Bb에 업로드한다. Write a θ(n) algorithm that sorts n distinct integers, ranging in size between 1 and kn inclusive, where k is a constant positive integer. (Hint: Use a kn element array.) k는 일정한 양의 정수이고, n개의 서로 다른 정수를 1에서 kn까지 정렬하는 θ(n) 알고리즘을 작성하라. (힌트: kn 요소 배열 사용) https://ict-nroo.tistory.com/58 [Algorithm] 3-7. Counting So..

풀어야할 인스턴스를 몇개로 나눈다. 부분으로 나누고 그 각 부분을 재귀적으로 해를 구한다. 그리고 원래 instance의 해를 구하는 것이다. Binary Search가 가장 기본적인 Divide and conquer이다. >> 합병정렬 알고리즘의 구체적인 개념 더보기 합병 정렬(merge sort) 알고리즘의 구체적인 개념 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 다음의 단계들로 이루어진다. •분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. •정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 ..

둘 중에 누가 더 클지 모를 때 g(n)을 f(n)으로 나눠서 극한값을 취해주면 알 수 있다. 정 모르겠으면 로피탈써라. 분모 미분 분자 미분 근데 이 정도로는 나오지 않을 것이다. recurrsive 한 알고리즘 fib(n){ if(n

Order는 한마디로 하면 시간복잡도 함수에서 상수를 무시하고 n값(input)이 클 때 어떻게 behave하느냐를 나타낸다. 우리가 다루는 알고리즘의 효율성이라는 것은 input사이즈가 클 때 문제가 된다. 왜 무시하느냐? 3n^2인 것은 다른 컴퓨터로 돌리면 0.5n^2 정도 차이밖에 안난다. 그래서 상수를 무시하고 나타낸다. 또 차수가 높은 항만 취해서 나타내고 차수가 낮은 항은 무시한다. 0.1 n^2이 n보다 언젠간 커진다. asymtotic x축은 input 사이즈, y축은 걸리는 시간과 비례 빅O의 f(n)의 정의이다. time complexity function 들의 집합이다. 양의 실수인 상수 c가 존재하고, 음이 아닌 정수 n이 존재해서 g(n)

오늘은 알고리즘의 효율성 분석에 대해 알아보자 알고리즘의 효율성 분석은 시간 복잡도 함수로 나타낸다. f(n)의 BigO를 본다. 모든 알고리즘 input이 커질수록 시간이 커진다. 효율성을 나타낼 때 그 알고리즘에 실행에 걸리는 시간을 input 사이즈에 대한 함수로 나타낸다. n = input 사이즈 ,f(n) = 걸리는 시간 input size가 중요하지만 다음에 설명하겠다. 시간 복잡도의 분석을 time complexity analysis라고 한다. T(n)은 걸리는 시간이다. input 사이즈에 대해 걸리는 시간. 시간 복잡도 함수 : time complexity function input size가 같은 인스턴스라도 걸리는 시간이 다를 수 있다. 예를 들어 버블 sort를 보면 순서가 굉장히 ..

단순한 연산들의 sequence에 따라서 실행을 하면 그 결과로서 주어진 문제의 solution이 얻어지는 해법이 알고리즘이다. 여기서 중요한 것은 각 스텝이 기계적으로 연산 가능한 단순한 연산이다. 단순하지 않는 연산 : 두 수의 최대 공약수를 구하라 이 과정이 언젠가는 끝나야 한다. 끝나지 않고 영원히 돌아가면 알고리즘이 아니다. 솔루션을 내놓아야 한다. 항상 정확한 솔루션이여야 알고리즘이라고 말할 수 있다. sorting 알고리즘이라고 부를 수 있으려면 그 알고리즘은 어떤 input이 들어오더라고 sorting할줄 알아야 한다. 인스턴스라는 것은 어떤 문제에 무수히 많은 경우가 있다. 최단경로 문제를 보면 최단경로 문제를 푸는 무수히 많은 그래프가 있고, 각각에서 최단경로 문제가 있는것이다. 인스턴..