정렬, 이분검색,좌표 정리

정렬,이분검색,좌표 강의를 들으면서 알게 된 것 정리

 

Arrays.stream(arr).sum(); <- 1차원 배열 합 구하기

Arrays.stream(arr).max().getAsInt() <- 배열 최대값

Arrays.stream(arr).min().getAsInt() <- 배열 최소값

if(sum += x > cnt) <-이미 조건에서 sum에 x값이 더해진다 if(sum + x > cnt) 이걸로 비교하자

배열 정렬을 Array.sort(arr) 형태로 쉽게 할 수 있다, 내림차순은 Array.sort(arr, Collections.reverseOrder());

배열 깊은 복사는 int[] arr2 = arr1.clone(); 이렇게 clone 메서드를 이용해서 복사

 pointer impelements Comparable<point> 형태로 사용자가 정렬하고 싶은 방식대로 정렬할 수 있다

 

 

선택정렬 - 인덱스를 잡고 내부 for문 돌고나서 스왑하는 방식

 

버블정렬 - 바깥 for문은 횟수만 세고 내부 for문을  for(int j = 0; j < n-i-1; j++) n-i-1 해줘야한다

 

삽입정렬 - 바깥for문 i는 1부터 시작하고 안쪽 for문 j는 i-1부터 j >= 0까지 감소, 안쪽 for문 나오고 -1까지 감소한

arr[j+1] 자리에 tmp로 잡아둔 arr[i] 값 넣어주기  

중간에 걸리면 break로 나와서 arr[j+1]에 tmp 값 넣어주기

 

LRU - 먼저 캐시를 쭉 돌면서 캐시안에 작업이 있는지 확인하고 있으면

그 인덱스부터 삽입정렬을 이용해서 작업을 당긴 후 맨앞에 작업을 넣고 없으면 전부 뒤로 하나씩 밀고 맨앞에 작업을 넣어주기

 

중복탐색 - 배열 정렬

 

장난꾸러기 - 원래 배열에서 2개의 값이 바뀐 형태, 원래 배열을 깊은복사로 복사한 후 두개를 인덱스 하나하나 비교하기

 

 

좌표 정렬 x,y 등 좌표 두개가 있는 형태의 문제를 풀때 사용 하기위한 좌표 클래스를 만들고

클래스를 생성할떄 pointer impelements Comparable<point> 형태로 Comparable 인터페이스를 받아서

클래스 내부에 compareTo 메서드를 정의한다

오름차순으로 정렬할려먼 return this.x  - o.x; 내림차순으로 정렬하려면 return o.x - this.x; 형태로 리턴값을 주면 된다.

 

이분 검색 - lt, rt 값을 문제를 읽고 잘 잡아서 mid = (lt/rt) /2 ;를 두고 반복문을 돌면서 찾는 값이 mid보다 큰지 작은지를 잘 판단해서 lt와 rt 중 하나 값을 변경해가면서 푸는 방법, 이분 검색은 검색하려는 배열이 정렬된 상태에서만 사용 가능하니

정렬되지 않은 배열이 들어오면 꼭 정렬해주자. O(logN)의 시간 복잡도

반복문은 while(lt <= rt) 로 lt 와 rt가 교차하기 전 까지 돈다

 

뮤직비디오 - 이분검색을 활용한 결정 알고리즘으로 푸는 문제 

결정 알고리즘은 lt, rt를 잘 잡고나서 내부에 cnt 변수를 이용해 특정 카운트를 기준으로 이분 검색을 이용해서 푸는 문제

같다

 

 

 

마구간 정하기 - 위와 비슷한 문제, 문제에서 원하는게 최대값인지 최소값인지에 따라 lt, rt를 어디에 둘지가 바뀌는것 같다.