스크래치 COS -이진검색
스크래치COS 코딩시험에서 알고리즘의 가장 핵심적인 부분이 변수, 반복문, 조건, 함수이다.
코딩에서 가장 기본이 되는 알고리즘 중 검색 알고리즘에 대해 알아보겠다.
이전 글에 선형검색에 대해서 알아보았다.
이제는 이진검색에 대해서 알아보겠다. 이진검색은 리스트의 데이터가 먼저 정렬이 되어 있어야 한다.
정렬된 데이터를 기준으로 반을 나누어 가면서 검색한다.
아래 만일 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회 반복하며 1~100 사이의 난수를 num 리스트에 추가한다.
. 퀵정렬
. 입력한 데이터를 통해 퀵정렬을 실행하면 num 리스트를 정렬한다.
블럭코딩
| . 입력 신호를 받았을 때 . num 리시트 변수의 항목을 모두 삭제하기 . 10회 반복하며 1~100 사이의 난수를 num 리스트에 추가한다. |
| 퀵정렬 신호를 받았을때 퀵정렬(1, num의 길이) 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 리스트 변수가 정렬이 된다.
찾기 버튼 스프라이트를 클릭하면 이진검색이 실행이 된다.
찾고자 하는 값을키보드로부터 입력받는다.
키보드에서 71 숫자를 입력하면 "7번째 위치에서 찾았습니다." 스크래치를 활용한 이진검색 실행화면이 아래 그림과 같이 표시됩니다.
스크래치를 통해 퀵정렬 알고리즘을 통해 입력 리스트를 정렬하고, 이후, 찾기 버튼을 클릭하면 이진검색을 실행하는 알골리즘을 구현하였다. 이진검색은 다른 어떤 검색보다 매우 빠른 결과를 제공한다.
여기서도 분명히 low, high, mid의 변수값을 천천히 변화하는 값을 분석하며 이진검색을 분석하기를 추천한다.
다시 한번 강조해서 말하지만, 변수의 값이 각 프로그램 단계별 순차적으로 어떻게 변화하는지 추척하는 것이 매우 중요하다. 블럭을 하나씩 쌓으면서 변수 볼륨 값의 변화를 살펴보자. 코딩은 눈으로 보면서 이해하고 학습하지만 직접 블럭을 쌓으며 이해하고 학습하는 것이 더 효과적이며 창의와 이해의 개념이 ~쑥 늘어납니다.
앞으로의 여러분의 모습을 기대합니다.
Just Do it!!!
Just Drag&Drop!!!
'스크래치 > 스크래치 COS시험' 카테고리의 다른 글
| 스크래치COS-퀵정렬 (0) | 2022.08.11 |
|---|---|
| 스크래치COS-선택정렬 (0) | 2022.08.10 |
| 스크래치COS-버블정렬 (0) | 2022.08.09 |
| 스크래치COS-선형검색 (1) | 2022.08.08 |
| 스크래치COS-십진수를이진수로변환 (0) | 2022.08.07 |
댓글