[ 알고리즘 ] 정렬(1) : Selection Sort, Recursive Selection Sort 1. sorting의 조건 정확하게 sorting이 되기 위해서는 아래의 두가지 조건이 성립되어야한다. 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]n−1 일 때 sort 함수가 성공한다고 가정하자. 항상 재귀 실행 전에 a[0]에 최소값이 들어간 후 실행된다. 따라서 재귀로 들어가기 전부터 ∀x((x>0)→(a[0]a[0] 학부 내용 정리/[ 2-2 ] 알고리즘 2022.10.09
[ 알고리즘 ] Binary Search, Recursive Binary Search 1. Binary Search 이진탐색트리 코드이다. l은 왼쪽 끝 ,r은 오른쪽 끝 ,m은 중간이다. 기본 적인 아이디어는 sorting된 배열의 중간을 찾아 크기를 비교해가며 원하는 값을 찾는 것이다. 처음에는 0번째 배열을 l , 마지막 배열을 r로 두고 탐색을 시작한다. 탐색은 l과 r이 만나면 종료된다. m은 l과 r의 중간이고 (l+r)/2 로 두었다. 이게 성립하나를 위해 몇가지 예시를 보겠다. 1) n=2 l=0, r=1, m=0 으로 모두 탐색 가능하고 2) n-3 l=0, r=2, m=1 으로 모두 탐색 가능하다 a[m]과 x를을 비교해서 x가 작다면 왼쪽을 탐색하고 x가 크다면 오른쪽을 탐색하고 x와 같다면 종료된다. 왼쪽 탐색을 위해서는 r을 m의 바로 전 인덱스로 설정되고 오른쪽 .. 학부 내용 정리/[ 2-2 ] 알고리즘 2022.10.03
