기본 콘텐츠로 건너뛰기

개발 공부 - 이진 검색 (추가)

* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.

* 프로그래머스에 살다가 새벽이 넘어버려서 부랴부랴 쓴다.
하루의 일과를 지켜내겠다는 의지!


이진 검색은 정렬된 배열에서 원하는 데이터를 찾는 것이다.
작은 것에서 큰 것으로 정렬하는 것 : 오름차순 (ASC)
큰 것에서 작은 것으로 정렬하는 것 : 내림차순 (DESC)

1~100까지 한 숫자를 떠올릴 때, 적은 횟수로 맞추기 위해서는 50을 찾는 것이
이진 검색의 기초이다. (중간 값을 생각할 수 있으면 됨)

검색 대상 배열 a
찾아낼 값이 저장된 변수 x
찾은 요소의 인덱스를 저장하는 변수 pos를 쓴다.

왼쪽 끝 요소 인덱스를 저장한 변수 left (초기값은 0이다.)
오른 쪽 끝 요소 인덱스를 저장한 변수 right (초기값은 마지막 인덱스다)
배열 중앙 요소 인덱스를 저장한 변수 middle 이 필요하다.( ( 왼 + 오 )/ 2 로 구할 수 있다.)

정수형이라 나머지는 버리고 middle 값을 적용하면 된다.

1. pos를 -1로 초기화하고
2. left를 0으로 초기화하고
3. right를 a의 길이로 초기화하고
4. left 와 right 로 middle을 구하고
5. a[middle]과 x(찾아낼 값) 을 비교해서
A x를 찾으면 pos를 middle로 덮어씀
B a[middle] > x 면 right를 middle -1 로 변경하고 <<< 로 감
C a[middle] < x 면 left 를 middle +1 로 변경하고 >>> 로 감

6. B, C일 경우 원하는 값이 발견되지 않았으면 재실행함




앗 POS는 -1이다.
(-1이 미발견)

이걸 Java로 구현하면 이렇게 된다.


결과는 5가 나온다. (정상 동작)
이진 검색은 for문이 아닌 while 문을 사용하는 것이 포인트라고 한다.

만약 x 값이 아예 없는 숫자라면 전체를 탐색한 후 -1이 나오는 것이 정상이다!

추적 코드를 넣어보면 아래와 같다.
while 문 실행 전, 실행 중, 실행 후에 추적 코드를 삽입한다.





선형 검색과 이진 검색은 모두 데이터 검색을 목적으로 사용하는 알고리즘인데, 
보통 배열의 처음부터 끝까지 순차적으로 확인하는 선형 검색보다는
배열을 2개로 나누면서 검색 범위를 좁히는 이진 검색이 더 효율적이다.

선형 검색은 시간 복잡도가 O(N) 이며, 
이진 검색의 시간 복잡도는 O(log2N)이다.
log2N은 N개의 데이터를 계속 분할해서, 마지막 하나가 될 때까지 처리한 횟수이다.

따라서 요소 수가 8개인 배열을 이진 검색하는 경우 -> 3회 분할하면 요소 수가 1개가 된다.
8 -> 4 -> 2 -> 1

따라서 데이터 수가 많은 경우에는 선형 검색보다 데이터를 일정 기준으로 정렬하여 이진 검색을 사용하는 것이 맞다.
(데이터 수가 적은 경우에는 정렬 하는 것이 낭비이므로 그냥 선형 검색을 쓰는 것이 낫다.)


정렬은 자바 코드 상으로는 아래와 같이 오름차순 / 내림차순 해서 사용하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Arrays;
import java.util.Collections;
public class App {
    public static void main(String[] args) throws Exception {
        int [] a = new int[10]; 
        for(int i : a){
            i = (int)(Math.random()*10);
        }
        //오름차순
        Arrays.sort(a);
        //내림차순 : Stream으로 쉽게 해결할 수 있다. (컬렉션이라 Integer로 사용해야 한다.)
        Integer [] tempA = Arrays.stream(a).boxed().toArray(Integer[]::new);
        Arrays.sort(tempA, Collections.reverseOrder());
        a = Arrays.stream(tempA).mapToInt(i->i).toArray();
        int x, pos, left, right, middle;
        x = a[1];
        pos = -1;
        left = 0;
        right = 9;
        System.out.println("반복 실행 전 x 값 : " + x);
        System.out.println("반복 실행 전 pos 값 : " + pos + " left 값 : " + left + " right 값 : " + right);
    
        while(pos == -1 && left <= right){
            middle = (left+right)/2;
            if(a[middle] == x){
                pos = middle;
            }else if(a[middle] > x){
                right = middle -1;
            }else{
                left = middle + 1;
            }
            System.out.println("반복 실행 중 x 값 : " + x);
            System.out.println("반복 실행 중 pos 값 : " + pos + " left 값 : " + left + " right 값 : " + right);
        }
        System.out.println("pos 값은 " + pos);
    }
}
cs

보약같은 Stream!
8부터 Stream 이랑 람다 지원해서 너무 행복함.

쓰는 것만 썼는데 조금 더 확장해서 써보자.
읽어보고 (추가) 지울 것 : https://ahndding.tistory.com/23



댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - PC 카카오톡 작업 표시줄 아이콘 이미지 변경 방법

PC 카카오톡 사용시 작업 표시줄에서 아이콘 이미지를 변경하는 방법이다. 1) 작업 표시줄 내 카카오톡 아이콘에서 마우스 오른쪽 버튼을 누른  뒤 속성에 들어간다. 2) 아이콘 변경에서  C:\Windows\system32\imageres.dll C:\Windows\system32\shell32.dll C:\Windows\system32\DDORes.dll C:\Windows\System32\moricons.dll (MS DOS Icons) 등을 누른 뒤 적당한 것을 선택하여 적용한다. * 사내 메신저 아이콘을 참고해도 된다. 참고 : 기본 아이콘 위치 https://blog.silnex.kr/windowstip-windows-%EA%B8%B0%EB%B3%B8-%EC%95%84%EC%9D%B4%EC%BD%98-%EC%9C%84%EC%B9%98/ 2022. 11. 29.  생각보다 유입이 많아서 놀랐습니다. PC 카톡 사용자 화이팅!

운동 정보 - 어메이즈핏 밴드 5 스마트밴드 나이키 런 클럽(NRC = Nike Run Club) 연동

 나이키 런 클럽 쓰려고 산 어메이즈핏 밴드5 인데 연동이 영 어려워서 찾아보고 써봤다. 1. Zepp 앱은 연동이 되어 있어야 한다. 2.  Zepp 앱 -> 프로필 -> 내 기기 -> Amazfit Band 5 3. 검색 가능 : 켜짐 활동 심박수 공유 : 켜짐 연결 제한 : 꺼짐 (기본) 백그라운드에서 실행 : 제외로 등록 4. NRC(나이키 런 클럽) 앱 -> 설정 -> 러닝 설정 -> 기기 5. 심박수 표시 -> 블루투스에서 AmazFit Band 5 누르고 NRC 즐기면 된다! * 안드로이드 이용자입니다.