3월 17일 Day12.

오늘 알고리즘 문제 풀 때 2차원 배열을 정렬하는 Integer.compare(o1, o2) 를 접하게 되었는데 검색 알고리즘을 공부하다가 같은 부분을 다시 보게 되었다 ! 생각보다 더 깊이 있는 공부가 필요해서 추가적으로 이것 저것 찾아보며 탐구해보았는데 완전히 이해는 되지 않았지만 감은 잡았다. 몇 번 더 복습해서 보면 알 것 같은 느낌적인 느낌!!

아, 그리고 그동안 이해되지 않았던 static 드디어 깨우쳤다 ! 유레카다 이거야 ~ 아주 눈물 콧물 기절임

 

저녁 9시에 14기 무엇이든 물어보살이 있었는데 인상적인 말씀을 해주셔서 몇 자 더 적어본다.

 

"돌파력이 있는 개발자" 나는 어떤 개발자가 되고 싶은가? 라는 물음의 답을 찾았다. 돌파력을 가진 개발자가 된다면 개발을 업으로 삼았을 때 참 멋있겠다는 생각을 했다. 그냥 개쩌는 개발자가 되어야지 했었는데 ㅋㅋㅋ 조금 더 멋있는 말로 순화시켜서 말하고 다녀야겠당 ㅋㅋㅋㅋㅋ 👀 

 

아무튼, 오늘도 오.운.공.!!!!!!

---

• 오늘의 목표 :: 아이디어 떠올리고 코드 구현 해보기, 많은 고민 하기, 기초부터 차분히 다져나가기

 

• T.I.L

<자료구조 & 알고리즘>

 

* 검색 알고리즘 

[ 배열에서 검색하기 ]

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색   2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 검색   3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 검색

- 선형 검색 / 순차 검색

: 원하는 키 값을 갖는 요소를 만날때 까지 맨 앞부터 순서대로 전부 검색 → O(N)

종료조건 1, 검색할 값을 발견하지 못하고 배열의 끝까지 갔다?   종료조건 2, 검색할 값을 찾았다!

-  보초법 

: 원하는 키 값을 갖는 요소를 배열의 n+1 번째 요소로 둠

종료조건 1, 검색할 값을 찾았다!

   => 종료 조건을 검사하는 비용을 반으로 줄임

 

- 이진 검색

: 이미 정렬되어 있는 배열에서 검색! → O(logN)

: 찾으려는 key 값과 배열의 중앙값과 비교하여 검색 범위를 줄여나갈 수 있음.

종료조건 1, 배열의 중앙값과 key 값이 일치했다?  종료조건 2, 검색 범위가 더 이상 없다                     => 둘 중에 하나만 만족하면 됨

 

** 복잡도와 증가율

→  1   →   logN   →   N   →   N logN   →   n^2   →    n^3    →    n^k     →     2^n      →

 

 

* Arrays.binarySearch에 의한 이진 검색

java.util.Arrays 클래스의 binarySearch 메서드를 활용!

int[] x = new int[a]; 		// 검색할 배열
int key = n;		  	// 찾고싶은 값

Arrays.binarySearch(x, key); 	// x배열에서 key 값을 찾으면 해당 인덱스 반환
				// 찾지 못하면 삽입포인트 반환 (삽입포인트는 음수)

 

** 자연 정렬로 정렬되지 않은 배열에서 검색하기?

Comparator & Compare 이용

class PhysExamSearch {
    static class PhyscData {
        private String name;     // 신체검사 데이터 저장
        private int height;
        private double vision;

        public PhyscData(String name, int height, double vision) {      // 생성자 만들어주고
            this.name = name;
            this.height = height;
            this.vision = vision;
        }

        @Override
        public String toString() {
            return "name = " + name + ", height = " + height + ", vision = " + vision;
        }

        private static class HeightOrderComparator implements Comparator<PhyscData> {
            @Override
            public int compare(PhyscData o1, PhyscData o2) {
                return Integer.compare(o1.height, o2.height);

//                return (o1.height > o2.height) ? 1 :
//                        (o1.height < o2.height) ? -1 : 0;
            }
        }

        public static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();
    }




    public static void main(String[] args) {
        PhyscData[] x = {
                new PhyscData("홍길동", 169, 1.0),
                new PhyscData("홍길동2", 180, 1.2),
                new PhyscData("홍길동3", 150, 0.3),
                new PhyscData("홍길동4", 170, 0.2),
                new PhyscData("홍길동5", 175, 1.5),
                new PhyscData("홍길동6", 183, 2.0),
        };

        int searchHeight = 183;  // 키가 183인 사람을 찾아주세요!
        
        int idx = Arrays.binarySearch(x,
                new PhyscData("", searchHeight, 0.0),
                PhyscData.HEIGHT_ORDER);

        if ( idx < 0 ) {
            System.out.println("없습니다.");
        } else {
            System.out.println("있습니다. : " + x[idx]);
        }
    }
}

***추가 학습자료 :: https://st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해

 

 

• 오늘 푼 문제

하노이 탑 이동순서 :: https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

좌표 정렬하기2 :: https://www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

통계학 :: https://www.acmicpc.net/problem/2108

2108번: 통계학

 *** 최빈값 구하기 알고리즘 학습필요 ⭐⭐⭐