[정보처리] 데이터베이스 - 자료구조3

https://youtu.be/BoaTeMlcD2s

1. 데이터 검색 방법 및 알고리즘 이해

1-1. 데이터 검색의 기본 이해
-  '데이터 검색'이라는 용어에 대한 이해함 (전자기기에서 정보를 찾아내는 것)
-  일반적인 데이터 검색(선형)과 선택사항에 대해 이해하는 것이 중요함
-  내부 검색과 외부 검색을 소개하며 어떤 상황에서 각각 사용되는지를 알아봄
- (중요) 기본적인 검색 알고리즘 형태와 이에 필요한 키를 배움

1-2. 선형 검색의 활용과 이해
- (중요) 선형 검색이란 모든 가능한 값을 모두 검색하는 방법임
-  해당 검색 방법은 일반적으로 효과적이며 비교 횟수가 적은 점이 특징임
-  하지만 처리 속도가 느림, 큰 데이터 처리가 불편함 등 단점이 존재함
-  선형 검색의 대표적인 알고리즘으로 헤싱을 소개함

1-3. 기타 검색 알고리즘들과 이해
-  다양한 종류의 검색 알고리즘들을 알아보고 이를 활용하는 방법을 이해함
-  제어 검색과 비선형 검색을 중심으로 세부적으로 설명함
- (중요) 각 검색 알고리즘들의 특성과 사용 상황을 알아볼 필요가 있음
-  강좌 내에서는 주요한 내용들에 대해서만 집중해 설명하였으며 중요한 부분에 대해서 추가적으로 강조하였음

2. 평균 검색과 피보나치 검색

2-1. 평균 검색 이해
-  '첫 번째 데이터'라는 용어 사용이란 검색할 목록이나 순위 목록을 의미함
- (중요) 평균 검색이란 특정 항목(키)의 가운데 절반에 해당하는 값을 찾아가는 검색 방법임
-  중간값을 먼저 찾고, 그 값을 기준으로 다른 데이터와 비교하여 동일하거나 다른지를 판단함
- (중요) 검색 대상을 찾았다면, 검색 결과가 동일하다면 검색 종료

2-2. 피보나치 검색 이해
-  피보나치 수열이라는 수열 패턴을 사용하여 평균 검색 문제 해결이 가능함
-  입력된 데이터를 더하거나 뺀 각각의 결과들을 통해 최종 목록을 만들어냄
-  본래 검색 알고리즘은 중간값을 직접 구하는데, 이를 피보나치 수열을 이용하여 구하게 변경됨
-  따라서 피보나치 검색은 중간값 구하기 없이 최종 목록을 만들어낼 수 있음

2-3. 피보나치 검색의 장점 및 활용
-  피보나치 검색은 2분 검색에 비해 명확한 경로를 제공하며, 비효율적 요소를 최소화 함
- (중요) 또한 원본 데이터의 변조를 덜 요구하며, 동일성 확인 과정이 상대적으로 단순함
-  따라서 시간복잡도가 낮으며, 특히 큰 규칙을 처리할 때 유용하게 활용될 수 있음
- (중요) 중요한 것은 검색 대상이 여러 개일때, 모든 데이터를 모두 검색해야 하므로 전체 공간을 차지하는 문제가 있음

3. 피보나치 수열과 알고리즘 이해

3-1. 피보나치 수열의 기본 이해와 활용
- (중요) 피보나치 수열이란 어떤 숫자 집합에서 모든 항목이 차례대로 더되는 형태의 수열을 의미함
-  이러한 특성을 활용하여 데이터를 탐색할 때는 피보나치 추리 이용
-  해당 추리의 계산 및 검색 시간이 상대적으로 빠름
-  피보나치 추리 사용 시 복잡하지만, 효율성이 좋음

3-2. 피보나치 추리에 대한 설명
-  피보나치 추리는 피보나치 수열의 원리를 통해 작건의 위치를 확인하는 방법임
- (중요) 이 추리에서는 중심좌측의 값을 기준으로 한 좌표가 오른쪽으로 움직이는 것을 이용함
-  결과는 중심 좌측의 값에서 '피보나치 수열'로 인한 변화를 구하여 정렬됨
-  찾는 작업이 일종의 연결 검색으로 진행되어 효율성이 좋음

3-3. 피보나치 추리와 검색 알고리즘 간 관계
-  피보나치 추리는 검색 알고리즘이 뚜렷하게 유용한 이유 중 하나임
-  찾고자 하는 데이터를 찾는 경우에는 선형 검색처럼 특정 단계를 수행 후 추가적인 검색이 필요 없는 경우가 많음
- (중요) 피보나치 추리 역시 이런 상황에서도 적용 가능하며, 이로 인해 효과적인 검색이 가능해짐
-  따라서 피보나치 추리는 검색 알고리즘 개발에도 도움이 될 수 있음을 알 수 있음

4. 제어 검색과 블록 검색

4-1. 보완 검색과 기초 이해
-  '보고', '백색', '피보나치' 등의 형태된 검색 메커니즘 소개함
-  예를 들어, '파드'에 대한 검색은 '파드(경제)'라는 입력부터 시작해 관련된 모든 파드를 찾아가는 방식을 사용함
-  이를 위해 총합 검색, 반복 검색 등 다양한 기법들을 이용해 복잡한 입력문장을 처리 가능함
- (중요) 검색 메커니즘이란 어떤 문장을 입력받아 특정 정보를 찾거나 검색결정보다 일부 정보만을 선택적으로 제공하는 방식임

4-2. 선형 및 보완 검색
-  여러 검색 방식 중 선형 검색과 보완 검색에 대해 설명함
-  선형 검색은 시간적 순서에 따라 진행되는 방식이며, 크거나 데이터 양이 커질수록 효율성이 감소함
-  보완 검색은 기본적인 검색 속도가 갖춰졌으면, 추가로 입력의 잘못을 보완해 나가는 방식임
-  이를 통해 발전된 데이터 정렬 능력 및 신뢰성을 획득하면서도 초기 검색 비용이나 전체 데이터 양은 유지할 수 있게됨

4-3. 블록 검색
-  블록 검색이라는 방식에 대해 소개함
-  여기서 말하는 블록은 일련의 숫자나 문자열 등을 의미하며, 그 사이에 다른 것을 검색하는 방식을 설명함
- (중요) 이때 블록의 수는 일반적으로 크게 두 가지로 나뉘며, 사용자는 적절한 수를 고려하여 선택하게 됨
-  또한, 각 블록 내에서 가장 큰 값이 포함되어 있는 인덱스를 저장하게 됨

5. 이진 및 추리검색 이해하기

5-1. 이진 검색 알고리즘 소개
- (중요) 인덱스 테이블 이용하여 원하는 데이터 찾아내는 이진 검색 알고리즘이 존재함
-  데이터의 개수가 많을 때 뒤섞인 상태를 효율적으로 관리하며 검색 수행 가능
-  특정 데이터 값이 묶여있는 부분 먼저 검색하고, 다른 부분은 별도로 검색함
-  라이브러리의 각 항목을 순차적으로 검색하면서 데이터를 찾아냄

5-2. 이진 검색 사례와 공식
-  인덱스 테이블 작성 시, 데이타 구조가 자연스럽게 분류되도록 함
-  복잡한 리스트에서 필요한 데이터 값을 찾을때 위와 같이 이진 형태로 만듦
- (중요) 선정 검색이 아닌 이진 검색 사용 시, 전체 데이터를 차례대로 검색하게 됨
-  데이터의 일부를 선택해서 검색하는 것으로 더욱 효율적임

5-3. 이진 추리 검색 이해
-  이진 추리 검색은 입력된 데이터를 이진 추리로 만들어 이후 검색하는 방법임
-  이 추리 과정에서 복잡한 데이터 구조를 직관적으로 나타낼 수 있음
- (중요) 원하는 데이터값을 찾아낼 때, 작은 값부터 시작해서 매개변수의 범위를 점점 확대하면서 검색 진행
-  만약 일정 조건 이상의 데이터값이 존재한다면, 이진 추리의 한 조건을 충족시키지 못한다는 것 의미

6. 데이터 검색 및 해싱 방법론 소개

6-1. 다양한 검색 방법론의 설명
-  선형 검색, 등간 검색, 비선형 검색, 피보나치 검색 등을 포함한 다양한 검색 방법론을 소개함
- (중요) 이들 방법론이란 복잡한 데이터 집단 속에서 특정 데이터를 찾거나 검색하기 위한 다양한 방법인 것을 강조함
-  데이터의 특성에 따라 적합한 선택법이나 어떤 방법론을 사용해야 할 지 결정하는데 도움이 될 수 있음
-  이러한 다양한 접근법을 이해하면 복잡한 데이터 세트를 더 효율적으로 활용할 수 있다는 점을 명시함

6-2. 해싱 검색에 대한 설명
-  해싱이라는 개념과 필요성을 다룸
-  해싱이란 데이터의 주소를 해싱 함수를 통해 생성하는 과정이며 이를 통해 주소 저장에 용이함을 언급함
- (중요) 해싱을 통한 주소 생성은 아이디어 삽입 및 원하는 객체를 신속하게 찾는 것이 가능해짐을 강조함
-  주소생성에서 '재산법', '평편계법', '대수적코딩법' 등의 방법론이 유용하며, 이러한 방법론들의 적용을 통해 이더이 서열이 중요함을 보여줌

6-3. 해싱 검색 방식 설명
-  해싱이 된 주소는 어떻게 검색되는지 설명함
- (중요) '헤싱테이블'은 저장된 해싱 주소와 관련된 테이블로서, 동일 주소를 갖는 다른 주소는 차감됨을 강조함
-  동일 주소(올바르게라 부터 처음 찾는다 생각하면 됐다)를 검색할 때 충돌 현상을 방지하기 위해 오버풀로우 예외 처리 필요성을 언급함
-  대비적 주소를 이용한 해싱과 해당 주소 계산에 있어서 '핵심적인 소스 팁'(인덱스 소스 팁)으로 확인하도록 함

화자 1
00:10
자 전국에 계시는 우리 M2N 생방송 안방 가족 여러분 계속해서 뜨거운 가슴으로 감동의 수업을 함께 하겠습니다. 아 예 좋습니다. 여러분들 자 10분 정도 쉬었죠. 예 아유 좀 시원하게 목이 더 잡히네요. 그죠 여름 이 허스키한 이 목소리도 아주 좋은 날 그죠 에 두사부일체 예 여러분을 위하여 날마다 달려갑니다. 예 생중계 그죠 완벽 속성으로 그래서 우리가 앞 시간에 이제 우리가 그 자료 구조 이제 우리가 정리를 했지 크게 선형 구조 정리했고 또 바로 앞 시간에 비선형 구조 이제 추리 개념하고 그래프하고 보죠. 그래서 앞 시간에 정리한 거 어떤 문제도 빠져나갈 수 없는 거 부처님 손바닥 제재지 손바닥 됐나 그래서 고거 정리를 하고요.

화자 1
01:01
자 지금 뭐냐면 방금 우리가 이제 관계 관련 있는 데이터들 노드들 정점들 그죠 여러 데이타 리스트를 만들어 놨잖아요. 그 리스트에서 지금부터 뭐다 특정 데이터를 찾는 작업 검색과 그다음에 이 리스트의 데이터를 어떤 키를 기준으로 정렬 정렬정렬자로 정리하여 우러정렬 김정열 예 정렬하는 작업 이게 자료 구조 투다 그죠 그래서 우선은 요번 시간에는 검색 작업 그죠 특정 리스트에 들어있는 데이터를 어떤 식으로 검색하느냐 컴퓨터에서 제공하는 검색 방법들만 알면 되는 거겠지 그죠 좋습니다. 한번 들어가 봅니다. 예 야 자료구조 3이 되겠네 자 검색 설칭이 나왔죠 설칭 셀칭 스트레칭 검색 그래서 검색의 정의는 더 이상 안 써도 되겠죠.

화자 1
01:54
이제 우리 앞에서 배운 선형 리스트나 비선형 리스트 그 리스트 안에 들어있는 특정 데이터를 찾는 방법 찾는 작업을 검색이다. 그죠 예 리스트 속에 에 리스트 속에 내가 찾고자 하는 특정 데이터 특정 데이터 특정 노드 특정 원소 특정 요소 특정 증점 다 같은 말이다. 특등 말 발언도 잘 안 된다. 리스트 속에 특정 데이터를 찾는 작업이죠. 찾는 작업 요걸 검색이라 하는데 이 검색 방법 검색 알고리즘은 크게 내부검색과 외부 검색이 있더라고요. 전체를 다 보고 하면 들어간다 그죠 자 내부 검색은 뭐냐 하면 주기억장치 안에 들어있는 리스트 속에서 찾는 거죠. 주기억장치 그리고 외부검색은 보조 기억장치 테이프나 디스크에서 찾는 거죠. 테이프나 디스크인데 이 검색은요, 에 내부 검색과 외부검색이 검색 작업이 동일합니다. 방법은 검색방법은 동일하다 이 말입니다.

화자 1
02:53
그죠 방법은 동일하기 때문에 내부 검색을 가지고 이야기 하면 돼요. 내부검색을 배운 걸 그대로 외부검색의 포팅에 적용시키면 됩니다. 좋습니다. 그러니까 이 검색 방법은 에 검색 장소에 의해서는 내부와 외부로 나누고요. 검색 방법은 크게 뭐다 비교검색 특정 찾고자 하는 데이터를 일일이 비교하는 컴페리즘 매스트 비교법이 있고 이제 비교를 하지 않는 난 컴페리즘 매스트 2가지 방법이 있는 거야. 알겠나 자 이 비교 방법에는 크게 또 선형 검색 순차 검색이 있고 그다음에 어떤 기준을 둔 제어검색이 있어요. 이 제어검색은 또 2분 검색이 있고 피보나치 검색이 있고 보관 보관이 아니고 인터폴레이션 보관 검색이죠. 보관 들렸네요.

화자 1
03:42
보관검색 그다음에 블락 검색 추리검색 있고 그죠 그다음에 비교하지 않는 키의 계수적 성질을 이용해 가지고 한방에 찾아가는 뭐 헤싱 직접 건색법이 있습니다. 그래서 오늘날 컴퓨터에서 특정 어떤 집단 리스트 어떤 메모리 속에 들어있는 데이터를 찾는 작업 이게 다야 이것 중의 하나를 가지고 내가 프로그래밍해서 데이터를 찾아간다 이 말입니다. 알겠나 다시 해보자 선연검색 비교 검색에는 선연검색 제어 검색에는 2분 검색 피보나처 검색 보관검색 블락 검색 추리검색 그다음에 직접 검색법인 헤싱 1234 5~67개 7개의 알고리즘이 데이터를 찾는 거죠. 그죠 이 중에 하나를 적용시켜서 프로그래밍하면은 그 프로그램에 의해서 컴퓨터는 갭싸게 여러분이 식힌 방법에 의해서 데이타를 찾아간다는 말씀 알겠나 좋습니다.

화자 1
04:38
그죠 그래서 이제 각각을 하나씩 하나씩 보자 이 말입니다. 그죠 스위치 특정 니스 속의 데이터를 찾는 작업이다. 예 좋아요. 음 좋습니다. 자 제일 먼저 아주 쉬워요 그냥 가벼운 마음으로 따라오면 된다. 선정검색 미니어 설치 다른 말로 순차 검색이란 얘기죠 말 그대로 가장 단순한 검색이다. 단순하기 때문에 효율성은 좀 떨어지고 또 검색 시간이 많이 걸립니다. 그죠 이 설명검색은 어떻게 하느냐 데이터를 하나하나 차례대로 검색하는 거예요. 그래서 일명 순차검색이라 한다. 순차검색 같은 말이다. 이 말입니다. 예를 들면 니스트 속에 이제 리스트의 이름을 붙이면 파일이겠죠. 자 이게 하나의 리스트의 집단이다. 그래서 이거는 뭐 리스트 해도 되고 리스트 이름을 붙인 게 이제 파일이겠죠. 그죠 이 파일 속에 첫 번째 파일 첫 번째 데이터 이 말이다. 첫 번째 네코드 첫 번째 데이터 뭐 에프 원 에프 투 에프스 엔계가 있다.

화자 1
05:36
그죠 어 그럼 내가 찾고자 하는 걸 FK라 하자 이러면은 일일이 뭡니까? 비교하는 겁니다. 니가 에프케이가 에프케이가 니가 에프케이 이렇게 다 묻는 거예요. 그러니까 우리 정보처리 기사실 만약에 수업 듣는 학생이 60명이라면은 내가 여기서 60명 중에 어 홍길동이를 찾는다 카면 첫 번째 학생부터 니 홍길동이가 이러면 아니네 홍길동 홍길동 홍길동 홍길동 이렇게 찾아가는 거예요. 아주 다수 무식한 것이야 그래서 홍길동입니다. 하면 찾았네 이런 게 뭐다 순차 검색입니다. 알겠나 그럼 예를 들면은 이런 거다 이 말이야. 자 특정 리스트 속에 어 파일 속의 데이터가 1 2 3 4 5 뭐 5개가 있단 말이에요. 그럼 내가 찾고자 하는 데이터를 FK를 했을 때 나는 4를 찾고 싶다. 함 어떻게 잡는다. 첫 번째 데이터부터 이 리스트 속에 첫 번째 원소 요소 네코드 데이터를 물어요. 니가 사과 아니네 니가 4가 4가 아사하네 찾습니다.

화자 1
06:30
그죠 요런 아주 단순 무식하게 데이터를 설치하는 작업이 뭐다 선형 검색이죠. 뭐 이 선형 검색은요, 더 베스트 제일 최선 기분 좋으면 1번만에 완성할 수 있어 왜 내가 찾고 있는 데이터 처음에 딱 있으면 완성이에요. 근데 처양 제일 더러운 경우는 뭡니까? 마지막 데이터까지 찾을 경우가 있제 아니야. 나 끝까지 다 검색하는 경우가 발생합니다. 예를 들면 홍길동이가 첫 번째 앉아 있으면 1번만에 찾지만 홍길동이가 제일 끝에 앉아 있으면 마지막까지 다 검색해서 찾아야 되는 거 엔번까지 수행을 해야 되겠죠. 알겠나 그래서 인제 평균 이 선정검색은 평균 비교 횟수는 뭐야? 평균 2분의 엔 플러스 3분의 검색 시간이 걸리는 거죠. 많이 걸리는 거다 어 특정 데이터를 찾기 위해서 평균 2분의 그 리스트의 총 데이터 개수 엔 플러스 1번만큼 찾아야 되니까. 예 그래서 선전검사 가장 단순하지만 효율이 떨어지고 검색 시간이 많이 걸리는 거예요. 그죠 가장 빠르게 정확하게 찾는 게 따봉 아니야.

화자 1
07:30
어 그런 데 비해서 선전 검색은 비효율적이다. 이런 이야기입니다. 그렇지만 알고리즘이 너무나도 안 돼 이거 프로그램 짜면 장난이죠. 내가 찾고자 하는 데이터를 정의해 두고 그다음에 일일이 예 비교하면 되는 거죠. 그러니까 이 프로그램 짜기가 너무나 쉬운 거예요. 그죠 그래서 단순하면은 뭐든지 단순하면 안 좋잖아요. 그죠 그러니까 알고리즘이 복잡하면은 이 수행 속도가 빠른 겁니다. 되겠나 그렇게 정리하면 되고요. 선전검색 별로 공부할 게 없다. 됐죠 그 다음에 두 번째 이제 2분 검색이다. 그죠 자 2분검색 피보 나치 검색 보강검색은 제어검색이다. 그러죠 이 제어검색들은 제어 검색은요, 어떤 조건이 있느냐 하면 반드시 데이터가 정렬돼 있어야 됩니다. 정렬 에 반드시 순차적으로 데이터가 쫙 돼있어야 된다는 거지 뒤죽박죽 섞여있으면 이 제어검색은 적용하기가 힘들다 이 말이야.

화자 1
08:27
그래서 이런 제어검색에 첫 번째 이게 뭐가 2분 검색이 표준검색이죠. 제어검색에 스탠다드나 뭐가 2분 검색이 자 2분 검색은 뭐야? 말 그대로 반드시 정렬된 파일에서 전체의 파일을 2분 즉 반으로 나누어 가면서 검색하는 게 2분검색이 아닙니다. 반 나가라 예 이게 뭔 말이냐 이 말이에요. 자 이분 검색 자 이거 내가 인제 하나의 파일이다. 하나의 리스트라고 하죠. 첫 번째 데이터 첫 번째 레코드 같은 말입니다. 표현을 이래 놨어요. 첫 번째 데이터 두 번째 데이타 요 중간값 중간 데이터를 FN으로 해서 이게 FM이죠. FM 에프엠 또는 엠 에프엠이에요. 에프엠 중간 미디움 에 에프엠이면은 요 앞에 이건 잘못됐다. 요거는 에퍼 엠 마이너스 1번째고 요거는 뭐다 에퍼 엠 플러스 1번째 되겠죠. 엔을 엠으로 다 바꾸세요. 그리고 에프엠 마지막 데이터가 있겠죠. 그러면 이 전체를 우선은 뭐야? 반으로 쪼개는 거예요.

화자 1
09:25
중간값을 찾죠 중간값 그니까 2분 검색 한마디로 여기 이거 중간 값을 찾아라 시험에 중간값 나오면 무조건 뭐 2분 검색이야 중간 값을 구합니다. 중간값을 이제 우리가 FM 또는 내가 엠으로 해도 좋습니다. 미디어 홈 이 중간값을 구해 가지고 이 중간값과 비교하는 거예요. 중간값 그러니까 아까 선정 검색은 어떻다 내가 찾고자 하는 데이터하고 일일이 처음부터 비교했지 왜냐면, 중간 값을 딱 쪼개서 막 검색하는 거예요. 반씩 줄여가며 하는 겁니다. 그래서 인제 내가 찾고자 하는 데이터가 FK고 내가 찾고자 하는 데이터구요. 이 엠은 이제 중간값이라서 중간값 중간값 여기 쓰는 FM이겠죠. FM 이 중앙값을 구해 가지고 그럼 중앙값은 어떻게 구하냐? 중간값 엠 즉 뭐 에프엠 좋죠. 이 중앙값을 어떻게 구하느냐 2분의 첫 번째 데이타 더하기 마지막 데이타 그죠 2분의 예를 들면 첫 번째 데이타 더하기 레스트 데이타 이렇게 해도 되겠죠. 요렇게 하면 중앙 값이 나오겠죠. 중간값에 위치 값이죠.

화자 1
10:23
중간 값을 구해 가지고 그럼 이 FM을 즉 M을 구해 가지고 내가 찾고자 하는 데이터와 내가 방금 구한 중간값 엠을 비교하는 거예요. 비교하면은 3가지 경우가 발생하겠지 뭐 어떤 경우 내가 찾고자 하는 키 값이 중간값보다 적은 경우가 있는 거예요. 그러면 내가 찾고자 하는 데이터가 중간값보다 적다는 거는 뭐고 내가 찾고 있는 데이터 어디 있단 말은 요 속에 들어있다. 요 속에 들어있다는 거고, 맞나 또 두 번째 경우는 뭐다 내가 찾고자 하는 데이터가 중간과보다 크다 카는 경우 내가 찾고자 하는 데이터 어디 있다. 요 속에 들어있죠. 요 속에 맞나 맞아요. 즉 내가 찾고자 하는 데이터가 중간값보다 적다는 경우는 그 데이터는 내가 찾고 어디 있다. 에프와 첫 번째 데이터에서 중간값 즉 엠 마이너스 1번까지 FM 마이너스 1번째 사이 존재한다는 거예요. 아니면 두 번째 이런 경우 즉 내가 찾고자 하는 데이터가 엠보다 크닥 하는 경우는 중간값 바로 다음 이 에프 엠 플러스 1 또는 또 엠 플러스 1에서 마지막 데이터 사이 존재한다는 거야.

화자 1
11:22
여기가 존재한다면, 여기에 두 번째 여기 존재하고 첫 번째 같은 경우는 여기가 존재한다는 거예요. 맞나 그리고 세 번째는 뭡니까? 아 내가 찾고자 하는 데이터와 이 중간 갑하고 같아야만요 찾고자 하는 데이터 찾았다. 검색 완료 검색 완료 조건 뭐다 찾고자 하는 키 FK하고 중간 갑의 같은 경우는 작업을 중단합니다. 검색 완료 즉 검색이 완료됐기 때문에 작업을 중단합니다. 컴퓨터는 되겠나 됐습니까? 이렇게 하는 거예요. 자 백문이 불여일견인 한번 보자 이 말이야. 만약에 데이터가 자 리스트 속에 이렇게 1에서 10까지 데이터가 있어요. 어 그러면 여러분들 내가 찾고자 하는 데이터는 8이에요. 8 그럼 선정 검색은 몇 분 검색하노 몇 번 한번 8번 만에 찾아내죠 선정검색어 2분 검색은 뭡니까? 바로 이 리스트에서 중간값을 찾거든. 중간값 어떻게 찾는다 한번 봐봐 중간값 2분의 첫 번째 데이타 1 더하기 10이죠. 에 그러면 뭡니까? 2분의 11이죠.

화자 1
12:21
2분의 11 2분의 11이야 그럼 2분의 11은 5.5니까 보통 이것도 가소함수 취해서 오를 중앙값으로 잡아주면 돼요. 그러면 다섯 번째가 뭐다 다섯 번째가 중앙값이에요. 중앙값 어 맞나 그럼 내가 이제 중앙값 엠은 오고요. 내가 찾고자 하는 키 키 값은 뭐다 8이야 그럼 비교를 해보는 거야. 그러면 아 5가 8보다 적으니까 내가 찾고자 하는 데이터 어디에 존재한다. 오케이 6에서 어디 존재한다. 6 7 8 9 10 이 안에 존재한다는 거야. 알겠나 그럼 요걸 또 하나의 파일로 보고 여기서 또 중간값을 구하면 2차 중간값으로 가봐요. 1차 중간값이고 2차 중앙값을 구하면 중앙값 어떻게 구한다. 에 에 중앙값 어떻게 2분의 내가 찾고자 하는 데이타 인덱스 값입니다. 인덱스 값 요게 첫 번째고 요게 마지막이죠. 에 12345니까 1 플러스 5니까 몇 번째 인덱스 값을 매겨줘야 돼 이 6 더하기 10 하면 안 되고 그럼 뭐냐 2분의 6이니까.

화자 1
13:20
몇 번째 있는 세 번째 있는 게 중간값입니다. 2차 중간값 찾아보니까 8이에요. 8이고 내가 찾고자 하는 데이터가 8이니까. 아 똑같다 찾았다. 몇 번 만에 찾노 1번 작업하고 2번 작업만에 검색을 중단합니다. 아 맞나 선명 검색으로 하니까요? 8번 검색해야 되는 게 방금 2분 검색으로 검색하니까 몇 분 만에 작업 끝 2분만에 찾아 버립니다. 아 좋죠. 효율성이 좋죠. 얘들아 병태야 2분 검색 그죠 반씩 줄여가면서 즉 중간값을 찾는 거죠. 그렇죠. 그래서 1차 중간값 찾으니까 이런 경우가 나온다 그러면은 이 안에 존재한다는 거죠. 그래서 2분만의 검색이 완료되는 거 알겠나 시험에 여러분들 중간값 나오면 뭐다 이분검색 예 시험은 이 정도밖에 안 나와 그렇죠. 우리는 다 한번 구해보자는 거예요. 그죠 됐나 아주 쉬운가 자 요런 검색이 되었고요.

화자 1
14:18
그다음에 이제 요런 2분 검색을 2분 검색을 개선한 게 하나 했어요. 피보나치 검색이에요. 피보나치 스트레칭 피보나치 사람 이름이다. 이 피보나치 검색은 뭐냐 하면은 이 피보나치 수열 카는 게 있습니다. 우리가 수열 배웠잖아. 학교 다닐 때 아 중학교 고등학교 때 그죠 수열 계차수열 등비수열 등차수열 이랬는데 그중에 이 피보나치 수역 하는 게 있어요. 피보나치 수역 어 이거 안 들어봤나 안 들어 봤다고 뭐 니가 지금 수학 안 배웠어요. 시간만 있으면 내가 수학 이야기를 하는데 지금 몇 분 몇 분쯤 지났나요? 너무 지났어요. 그 이후에 환상적인 이야기를 됐습니다. 다음에 좀 이 피보나치 수율이 있는데, 피보나치 수율은 뭐냐 피보나치 수율의 원리를 이용해서 이 피보나치 검색은 피보나치 추리를 생성한 후 검색하는 겁니다. 그래서 이분 검색을 개선했고요.

화자 1
15:14
왜 개선했느냐 뒤에 보겠지만, 2분검색에서는 뭐가 있느냐 중간값을 구하기 위해서 반드시 무슨 연산 하오 나누셈 연산을 해야죠 나누셈이 필요하지만 이 나눔셈은 이제 컴퓨터에 부하를 좀 주는 거지 더하기 빼기보다는 근데 이 피보나치 검색은 나눔셈 역사용 하지 않고 똑같은 효율이 되는데 무슨 가감산만을 이용하기 때문에 효율이 피보나치보다는 저 2분 검색보다는 좋은 거예요. 그러니까 2분 검색을 개선했는 게 피보나치죠 그죠 왜 나누셈을 하지 않고 더하기 빼기로만 어 하는 거예요. 한번 보자 이 말이에요. 피보나치 수율이 뭐냐 하면 이런 거예요. 피보나치 수율은 현재항 현재항을 어떻게 만들었냐 하면은 현재양 전전항 더하기 현재항 전항을 하는 거예요. 예를 들면은 이가 현장이죠. 현장을 어떻게 만드노 FA는 FA 마이너스 2 더하기 FA 다입니다. FA 마이너스 1입니다. 그죠 8은 어떻게 만드나 8은 에프에이는 에프A- 2 더하기 에프A- 1입니다. 그렇죠.

화자 1
16:12
그러니까 1하고 1하고 더해 가지고 2가 되고 1하고 2하고 더해서 3이 되고 3하고 2하고 더해 가지고 5가 되고 5하고 3이 돼서 8이 되고 5하고 8에서 14 이렇게 지나 나가는 거예요. 어 8하고 13하고 더 가서 뭐 21이 되고 요렇게 더 해 가지고 얼마 어렵나 그다음부터 뭐 하겠다. 34 뭐 이래 나가겠죠. 이게 바로 피보나치 수율의 수열의 기본입니다. 어 알겠나 피보나치 에프엔 현지 양은 현지항 전전항 더하기 현재항 전항으로 되겠나 요런 게 바보로 피보나치 수열인데 이 어 좋아요. 이 피보나치 수요를 이용해 가지고 데이터를 찾아가는 거예요. 그죠 그럼 이 피보나치 추리를 생성합니다. 피보나치 추리를 만들어내 가지고 이 피보나치 추리에서 데이터를 찾는 작업이에요. 알고리즘은 복잡합니다. 그죠 피보나치 추리를 막 만들어내야 되기 때문에 그렇지만 복잡지만 검색 시간이 빠르고 효율성은 좋다는 겁니다. 그죠 만약에 에 한번 봐봐요.

화자 1
17:09
예를 들면 내가 자연수를 자 이런 데이터가 들어있는 거야. 이걸 이제 피보나치 검색으로 찾는다 그죠 찾고자 하는 데이타가 18이다. 이런 경우 한번 봅시다 아 그래서 뭐 이거는 여기까지 알 필요는 없지만, 한번 보자 이 말입니다. 그냥 재미로 봐요. 재미로 과거에는 문제가 많이 나왔는데 여기까지 깊이 있게 나오진 않을 거지만 함 보자 다음 장 봅시다 예 자 방금 이제 그 데이터를 내가 인제 자연수를 처리하는 거죠. 첫 번째 1 1 2 3 5 8 13 뭐 21 여기까지 합시다.

화자 1
17:50
어 이게 리스트에 들어있는 거요 어 아 아니지 아니지 인자 데이타 뭐 보기가 어떻게 되나 그거 아까 요 추억 이제 이거 데이터 자연수를 좀 찾아봐야 돼 데이터 1234 56 789 2개가 18 19 20 그죠 총 N이 니트 속에 총 데이터의 개수가 20개입니다. 자연수다 그죠 이 중에서 내가 찾고자 하는 데이타를 FK라 했을 때 내가 18이라는 데이터를 찾고 싶다. 했을 때 이놈을 이제 우리가 뭐로 찾을 수 있나 선연 검색어를 찾을 수 있죠. 선연검색으로 하면 몇 분 만에 찾나 18번 검색해야 돼요. 어 인제 2진검색 2분 검색은 뭐고 반씩 줄여 가기 때문에 한 3번 4번 만에 찾겠죠. 반씩 줄여 가죠 반씩 한 3분 만에 찾겠네 대충 보면은 그럼 이걸 피보라치 검색으로 함 찾아보자 이 말입니다. 그러면은 피보나치 검색은 뭡니까? 우선 이 데이터들을 뭐 피보나치 수열의 원리 수열의 원리를 이용해서 뭘 만든다.

화자 1
18:49
오케이 피보나치 추리를 생성하죠. 피보나치 추리 이게 바로 피보나치 추리입니다. 어 이 피보나치 추리의 원리는 이거지 이런 식이에요. 이렇게 가는 거예요. 에 자 그러면은 이제 어떻게 하냐? 자 이걸 한번 보도록 합시다. 처음에 이제 1 됐고 1 더하기 2 해가지고 3이 되고요. 3 더하기 5 뭐 이렇게 5 더하기 8 이래 가는데 자 봐 봐 자 3에서 5가 할 때 빠진 게 뭐예요? 4죠 빠졌제 빠지면은 뭡니까? 자 피바나 추리는 중심 작은 건 왼쪽 큰 거는 오른쪽 원리로 들어갑니다. 그러니까 4는 3보다 크니까 3의 왼쪽이고 5로 봤을 땐 5보다 적으니까 5 왼쪽 있어야 됩니다. 그렇지 3 4 5고 5에서 8 만들었죠. 8 그다음에 13 만들어 놓고 5하고 8 사이에 빠진 게 뭐가 67이 빠져있죠. 6 그 6은 뭡니까? 5보다는 크고 8보다는 적습니다. 그림이 좁아서 8보다는 좀 적어요. 그러니까 5의 오른쪽 팔의 왼쪽에 붙여야 됩니다.

화자 1
19:44
그죠 그럼 이제 어떻게 붙이느냐 어떻게 붙이느냐 보면은 예, 예 이게 좀 잘못됐네 그림이 예 이 7은 그죠 이거 좀 잘못했어요. 여러분 소리 이 그림을 좀 잘못해 요렇게 해야 됩니다. 요 차가 같아야 돼요. 자 요거 2차이고 요거 2차이죠. 5보다는 7은 크니까 오른쪽 6은 뭡니까? 7보다 적기 때문에 요쪽 이거 이쪽이 그려 줘야 됩니다. 요쪽에 요렇게 그리고 이제 8은 뭡니까? 8 그리고 인자 다 썼어요. 8하고 13 사이에 빠진 게 뭐였노 910 11 12죠 9 10 11 12야 그러면 이제 요게 뭘 하냐? 하면은 요게 3이 나니까 3보다 큰 게 11이죠. 10 11이고 어떻게 돼요. 11이고 10은 또 11보다 적으니까 그림이 조금 잘못되면 이쪽이죠. 왼쪽 또 9는 10보다 적기 때문에 10의 왼쪽으로 붙어야 됩니다. 약간 좀 이렇게 기울어져야겠네요.

화자 1
20:44
그리고 12는 여기 붙는 거 맞고요. 그리고 이제 13을 하고 21로 갈라 하니까 데이타 끝이 20이니까. 안 넘어가고 그다음에 이제 뭡니까? 요 차가 얼마예요. 요 차가 요 차가 보니까 5다의 말입니다. 오 큰 게 얼마야 18이니까. 18 위에 누가 있죠. 요게 같아야 돼요. 요게 요게 균형을 열어야 됩니다. 18이에요. 그러면 13과 18 사이에 빠진 게 뭐야? 지금 많이 빠졌죠 14 14 15 16 17이 빠졌습니다. 14 15 16 그러니까 이제 마지막에 20이니까. 인제 요거 요거는 2니까 요것도 요래 그려줘야 되면 아니 그림이 좀 이상하다 예 여기 16이고 16이고요. 여기에 15가 들어가고 여기 17 6일 같이요. 그럼 14는 15의 왼쪽이고 그죠 어 그리고 19는 어떻게 됩니까? 이 잘못됐어요. 이거도 아하 이거 엉망이네 19는 여기 달아야 됩니다. 19 예 그림이 좀 파워포인트를 하다 보니까 좀 이해하세요. 요거 19 요 달려야 돼요. 요거 에 18보다는 크고 20보다는 적고 이 그림이 조금씩 좀 잘못됐다.

화자 1
21:40
여러분 이해하시고 뭐 잘 몰려도 좋지만 이런 식으로 피보나치 이 데이터 1에서 20개의 데이타 중에 내가 찾고자 하는 데이터는 18이야 그럼 이놈의 피보나치 수위의 원리만 알면 된다. 피보나치 주의 원리를 이용해 가지고 피보나치 추리를 생성한다니까 이렇게 생성을 어떻게 한다. 자 피보나치 1 더하기 2 3 5 이런 식으로 이래 하고 그 사이에 빠진 게 뭐예요? 작은 거는 왼쪽 큰 거는 오른쪽 속으로 갖다 붙입니다. 이게 피보나치 주리를 만들었지 이 피보나적 줄이야 피보나치 줄이가 생성됩니다. 그죠 생성이 됐어요. 그러면 찾을 때는 뭐예요? 제일 먼저 뉴트노드부터 검색하죠. 내가 찾고자 하는 데이터가 에프케이 얼마 18이지 그럼 제일 먼저 딱 잘라 가지고 딱 검색한 뒤 이 12점 이쪽으로 다 와야 돼 이게 잘못했어요. 13 왼쪽에 탁 와야 되는데 이 그림들이 예 그러면 13은 18보다 적으니까 내가 찾고자 하는 데이터는 뭐야? 반드시 13 오른쪽에 있는 거야. 맞제 그럼 두 번째 뉴트 노드를 조사합니다. 딱 찾아보니까 어 18 찾았다. 몇 분 만에 검색한다.

화자 1
22:40
한번 2번 만에 검색이 끝납니다. 검색 완료 2번 만에 18일 찾았습니다. 찾는 추리를 생성했어요. 쫌 생선 이거 뭐야? 복잡하나 금방 찾는다 맞죠. 좀 복잡하지만 2분 만에 찾는 거죠. 2분 검색보다는 좋다는 거예요. 자 여러분 이해되나 여러분 굳이 피보나치 추리를 여러분 못 만들어도 좋아요. 어 못 만들어도 좋지 원리 이것도 어려운 건 아니제 피보나치 추리는 검색은 어떻다 자 만약 1에서 20개 데이터를 찾는데 에 내가 열여덟 번째 데이터를 찾고 싶으면 선형 검색어 18번 검색해야 되고 이 부분 검색어 반씩 줄여 가는데 나누기를 하잖아요. 왜 중앙갑을 구하기 위해서 근데 피보나치 검색은 뭐다 피보나치 수율의 원리를 이용해 가지고 피보노차리 줄이를 만들어 놓고는 바로 검사합니다. 루트 노드부터 검사에 들어가겠죠. 그러니까 18213보다 크니까 반드시 13 오른쪽에 있다고 하는 거예요. 그러면 두 번째 또 찾아보니까 아 찾는 것 2분만의 검색이 끝나는 겁니다.

화자 1
23:35
이해되나 그래서 피부 나치 여러분들 아 어렵지 않죠 요렇게 정리를 해주면 됩니다. 요 그림이 잠깐 보자 그림이 여러분 좀 전부 잘못됐어요. 전부 다 실은 여기는 전부 13 저기서 이쪽으로 다 가야 돼요. 지금 이쪽으로 다 밀려야 되제 예 요거 아까 그려줬죠 예 이해하시고 파워포인트를 하다보니까 조금 엉망이 됐네 어 우야겠노 예 아래 한글로 할 때는 다시 수정을 해줄게요 자 넘어갑니다. 그다음에 자 그다음에 제어 검색의 마지막 인터폴레이션 보강검색 자 보강검색 여러분이 줄척 있음직화 부분 이성직화 부분 어 이성직한 부분을 찾아가지고, 거기서부터 2분 검색을 행하는 게 봉안검색 역시 2분 검색을 개선한 거죠.

화자 1
24:23
예를 들면은 사전찾기 인명찾기부터 여러분 사전에 예를 들면 내가 파드를 찾는데 파드를 무식하게 에이부터 찾은 사람 있나 병팀이 그래 찾는다고 파드를 찾으면 어디서 찾노 아마 파드 에프부터 에프부터 뒤지제 에 그렇죠. 전화번호부에서 여러분들 홍길동의 주소를 찾고 싶으면 전화번호를 알고 싶으면 어떻게 한다. 기역부터 강부터 찾는 게 아니죠. 어디부터 찾노 기읍부터 들어가제 이게 바로 전부 다 보관 검색법입니다. 있음직화 부분부터 그죠 알겠나 이 보강검색은 인제 있음직한 부분을 어떻게 구하느냐 컴퓨터는요 있음직한 부분을 공식으로 구하죠. 자 있음직한 부분을 아이라 했을 때 이거 아이가 있음직한 부분입니다. 내가 있음직한 부분 이 섬 직함 부분을 찾는데 어떻게 찾느냐 하면은 K1은 뭡니까? 그 리스트의 최대값 어퍼로가 최대값이죠. 최대 최대값 마이너스 케이엘은 뭐다 최소값이에요.

화자 1
25:22
최소값 그 리스트에 그리고 내가 케이는 뭐야? 내가 찾고자 하는 키 값 내가 찾고자 하는 값 키 값이고 요 KL은 역시 채소값이겠죠. 채소값 야채값이 아니고 채소값 미니멈 밸류 최소값 되겠나 그리고 곱하기 곱하기 엔을 해줍니다. 전체 데이터의 개수죠 엔은 뭐다 리스트에 전체 데이터의 계수죠 전체 데이타의 수죠 예 요렇게 찾는 거야. 예를 들면은 자 1에서 10 총 데이터 갯수가 10이네요. 여기서 내가 찾고자 하는 데이터가 8이다. 하자 역시 선형 검색으로 찾을 수도 있고 이분 검색으로 찾을 수도 있고 피보나치 검색으로 찾을 수도 있지만 보강검색은 어떻게 찾는다 어떻게 찾아요. 이 섬취감부터 먼저 구하자 뭐 아이 값부터 구하자 이 말이에요. 있음직한 부분 아이 값을 구합니다. 어떻게 구한다. 최대값 얼마 10 마이너스 최소값 얼마 1이죠. 분의 찾고자 하는 데이터가 얼마 8 마이너스 최소값 1이죠.

화자 1
26:19
곱하기 총 데이타 계수가 얼마씩 이렇게 찾죠 그러면 얼마 9분의 7 곱하기 10이니까. 내가 찾고자 하는 데이터는 9분의 70 얼마 9분의 70이니까. 이거 우예냐 이거 보통 7점 얼마 어 예를 들면 막 이쯤은 붙어있다는 거예요. 이쯤부터 그죠 그럼 여기서부터 뭐다 2분 검색을 해버립니다. 그죠 그러면 역시 2분만의 작겠죠. 알겠나 어 이 원리만 알면 되겠지 이 찾는 거는 누가 찾노 컴퓨터가 찾기 때문에 여러분들은 원리만 알면 되는 겁니다. 그렇죠. 원리만 알고 그놈을 알고리즘 해서 프로그래밍만 해주면은 컴퓨터가 여러분 시킨 대로 보관 검색으로 찾아라 하면 보관 검색 어 선형 검색으로 하라면 선정검색 피보나치로 하라 하면 피보나치 그죠 2분 금속을 하면 2분 금속 이런다는 거야. 그러면 여러분들은 방법은 알아라 으으 방법은 알고 있어요. 아 찾는 방법은 알아야 된다는 말삭 좋습니다. 좋아요.

화자 1
27:17
자 그다음에 이제 블락 검색을 함 볼까요? 자 블락검색 자 이 블락검색은 말 그대로 블락 단위를 찾아준다는 거죠. 자 요것만 알면 돼요. 이것만 주어진 데이터를 가지고 블록을 설정합니다. 블락 어 블록 수 이 블록을 어떻게 결정하느냐 루트 엔으로 보통 결정한 루트 엔으로 좀 적당하게 나누면 됩니다. 루트 엔으로 루트 엔으로 찾아주고 그리고 해당 블록에서 가장 큰 데이터 때려가지고 인덱스 테이블을 만들어 인덱스 테이블을 만듭니다. 루트 앤으로 찾고 블랙을 만들고 그리고는 이 FK와 인덱스 테이블이 아이테이블이 뭐냐 인덱스 테이블 만들어 놓은 인덱스 테이블이에요. 요건 빠져버렸네 인덱스 테이블을 비교해서 해당 물약을 찾고요. 해당 물약을 찾았으면 그 안에서 무슨 검색 선정검색어 적용시킵니다. 어 자 직접 한번 해보자 이 말입니다. 블랙검색 금 내가 인제 찾고자 하는 데이터가 이제 이거예요. 146 막 뒤죽박수 섞여있어도 좋습니다.

화자 1
28:14
이거는 예 자 제어 검색은 방금 배운 2분 검색 피보나치 보관 검색은 반드시 데이터가 소팅돼 있어야 되지만 선형검색이나 블랙 검색은 다른 거는 뭐다 소팅될 필요는 없지 데이터가 이렇게 뒤죽박죽 섞여있어도 상관없는 겁니다. 이해되나 그래서 인제 제어검색만은 데이터가 소트돼 나머지는 섞여서 되는 거예요. 자 그래서 데이터가 이게 뭐 한 20개 있네요. 이 데이터에 데이타 인덱스를 딱 매겨보니까 이거는 이 리스트의 첫 번째가 14호 이거요 두 번째 데이타고 이 말이지 그래서 열다섯 번째 데이터가 뭐 71이네요. 그럼 내가 여기서 찾고자 하는데 딱 57을 찾는 거예요. 57 그러면 선연 검색으로 찾을 수 있겠죠. 선형 검색 찾으면 몇 분만에 찾노 57 여기 있는 12분 만에 찾는 거고, 물론 이분 금색으로 찾을 수도 있고요. 예 뭐 피보나치도 찾을 수도 있고 하는데 제어검색들은 소퇴를 시켜놔야 되고 예 함 봅시다 그러면 여기서 인제 인덱스 테이블을 먼저 만드는 거예요. 생성을 합니다. 인덱스 테이블은 어떻게 한다.

화자 1
29:14
아 제일 먼저 블락을 나눠야 돼요. 블락 블락 수를 결정해야 되죠. 블락 수 자 블락 수는 어떻게 결정한다. 누트 15 누트 15면 얼마 이거 이게 어렵나 모르면 차아뿌라믄 누트 15니까 루트 15 얼마예요. 이거 내가 모르겠다. 루트 15 적당하게 뭐 루트 20원 후에다노 그걸 모르겠다. 한 3.5이나 3개 되겠죠. 블락을 인제 3개로 나눴습니다. 이게 블락 원이고 이거 블록 투고 블락 3이고 컴퓨터 가지고 내가 하는 거 아니죠. 블락 수를 결정합니다. 그럼 블랙을 3개로 결정했죠. 그냥 15개는 뭐 5개씩 나누면 되는 거죠. 뭐 이거 넣대1로 안 해도 되죠. 당연히 15개니까 블락을 5개씩 해 가지고 3개로 나누면 되겠지 그렇죠. 그리고 인제 인덱스 그다음에 이제 블라우스를 결정하고 인덱스 테이블을 만들었는데 인덱스 테이블은 뭐냐면요 각 블랙 안에서 가장 큰 값을 가지고 있는 데이터의 인덱스를 하는 거예요. 그러면 블랙 안에서 가장 큰 데이터가 29 29의 인덱스가 보이면 3이죠.

화자 1
30:11
이렇게 3 오케이 두 번째 블랙에서 가장 큰 데이터는 얼마고 보니까 49네 49에 몇 번째 있나 여덟 번째 맞네요. 그러면 그죠 세 번째 블랙에서는 가장 큰 데이터가 어디에 있나 보니까 보니까 76이네 열세 번째 있다. 이 말이야. 요렇게 인덱스 테이블 각 블락에서 각 블락에서 가장 큰 데이터를 가지고 있는 그 인덱스 값을 가지고 만든 게 인덱스 테이블이야 대체 그 인덱스 테이블을 만들고 난 뒤에는 뭡니까? 내가 찾고자 하는 FK와 인덱스 테이블을 비교한 FK가 찾고자 하는 게 얼마예요. 내가 57을 찾고 있죠. 그러면은 찾아갑니다. 인덱스 테이블 검사하거든. 하니까 세 번째 세 번째 비교해 보니까 얼마 29니까 아 요 가장 큰 게 20분이니까. 이 불량안은 있다. 없다. 그러니까 불량하는 검색할 필요도 없는 거예요. 왜 그 테이블에서 가장 대장 내보다 적은데 뭐 내가 말하면 가상대하노 없습니다. 또 두 번째로, 갑니다. 가 보니까 여덟 번째 들어있어 아 이거 내보다 적으니까 이것도 찾을 필요 없다. 두 번째 내가 내가 없다. 이 말 찾고자 하는 게 없다. 이 말입니다.

화자 1
31:09
그리고 이제 세 번째 인덱스트를 가보니까 열세 번째 가보니 아 70 아이고 요 안에 있겠네 해서 해당 블락을 찾습니다. 해당 블락을 세 번째 블락이 있구나 그럼 요 세 번째 블랙에서부터 무슨 검색 선정검색을 합니다. 오케이 몇 번 만에 찾노 1번 비교 2번 그 다음에 3번 4번 5번 만에 찾아 들어가는 거죠. 선정 검색하면은 13분 만에 찾아야 될 거예요. 데일러 그래서 블랙 검색은요, 데이터의 개수가 많을 때 이렇게 많을 때 뒤죽박죽 섞여 있을 때 블락 으 많은 큰 리스트를 적당하게 루트인으로 블락을 하나 놓고 그 블랙 해당 블랙을 찾는데 어떻게 찾는다 인덱스 테이블을 만들어서 그 인덱스 테이블과 내가 찾고자 하는 데이터를 비교해 가면서 바로 찾아 들어가는 방법이다. 됐나 이 정도 어떤 문제 나와도 여러분은 맞출 수가 있을 겁니다. 알겠지 자 그다음에 한번 넘어가 보죠.

화자 1
32:02
자 재밌다 갈수록 재미있어지네 아니 뭐 가벼운 마음으로 해 1편의 드라마 보듯이 그저 내가 몸이 조금 안 좋다고 너까지 쳐지나 계속 요즘 어제하고 오늘날 요번 주에 와서 계속 이 몸이 안 좋아요. 왜 그러냐 막 굉장히 바쁘고 지금 또 어 이 시간에 지금 또 저 호주에서도 우리가 호주의 큰 대학하고 큰 비즈니스를 합니다. 여러분 우리 사이트를 잘 보면은 우리 사이트는 여러분 자격증만 따주는 사이트 이제 그 보면 취업 티비도 있죠. 자격증을 따서 여러분 인재 정보에 등록하면 이야기하지 반드시 자격증을 따면 우리 회사의 인재 정보에 여러분 사진 올리고 해 그럼 우리가 기업체들하고 연결돼 있어요. 기업체에서 딱 들어와서 여러분들을 픽업해 가거든. 어 그게 우리 기업 채용 정보예요. 우리 사이트에 있다잉 에 그것도 모르나 한번 설명해 보세요. 어 그리고 우리 MTM 에서 만든 사이트 다 그래 그리고 해외 취업까지 다 시켜주잖아.

화자 1
33:01
또 해외 진화까지 그러다 보니까 내가 미국하고 호주하고 자주 갑니다. 자주 가는데 요번에 생중계 때문에 내가 몬 가니까 지금 호주에서 날아왔어요. 에 호주에서 대학의 처장하고 이래 와가지고 지금 이 지금 예 생중계 끝날 때 기다리고 있는 거예요. 지금 옆방에서 알아 에 아나 여러분 때문에 이 비즈니스도 뭐하고 말이야. 박수 한번 쳐라 예 그래서 지금 끝나자마자 또 옆방으로 넘어가야 됩니다. 이 방송국에서 또 넘어가야 돼요. 에 그러나 그러니까 여러분이 호주 호주에도 여러분들 우리 엠투엠 점프 투어 한번 가보세요. 그죠 바로 온라인에서 여러분들 호주 대학 과정을 하고 호주의 큰 기업에 진출할 수가 있습니다.

화자 1
33:39
할렐루야 그죠 해외진출 휴먼웨어 왜그러노 국가가 해야 되는데 이거 국가 대학이 해야 되고 어 정부에서 해야 되는데 안 하니까 안하면 저끼리 맨날 쓸데없는 가지고 국민 혈세를 낭비하니까 제재치가 해야지 할 수 있나 어 대통령이 해야 되고 어 국회의원들이 해야 되는데 아무도 안 하니 내가 하자 내가 내가 나라도 해야지 그래서 내가 어 칼자루 두 칼 2개 가지고 적어 핸드폰 가지고 내가 세상 정보관을 다녀요 그래서 이 생중계 끝나자마자 또 미국도 가고 호주도 가고 내가 갑니다. 가서 또 가들 평정해야지 평정 여러분들 데리고 100만 군다 나바리 나바리가 대한민국에서 나바리 관리하면 되나 해외까지 그래서 내 슬로건이 뭐야?

화자 1
34:23
기술과 영어로 해외 진출하자 기술과 영어로 해외 진출 자 IT 기술과 영어로 휴먼웨어를 실천하는 게 제재치의 소원이야 알겠나 왜 국가에서 해야 되는데 국가에서 이 청년실업에서 이태백이 상팔선 사오정 어 뭐 어렵다 해결해야 되는데 안 하잖아. 뭐 하잖아. 왜 능력이 없어요. 능력이 없으니까 어 그래 뭐 내라도 해야 되지 뭐 어 여러분들 국회의원 뽑아주든지 말든지 뭐 내가 하는 거예요. 따라와 알겠나 그래서 열 받으면 지금 기다리고 있어요. 지금 에 호주대학에 유명한데 처장이네 기다리고 딱 있는 거야. 좋습니다. 빨리 하라고요. 좋아요. 자 이 추리검색은 이진 검색추리를 역시 인제 이 추리검색은 이 데이타 집단을 이진추리로 만듭니다. 이진추리 즉 완전히 이진 추리를 만들죠 그죠 전이진 추리를 만드는 거예요. 만들어 놓고 이제 데이터를 검색하는 겁니다. 예를 들면은 자 리스트 속에 데이타가 5863 뒤죽박죽 섞여있어도 좋습니다. 그죠 데이타가 리스트 속에 파일 속에 이렇게 있는 겁니다.

화자 1
35:22
내가 찾고자 하는 데이터 2를 찾고 싶다. 선연 검색으로 찾을 수도 있고 뭐 여러 가지 찾을 수가 있는데, 이제 이진 추리 검색을 하라 이카면 어떻게 한다. 이 논문이 우선 뭐다 전이 진추리 이진추리를 만드는 거야. 이진추리 어떻게 만든다. 제일 첫 번째 데이터가 묶여 놓더니, 5 그리고 두 번째 탈이 우예 됩니까? 아 이거도 조금 잘못됐네요. 다시 합시다. 요것 좀 아유 좀 실수가 많네요. 다시 합니다. 예 자 첫 번째 첫 번째 데이타가 루트노드가 돼요. 그다음에 두 번째가 오 요거 역시 팔이 5보다 크나 적으나 크면은 왼쪽이고 적으면 오른쪽입니다. 여기 갖다 붙이고 이 잘못됐네요. 완전히 무시하십시오. 그리고 6은요, 6은 어떻게 됩니까? 5보다는 크고 8보다는 적습니다. 그러니까 5보다는 크고 8보다 적으니까 요렇게 요렇게 가야 돼 6 5에 오른쪽 4는 어떻습니까? 5보다 적으니까 4가 여기 오네요. 4가 여기 인제 더 옵니다. 3은 어떻습니까? 5보다 적고 4보다 적으니까 여기 오네요.

화자 1
36:22
여기 오케이 9는요 5보다 크고 8보다 크니까 여기 오네요. 여기에 요기 오네 요게 맞아요. 그 다음에 10은 5보다 크고 8보다 크고 9보다 크니까 여기 오네요. 여기 옵니다. 완전히 잘못됐어요. 1은요, 5보다 적고 적으니까 왼쪽 4보다 적으니까 왼쪽 3보다 적으니까 왼쪽 여기 옵니다. 여기에 예 2는요 5보다 적으니까 왼쪽 저건 적고 1보다는 크니까 뭐예요? 요쪽이 와요. 요쪽 예 그리고 7은요, 5보다 크니까 왼쪽 팔보다 적으니까 오른쪽 팔보다 적으니까 왼쪽 6보다 크니까 오른쪽 이렇게 와요. 요게요 요렇게 되는 이거 틀렸고요. 요게 맞습니다. 요거 요렇게 만들어 놓자 됐나 이 주어진 데이터는 것을 이진추리로 만들 줄 알아야 되겠죠. 그럼 만들면 어떻게 한다. 요놈보다 적은 건 요쪽 큰 건 이런 쪽 이렇게 나열합니다. 됐어요. 그래 놓고 이제 찾는 거예요. 그럼 내가 찾고자 하는 게 2지야 내가 찾고자 하는 게 데이타가 2입니다.

화자 1
37:22
그러면 이제 검사를 합니다. 처음에 오를 검사하죠. 그러니까 내가 찾고 2이니까. 5보다 5가 내보다 크니까 여기 찾아요. 그럼 여기 찾습니다. 그 다음에 찾아요. 어 아니 몇 번 만에 1번 2번 3번 4번 5번 만에 찾습니다. 근데 선정 검색하면 몇 번 만에 찾는 거 하나 둘 셋 넷 다섯 여섯 일곱 여덟 번만 9번만에 찾는 거 1234 5번 만에 검색이 완료되는 겁니다. 알겠나 예 요렇게 추리검색은 이진추리를 생성 후 검색하는 거죠. 되겠나 뭐 예를 하나 더 보고 만약 이런 경우 데이터가요 54321 이렇게 되면 어떻겠냐 이거는 뭐요 사양추리가 되죠. 사양추리 같은 경우는 선정검색과 동일하게 되겠죠. 내가 만약 여기서 일을 찾는다 카면은 에 이건 뭐야? 1번 2번 3번 4번이지만 선정검색도 뭐야? 1번 2번 3번 4번 그죠 만약에 이 데이터들을 추리로 만들었는데 사양 추리로 만들어져 버렸다 하면 이거는 뭐다 2진 검색할 필요 없고 뭐하는 게 좋다. 선정검색하고 똑같다 이 말입니다. 뭔 말이 되죠. 어 선정검색과 동일한 효과가 납니다.

화자 1
38:22
어떤 경우는 사향 2주 아닌 경우는 뭐예요? 전이진 추리나 정의진 추리 같은 경우는 이제 아주 효과가 좋은 거예요. 됐나 주어진 데이터를 이진 추리로 만들어 놓고 거기서 그래서 이진 추리를 만들 줄 알아야 된다는 거 뭐 아주 쉬워요 작은 건 왼쪽 큰 거는 오른쪽 작은 건 왼쪽 큰 거는 오른쪽 하면 됩니다. 좋습니다. 넘어가 넘어가자 예예 좋아요. 그다음에 이제 방금 봤는 것들은 뭐다 비교 검색이죠. 비교검색 지금부터 하는 거는 헤싱 해싱은 앞에서 했잖아. 헤싱을 했습니다. 내가 직접 파일에서 했죠. 자 해싱 검색어 뭐냐 직접 검색법 실은 가장 빠른 검색이다. 그죠 내가 찾고자 하는 키 값으로 원하는 레코드 원하는 데이터 원하는 원소 원하는 요소가 있는 기억 장소의 주소를 빡빡 해싱 함수를 이용하여 직접 계산해 한방에 찾아가는 방식이 해싱이다. 이 말입니다.

화자 1
39:21
그죠 해싱은 뭐다 바로 해싱 함수에 의해서 뭘 구한다. 주소를 자동으로 생성해서 이 구해진 주소를 가지고 만든 테이블이 뭐다 해싱테이블입니다. 그럼 이렇게 주소값을 자동으로 구해주는 핵심함수는 뭐가 있느냐 여기에 있다. 이 말이에요. 7가지가 자 요건 아 요건 각각 모녀도 좋다. 여러분 살짝 봐 놓으면 돼요. 제3법 나눠 가지고 구하는 주소법이 있고 제곱법 뽑혀서 주소를 구하는 게 있고 폴딩 법 이게 인제 폴딩법은 이 접는 거죠. 접는 거 접지법이라 하죠. 폴딩법 접지법 어 대타들을 접어서 주소 갖고 가는 게 있고 대수적 코딩법도 있고요. 숫자 분석 디지털 어널리시스 그죠 그다음에 기수변환법 그다음에 렌즈 무작위로 데이터를 발생시켜서 주소를 구하는 거죠. 그러니까 헤칭 함수의 종류 이렇게 시험이 나오죠. 그러면 다음 중 헤싱 함수의 종류가 아닌 것 있다고 문제 나오거든요.

화자 1
40:13
여러분 살짝 눈으로 살짝 쿵 어 재산적 오 폴딩법 대수적 코딩법 숫자 분석 기수변화법 무작위법 이 정도만 살짝 쿵 봐주면 됩니다. 알겠나 이것 중에 하나를 가지고 뭐다 주소를 구하죠. 재산법으로 구할 수도 있고 제곱을 할 수 여러 가지 방법 중의 하나만 하면 되는 거죠. 그럼 여러분 각각의 알고리즘은 뭘 해도 좋습니다. 원래는 대학원 과정에서는 이런 것까지 다 합니다. 학부 과정에서는 여러분들 종류만 알고 있으면 돼 정보처리기사는 학부 과정에 묻는 거고, 기술사가 뭡니까? 석박사 과제이다. 알겠나 여러분 정보처리기사 자격증 따고 7년 있으면은 정보처리기술사도 할 수가 있습니다. 기술사 박사급입니다. 예 그래서 인제 자동으로 생성되어 만든 주소를 뭐다 이런 해시 테이블에 하죠. 이 해시테이블은 뭡니까? 슬롯도 아니 슬롯이에요. 이 슬롯 슬롯 슬롯 슬롯 슬롯을 슬롯의 주부였는데 이 슬롯은 또 뭡니까? 이거 버킷 버킷 완 버킷 투 버킷 쓰리 버킷 포 이 버킷이에요. 버킷은 행이고 슬롯은 열입니다.

화자 1
41:13
열 그러니까 해시테이블 어떻게 구성되나 하면요 슬롯이 모여서 버킷을 형성하고 버킷 버킷들이 모여 가지고 하나의 해시 테이블을 만들어냅니다. 알겠나 예 그래서 이게 구해진 주소를 해시테이블에 저장을 딱 한단 말이야. 하는데 여러분 어떤 경우 동일주소 즉 시나미녀 드레스 즉 동의어 어 동일 주소하고 구할 수가 있지 이게 숫자를 구하다 보니까 어 그러면 동일 주소를 구하면요 같은 슬로스 같은 솔로 여기에 만약에 주소가 구했어요. 또 구해지면 여기 들어와 그럼 동일 주소 구하면 어떤 현상이 일어나냐 딱 충돌현상이 일어납니다. 홀리전 동일 주소가 구해지면 충돌 현상이 일어난다니까 빡 같은 거 놓으니까 박치기 할 거 아니에요. 골리죠 충돌 빡 충돌하면 구해야 되는 한 놈이 튕겨 나가야 되지 튕겨나가는 게 뭐다 오버플로우입니다.

화자 1
42:06
그죠 자 동일 주소를 구해주면 어떤 현상 골리죠 콜리젠이 이런 한 놈이 튕겨나가는 현상 무슨 현상 오버풀로 그럼 이런 오버풀로를 방지하는 방법이 없는 있다. 이 말입니다. 그죠 자 개방주소법 이것도 역시 제목 전달 개방주소법 폐쇄주소법 재해신법 2차 탐색법 이놈은 뭐다 오버풀로 방지법이죠. 그죠 개방주소법 폐쇄주소법 재심법 2차 탐색법 요런 것들은 오버플로 방지법이에요. 되겠나 자 중요하죠. 해싱 하는 게 뭐다 지금까지 봤는 것들은 데이터를 일일이 비교를 해야 되는데 해시는 뭐다 내가 구하고자 하는 데이터 찾고자 하는 데이터의 주소 값이 뭐다 해시 함수를 이용해서 주소 값을 다 구해 가지고 주소를 저장해 놓고 이 주소를 탐색해서 이 주소 값을 가지고 한 방에 찾아가는 게 뭐다 헤싱 예 해싱 섭치다 이 말입니다. 됐나요? 그래서 동일 주소 권리전 오브플로우 해결 방법 되겠습니까? 그래요.

화자 1
43:01
자 방금 봤는 것들이 오늘날 컴퓨터에서 특정 리스트 속에서 또는 파일 속에서 데이터 집단 속에서 특정 데이터를 찾는 방법들입니다. 특정 데이터를 찾는 방법들 다시 정리하자 그다음에 뭐 있어요. 비교 방법에는 선연 검색 그 다음에 저 검색에는 이분 검색 피보나치 검색 보강검색 그 다음에 블락검색 추리검색 가장 빠른 방법이 뭐다 해싱 검색 됐나요? 예 요 정도입니다. 그죠 실제 요거 외에는 없더라 이 말입니다. 그래서 컴퓨터에서 데이터를 신속 정확하게 찾는 게 이런 방법들이 있기 때문에 우리는 아주 쉽게 검색을 할 수가 있는 겁니다. 그죠 되나 그래서 어렵지 않다 이 말입니다. 그죠 검색에서도 1문제 예상되는데 요 7개 중에 하나가 나오겠다. 그렇죠. 그래서 여러분 가벼운 마음으로 정리하시면 됩니다. 됐나요? 자 다음 없죠 이렇게 금세 오늘은 준비되어 있는 게 있습니까? 한번 넘겨보면 없죠 예 좋아요.

화자 1
44:01
좋습니다. 그래서 내가 오늘 요즘 요번 주에는 좀 아주 컨디션이 나쁜데 어쩔 수 없는 생방송인데 이거 인생은 생방 인생은 생방송 생방송 아니야. 우짜게노 여러분 힘을 좀 더 주시고 목이 지금 너무 뻣뻣합니다. 그죠 그래서 오늘은 검색만 이렇게 하고요. 이제 내일도 나머지 정렬 그리고 데이터베이스로 넘어가 봅니다. 이해되나 계속해서 여러분 열심히 하고 있고 또 생방송을 조금 보는데 다소 이제 접속이 많다보니까 그런 점 계속 양지바라고 좋아요. 자 제2의 제자로써 에 자부심을 가지고 이제 기술자만이 사는 거죠. 너또 복권 인생 인생 역전 몇 가지 2가지 뭐고 순자 시험 나온다 어 너또복권 아니면 뭐다 기술이다. 그죠 그래서 특히 기술 중에서도 IT 기술이 최고의 머리 뽑는 기술도 있고 뭐 여러 가지 있지만 IT 기술을 익혀가지고 이제 거기서 영어를 가지구요.

화자 1
44:53
전 세계의 휴머니아를 한번 실천해 보자 우리의 나발이를 넓히자 그런 메시지를 주면서 오늘은 여기까지 하겠습니다.