1. 🍎 문제 2. 🤔 접근 구현해야 되는 작업은 다음 3가지이다. 또한 주어진 인덱스는 1부터 시작하는 것에 주의한다. 1. 배열을 i부터 j까지 자른다. 2. 자른 배열을 정렬한다. 3. k번째 요소를 answer 배열에 추가한다. 3. 💡 구현 1. 배열 자르기 | Arrays.copyOfRange ( 원본 배열, 시작인덱스(inclusive), 끝 인덱스(exclusive) ) copyOfRange 함수를 사용하면 원하는 인덱스만큼 배열을 카피할 수 있다. // 배열 자르기 int [] sliceArray = Arrays.copyOfRange(array, commands[t][0]-1, commands[t][1]); 2. 정렬 | Arrays.sort() sort 함수를 사용하면 오름차순 정렬을 ..

Arrays.sort() 배열을 정렬하는데 사용 ('int [] ', 'String []' 등) 기본 데이터 타입 배열, 객체 배열 모두에 사용 가능 주어진 배열 직접 변경 Collections.sort() 컬렉션을 정렬하는 데 사용('List', 'Set' 등) 주어진 컬렉션을 직접 변경 둘 다 Comparable 인터페이스나 Comparator 인터페이스 중 하나를 구현하고 있어야 한다. 이 둘의 차이는 무엇일까? 알아본다. Comparable 인터페이스 객체가 자연스러운 순서를 갖도록 하는 것이 목표 객체 자체가 비교 로직을 구현 `compareTo` 메소드 제공해야함 메소드는 현재 객체가 다른 객체보다 작으먄 음수, 같은 0, 크면 양수를 반환해야 함 List people = new ArrayLi..

알고리즘 퀵 정렬은 기준값(pivot)을 선정해 해당 값도가 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 평균적인 시간 복잡도는 O(nlogn)으로 다른 O(nlogn)의 알고리즘 중 가장 빠르다고 평가 된다. 구체적인 내용 기준점을 정하고 기준점을 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 이동 시키며 정렬을 진행 한다. 이때 기준점이 되는 레코드는 한 번 정렬이 완료되면 더 이상 자리가 바뀌지 않는다. partition 함수를 통해 피봇을 기준으로 왼쪽, 오른쪽을 나누게 된다. 최종적으로 피봇의 위치는 low가 higt보다 커지는 순간으로 결정된다. 이렇게 피봇을 기준으로 한 번 정렬된 리스트는 다시 왼쪽, 오르쪽 리스트로 쪼개져 partition 함수를 호출하며 리스..

알고리즘 개념 인접한 2개의 레코드를 비교하며 정렬 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환 1회전이 돌때 마다 정렬이 완료된 레코드가 가장 오른쪽에 1개씩 추가됨 코드 - Java // buble sort for(int i = N-1; i >=0 ; i--) { int chage = 0; for(int j=0; j arr[j+1]) { chage++; int tem = arr[j]; arr[j] = arr[j+1]; arr[j+1]= tem; } } if(chage == 0) break; } 시간 복잡도 분석 비교 횟수 (n-1) + (n-2) .. 2 + 1 = (n * (n+1)) / 2 시간 복잡도: O(n^2) 최선, 평균, 최악 모두 같다. 이동 횟수 최악의 ..

선택 정렬 개념 제자리 정렬 (in-place sorting)이다. 입력 배열 외에는 추가 메모리를 요구하지 않는 정렬이다. 정렬된 해당 요소가 넣어질 위치가 정해져 있다. 자료 이동 횟수가 미리 결정된다. → n-2번 구체적인 설명 선택 정렬이란 첫 번째 위치부터 차례대로 정렬이 안된 요소 중 가장 작은 것(큰 것)을 선택하여 위치를 교환하여 점점 정렬을 완료해나가는 기법이다. 첫번째 루프일 때 첫번 째 요소를 두번 째 요소부터 마지막 요소까지 비교하여 가장 작은 값을 찾으면 해당 요소와 교환한다. 두번 째 루프일 때 두번 째 자료를 세번 째 요소 부터 마지막 요소까지 비교하여 가장 작은 요소를 찾으면 해당 요소와 교환한다. 이렇게 n-1 요소까지 반복한다. 시간 복잡도 비교 횟수 (n-1) + (n-..