깡뇽

- Quick Sort : 빠른 정렬 => Merge Sort처럼 분할 - 정복 - 합병의 분할정복법을 이용함. Ex) 정렬할 배열이 주어졌을 때, 마지막 수를 기준(pivot)으로 삼음 -> 기준보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치(분할:partition)를 함. -> 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬함. => 정렬 완료 - 최악의 경우 항상 한 쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우 이미 정렬된 입력 데이터 ( 마지막 원소를 기준으로 선택하는 경우 ) - 최선의 경우 항상 절반으로 분할 되는 경우 => 분할이 얼마나 되어 있는지에 따라 Quick Sort는 영향을 받음. - 평균시간복잡도 최악의 경우는 매우 극단적인 예이며 대체적인 경우가 존재 - ..

- 분할정복법 : 분할, 정복, 합병을 거치는 방법 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 문제를 순환적으로 해결 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 - Merge Sort : 합병정렬 1. 분할 -> 데이터가 저장된 배열을 절반으로 나눔. (divide) 2. 정렬 -> 각각을 순환적으로 정렬함. (recursively sort) 3. 합병 -> 정렬된 두 개의 배열을 합쳐 전체를 정렬함. (merge) => 합병 과정이 실질적으로 중요함. Ex) A | G | L | O | R 과 H | I | M | S | T 의 정렬된 두 배열이 있을 때, A와 H는 각 배열에서 가장 작은 값이며 두 배열을 하나의 배열로 합병할 때..

- 정렬 Bubble sort, Insertion sort, Selection sort => 상대적으로 단순하고 느림. Quick sort, Merge sort, Heap sort => 상대적으로 빠름. Radix sort - Selection Sort 1. 데이터 중에서 가장 큰 값을 찾고 마지막 자리의 값과 위치를 바꿈. => 가장 큰 값이 마지막 위치를 갖게 됨. 2. 가장 큰 값을 제외하고 남아 있는 데이터 중에서 가장 큰 값을 찾고 마지막 자리의 값과 위치를 바꿈. 이때, 정렬하고자 하는 데이터 중에 가장 큰 값이 마지막 자리에 있는 경우 그 위치에 그대로 둠. 3. 2번을 반복함. 2개의 데이터가 남을 때까지 반복한 후 그 둘 중 큰 값을 뒷자리로 보냄. 정렬은 완료됨. Ex) 배열 A[1....

=> Recursive Thinking : 현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 - 미로 찾기 예시 Decision Problem(답이 yes 또는 no인 문제)으로 전환 Ex) boolean findPath ( x, y ) if ( x, y ) is the exit return true; else for each neighbouring cell ( x', y' ) of ( x, y ) do if ( x', y' ) is on the pathway if findPath ( x' , y' ) return true; return false; => 무한루프에 빠지..

- 순환적 알고리즘 설계 적어도 하나의 Base case가 있어야 함. 즉, 순환되지 않고 종료되는 case가 있어야 함. 모든 case는 결국 base case로 수렴해야 함. & 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔야 함. Ex) 순차 탐색 : 배열의 데이터들이 저장되어 있을 때 내가 원하는 데이터가 존재하는지 어디에 있는지 찾는 것 => 시작점을 암시적으로 표현할 수도 있고 시작점과 끝점을 모두 명시적으로 지정할 수도 있음 ① 맨 앞부터 검색, ② 맨 뒤부터 검색, ③ 중간 값을 검색 ( 이진 검색과 다름 ) Ex) 최대값 찾기 Ex) 이진 검색 : 데이터가 크기 순으로 정렬되어 있을 때 사용할 수 있는 검색 방법

수학함수 계산, 문자열의 길이 계산, 문자열의 프린트, 문자열을 뒤집어 프린트, 2진수로 변환하여 출력, 배열의 합 구하기, 데이터파일로 부터 n개의 정수 읽어오기 등이 가능 - 모든 순환함수는 반복문으로 변경 가능하며 반대로 모든 반복문은 순환함수로 표현 가능 - 복잡한 알고리즘을 단순하고 쉽게 표현하는 것을 가능하게 함 - 함수 호출에 따라 overhead가 있음

- 순환 (recursion) : 자기 자신을 호출하는 함수. 재귀함수. => 무한루프에 빠지는 경우가 있음. ① Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함. ② Recursive case : recursion을 반복하다보면 결국 Base case로 수렴해야 함. 위 2가지 요구사항을 충족하면 무한루프에 빠지지 않음. 순환함수는 수학적귀납법으로 증명 가능함. Ex) Factorial : n! 을 순환함수로 만들어보자 public static int factorial ( int n ) { if ( n == 0 ) return 1 ; else return n * factorial ( n - 1 ) ; } => 수학적귀납법 증명 1. n = 0인 경우에 1을 반환하..

- 시간복잡도 : 실행시간은 하드웨어, 운영체제 등과 같은 실행환경에 따라 달리질 수 있기 때문에 실행 시간을 측정하는 대신 연산의 실행 횟수를 측정함. 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 가능. - 점근적 분석 : 데이터의 개수 n→∞일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현 하는 기법. 상대적으로 가장 간단하며 알고리즘의 실행환경에 비의존적이기 때문에 광범위하게 사용될 뿐임. - 이진검색 : 정렬된 데이터의 중간값을 비교해 나가는 방식이기 때문에 한 번 비교할 때마다 남아있는 데이터가 절반으로 줄어듬. 즉, 시간복잡도는 O(log2n)임. => 순차검색의 시간복잡도는 O(n)이고 이진검색은 O(log2n)이며 둘의 차이는 매우 큼. ① 버블 정렬 ② 삽입..