엔트리 -이진검색
엔트리 코딩시험에서 알고리즘의 가장 핵심적인 부분이 변수, 반복문, 조건, 함수이다.
코딩에서 가장 기본이 되는 알고리즘 중 검색 알고리즘에 대해 알아보겠다.
이전 글에 선형검색에 대해서 알아보았다.
이제는 이진검색에 대해서 알아보겠다. 이진검색은 리스트의 데이터가 먼저 정렬이 되어 있어야 한다.
정렬된 데이터를 기준으로 반을 나누어 가면서 검색한다.
아래 만일 9를 찾는다고 하면 7개의 데이터 수에서 반의 위치는 4와 찾고자 하는 값 9와 비교를 한다.
num : 정렬된 리스트
n = 9
if num(4) < n (7 < 9, true)
오른쪽의 데이터에서 찾을 것이다.
| 1 | 3 | 5 | 7 | 9 | 11 | 13 |
| i |
if num(6) < n (11 < 9, false)
왼쪽의 데이터에서 찾는다.
| 1 | 3 | 5 | 7 | 9 | 11 | 13 |
| i |
if num(5) = n ( 9 = 9, true)
found
| 1 | 3 | 5 | 7 | 9 | 11 | 13 |
| i |
이진검색은 총 3번에 검색해서 찾는다. 만일 선형검색을 하면 5번을 검색해서 찾을 수 있다.
이진검색이 빠르게 찾을 수 있는 장점이 있다. 그러나 정렬해야 하는 시간이 소요되는 단점이 있다.
요구사항
리스트에 5개의 숫자를 1~100 사이의 난수를 발생하여 삽입한다.
그리고 이진 검색 알고리즘을 활용하여 찾고자 하는 겂을 검색한다.
먼저 리스트를 난수 발생하여 삽입한 후에 정렬한다.(퀵정렬, 버블정렬 등)
이후 이진 검색 알고리즘을 통해 찾고자 하는 값을 검색한다.
low = 1
high = 10
loop( low < = high ) {
#### 데이터의 중간 위치를 계산한다. : mid
mid = (low + high) /2
### 중간위치값과 n값이 같으면 검색완료
if n = num(mid) {
검색완료
}
### 찾지못했다면 왼쪽/오른쪽에서 찾을 것인지 판단해야 한다.
### n값이 중간값보다 크면 왼쪽에서 찾는다 -> high = mid-1로 정한다.
### n값이 중간값보다 작으면 오른쪽에서 찾는다 -> low = mid + 1로 정한다.
else {
if n < num(mid) {
high = mid-1
else {
low = mid + 1
}
}
}
else {
탐색 실패
}
분석 및 설계
. 변수만들기
- num : 10개의 숫자를 저장하는 리스트 변수이다.
- temp : 임시 저장 변수
- mid : 가운데 위치값을 저장하는 변수 (기준이 되는 위치 값)
- low : num리스트의 왼쪽 위치값을 저장하는 변수이다.
- high : num리스트의 오른쪽 위치값을 저장하는 변수이다.
. 오브젝트
- 엔트리봇 오브젝트 : 실제 하는 일은 없다.
- 입력 글상자 오브젝트 : 입력 글상자를 클릭하면 num 리스트에 난수 값이 10개 입력된다.
- 퀵정렬 글상자 오브젝트 : 퀵정렬 글상자를 클릭하면 퀵정렬 알고리즘으로 정렬을 실행한다.
- 이진검색 글상자 오브젝트 : 이진검색 글상자를 클릭하면 이진검색 알고리즘으로 검색을 실행한다.
. 초기화
. 입력 신호를 받았을 때
. num 리시트 변수의 항목을 모두 삭제하기
. 10회 반복하며 1~100 사이의 난수를 num 리스트에 추가한다.
. 퀵정렬
. 입력한 데이터를 통해 퀵정렬을 실행하면 num 리스트를 정렬한다.
블럭코딩
| . 입력 글상자 오브젝트를 클릭했을 때 . num 리시트 변수의 항목을 모두 삭제하기 . 10회 반복하며 1~100 사이의 난수를 num 리스트에 추가한다. |
| 퀵정렬 글상자 오브제트를 클릭했을 때 초기값 설정 . 찾고자 하는 값을 키보드로부터 입력받아 변수 n에 저장한다. . low = 1 . high = num의 길이 |
* 이진검색
| 이진검색 loop( low < = high ) { #### 데이터의 중간 위치를 계산한다. : mid mid = (low + high) /2 ### 중간위치값과 n값이 같으면 검색완료 if n = num(mid) { 말하기(검색완료) } ### 찾지못했다면 왼쪽/오른쪽에서 찾을 것인지 판단해야 한다. ### n값이 중간값보다 크면 왼쪽에서 찾는다 -> high = mid-1로 정한다. ### n값이 중간값보다 작으면 오른쪽에서 찾는다 -> low = mid + 1로 정한다. else { if n < num(mid) { high = mid-1 else { low = mid + 1 } } } 말하기(탐색 실패) |
* 디버깅
low=1
hight = 10
num 리스트
| 4 | 10 | 15 | 32 | 53 | 54 | 62 | 80 | 81 | 98 |
| low | mid | high |
n=62 (찾고자 하는 값)
* 이진검색 알고리즘
[[스텝1]]
low > high 반복하기
mid = 버림((1 + 10) / 2), 5
if n = num(mid) (62 = 52, false)
else
if n < num(mid) ( 62 < 52, false) {
high = mid - 1
else
low = mid + 1 ( 6 )
| 4 | 10 | 15 | 32 | 53 | 54 | 62 | 80 | 81 | 98 |
| low | mid | high |
[[스텝2]]
low > high 반복하기
mid = 버림((6 + 10) / 2), 8
if n = num(mid) (62 = 80, false)
else
if n < num(mid) ( 62 < 80, true) {
high = mid - 1 (7)
else
low = mid + 1 ( 6 )
| 4 | 10 | 15 | 32 | 53 | 54 | 62 | 80 | 81 | 98 |
| low, mid |
high |
[[스텝3]]
low > high 반복하기
mid = 버림((6 + 7) / 2), 6
if n = num(mid) (62 = 54, false)
else
if n < num(mid) ( 62 < 54, true) {
high = mid - 1 (6)
else
low = mid + 1 ( 7 )
| 4 | 10 | 15 | 32 | 53 | 54 | 62 | 80 | 81 | 98 |
| low, mid, high |
[[스텝3]]
low > high 반복하기
mid = 버림((7 + 7) / 2), 7
if n = num(mid) (62 = 62, true)
찾았습니다.
else
if n < num(mid) ( 62 < 80, true) {
high = mid - 1
else
low = mid + 1
* 실행 결과물
'입력' 글상자 오브젝트를 클릭했을 때 num 리스트 변수에 10개의 난수값이 추가된다.
이진검색을 효율적으로 하기 위해서는 입력데이터가 정렬이 되어 있어야 한다.
그래서 지난 시간에 작성한 퀵정렬을 활용한다.
퀵정렬 버튼 스프라이트를 클릭하면 아래와 같이 num 리스트 변수가 정렬이 된다.
이진검색 글상자 오브젝트를 클릭했을 때
찾고자 하는 수를 입력한다. 여기서는 42를 입력하였다.
찾은 결과 화면이다.
8번째에서 찾았음을 알려준다.
엔트리를 통해 퀵정렬 알고리즘을 통해 입력 리스트를 정렬하고, 이후, 찾기 버튼을 클릭하면 이진검색을 실행하는 알골리즘을 구현하였다. 이진검색은 다른 어떤 검색보다 매우 빠른 결과를 제공한다.
여기서도 분명히 low, high, mid의 변수값을 천천히 변화하는 값을 분석하며 이진검색을 분석하기를 추천한다.
다시 한번 강조해서 말하지만, 변수의 값이 각 프로그램 단계별 순차적으로 어떻게 변화하는지 추척하는 것이 매우 중요하다. 블럭을 하나씩 쌓으면서 변수 볼륨 값의 변화를 살펴보자. 코딩은 눈으로 보면서 이해하고 학습하지만 직접 블럭을 쌓으며 이해하고 학습하는 것이 더 효과적이며 창의와 이해의 개념이 ~쑥 늘어납니다.
앞으로의 여러분의 모습을 기대합니다.
Just Do it!!!
Just Drag&Drop!!!
'엔트리메뉴 > 엔트리코딩시험-알고리즘' 카테고리의 다른 글
| 엔트리-퀵정렬 (0) | 2022.09.13 |
|---|---|
| 엔트리-선택정렬 (0) | 2022.09.12 |
| 엔트리-버블정렬 (0) | 2022.09.11 |
| 엔트리-선형검색 (1) | 2022.09.10 |
| 엔트리-십진수를이진수로변환 (0) | 2022.09.09 |
댓글