해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다. 3-3장 검색 알고리즘 - 천장함수 (2/5) 천장함수 Ceiling Function 천장함수 = 올림 함수, 내림 함수 검색에 필요한 비교 횟수 평균값 : log n회 (이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n이 된다.) 검색 성공 시 : log n - 1회 검색 실패 시 : [log(n + 1)]회 검색 실패 시, 사용한 [ ]은 천장 함수 기호를 나타낸다. [x]는 x의 천장 함수이고, x보다 크거나 같으면서 가장 작은 정수이다. ex) [3.5] = 4 ceil(3.23) = 4 floor(3.23) = 3
해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다. 3-3장 검색 알고리즘 - 이진검색 (1/5) 이진검색 - 데이터의 키 값이 이미 오름차순 / 내림차순으로 정렬(sort)되어있어야 함 - 정렬이 되어있기 때문에 처음, 중간, 끝을 검색하며 범위를 줄여나가면 됨 - 선형 검색보다 좀 더 빠르게 검색할 수 있다. 이진검색 방법 - 찾는 값을 설정한다. (39). - 배열의 중앙에 위치한 요소 a [5] (31)부터 검색 시작 (배열이 오름차순 / 내림차순으로 정렬되어 있기 때문에 찾는 값이 작으면 더 앞으로 가서 검색하고, 찾는 값이 크면 더 뒤로 가서 검색하면 된다.) - 검색하려는 값인 39는 중앙 요소 a [5]보다 큼 - 검색 대상..
해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다. 3-2장 검색 알고리즘 - 선형(순차)검색 | 보초법 검색 선형 검색 linear search / 순차 검색 sequence search - 요소가 직선 모양으로 늘어선 배열 - 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다. 선형 검색에서 배열 검색의 종료조건 2가지 1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패 2. 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공 배열 요수에 따른 검색 수행 횟수 배열의 요소의 개수가 n개일 때 [2️⃣−1️⃣], [2️⃣−2️⃣] 조건을 판단하는 횟수는 평균 n/2회이다. * [2️⃣−1..
해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다. 3-1장 검색 알고리즘 - 검색과 키 그리고 배열 검색 알고리즘이란 - 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 것 검색과 키 검색(searching) 과정 1. 국적이 한국인 사람을 찾는다 2. 나이가 21세 이상 27세 미만인 사람을 찾는다 3. 어떤 낱말과 발음이 가장 비슷한 이름의 사람을 찾는다. 이때 검색의 공통점은 특정 항목에 주목한다는 점이다. 여기서 주목하는 특정 항목을 키(key)라고 한다. 데이터가 단순한 정수값이면 데이터값을 키값이라고 생각해도 좋지만 대부분의 경우에서 키는 데이터의 '일부'이다. 1. 키값과 일치하도록 지정한다. (한국) 2. 키값의 구간을 ..
해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다. 2-1장 기본 자료구조 - 구조체 : -> 연산자 (2/2) -> 연산자 // 포인터이름 -> 멤버이름 (p가 가리키는 객체 안의 멤버 x) p -> x - 포인터 p가 x를 가르킨다. - p가 구조체형 객체에 대한 포인터일 때, p가 가리키는 객체의 멤버 x에 접근하는 형식에 사용