Algorithm5 퀵 정렬 (Quick Sort) 알고리즘 퀵 정렬(Quick Sort) > 문제가 2개로 분할되고, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘 > 쪼개지는 데이터의 크기가 일정하지 않다. 피봇(Pivot)이라고 하는 일종의 인덱스를 통해 기준값을 지정하고, 피봇보다 작은 숫자들은 왼편으로, 큰 수는 오른편에 위치하도록 분할한다. (오름차순) 분할된 부분에 대해서는 재귀적으로 수행하여 정렬 피봇은 분할된 왼편이나 오른편의 부분에 포함되지 않는다. 피봇은 이미 정렬된거라고 보고 나머지에 대하여 재귀적으로 수행 알고리즘 순서 2020. 9. 21. 분할 정복 알고리즘 , 합병정렬(Merge Sort) 알고리즘 자바 코드 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며 이들의 해를 취합하여 원래의 문제를 얻기위해 사용한다. 부분문제 > 분할된 입력에 대한 문제 (SubProblem) 부분해 > 부분문제의 해 더 이상 분할 할 수 없을때 까지 부분문제를 계속해서 분할한다. 정복과정 > 부분해를 취합하면서 구하고자 하는 원래 문제의 답을 얻는다. 크기가 N인 입력에 대한 분할정복 알고리즘 첫번째 나누어진 각각의 크기에 대한 입력은 n/2 두번째 나누어진 각각의 크기에 대한 입력 n/4 . . . 더 이상 입력의 크기를 나눌 수 없는 경우 (1인경우) 까지 문제의 수준을 쪼개는 과정을 분할 과정이라고 한다. 입력의 크기가 N일때 총 분할 횟수의 일반화.. 2020. 9. 21. 알고리즘의 효율성, 시간복잡도 (Big-O) notation 알고리즘의 효율성은 - 알고리즘의 수행시간 (시간복잡도, Time Complexity) - 수행하는동안 사용되는 메모리 공간의 크기 (공간복잡도, Space complexity) 로 나타낼 수 있다. 사용되는 메모리, 공간등은 주어진 환경에 따라서 다르기 때문에 보통 알고리즘을 비교할때는 시간복잡도로 표현한다. 시간복잡도는 알고리즘의 수행하는 기본적인 연산의 횟수를 입력의 크기에 대한 함수로 표현한다. ex) 크기가 N인 데이터를 순차적으로 비교 한다면 총 비교 횟수는 (N-1)이 되므로 크기가 N인 순차적인 알고리즘의 시간복잡도는 (N-1)이다. 시간복잡도는 표현할때는 3가지의 분석 방법이 주어지는데 1. 최악의 경우 분석 (Worst Case Analysis) 2. 평균의 경우 분석 (Averge C.. 2020. 9. 10. 최초의 알고리즘 가장 오래된 알고리즘은 A.C 300년 전에 만들어진 유클리드의 최대공약수를 찾는 알고리즘으로 알려져 있다. 최대공약수(GCD) : 2개 이상의 자연수들의 공통된 약수중 가장 큰 수 유클리드는 2개의 자연수의 최대공약수를 구하기 위해 큰 수에서 작은 수를 뺀 수 작은수와의 최대공약수는 같다 라는 성질을 이용하여 최대공약수를 찾았다. ex) 24와 14의 최대공약수 (큰수 : 24, 작은수 :14) 큰수 - 작은 수 :: 24 - 14 = 10 > 10과 작은수(14)와의 최대 공약수는 같다 >> 이 과정에서 다시 큰수는 14, 작은수는 10으로 swap되며 소분해 나갈때 0을 제외한 나머지 수가 두 수의 최대 공약수 이다. 최대공약수 ( n, 0 ) = n 2020. 9. 10. 알고리즘이란 알고리즘이라는 이름은 페르시아 수학자인 '알콰리즈미'로부터 유래 되었다고 한다. 이건 별로 기억할 필요는 없고 여러 의미를 가지고 있는것 같은데 내가 생각하는 알고리즘은 문제를 해결하는 단계적인 절차, 또는 방법이라고 생각한다. 여기서 문제를 해결하기 위한 도구는 컴퓨터이며 여기서 입력이 주어지며 알고리즘을 통해 결과를 출력 받는다. 알고리즘의 특성으로는 1. 정확성 > 알고리즘은 주어진 입력에 대하여 올바른 정답만을 도출해 내어야 하며 오답을 뱉을시 이는 알고리즘이라고 할 수 없다. 2. 수행성 > 알고리즘의 각 단계는 코드는 컴파일러에 의하여 기계어로 번역이 가능하며 수행이 되어야 한다. 즉 컴퓨터가 알아먹을 수 있는 언어로 작성되어야 한다는 말이다. 3. 유한성 > 알고리즘은 일정한 시간내에서 종료.. 2020. 9. 10. 이전 1 다음
