오늘은 정렬, 이분탐색을 배웠다. 근데 충격적인 건 이분 탐색인 줄 알고 풀었던 문제가 사실은 파라매트릭 서치 문제였다는 거... 기술 매니저님께서 대부분 upper bound 케이스였다고 하셨다. 신기하다!
기술 매니저님께 피드백 받고, 팀 스터디 진행하면서 배워가는 게 많다! 모두 감사드립니다~ 나도 더 열심히 공부해야겠다!
- 오늘 진행된 강의에서 학습한 내용은 무엇인가요?
정렬, 이분 탐색
- 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?
강의 내용 정리
자바 정렬 O(NlogN)
병합, 삽입 정렬이 섞인 Tim sort를 내부적으로 사용
Comparator 인터페이스에서 Generic을 사용하기 때문에 Comparator 을 사용하는 경우 (예를 들어 역순) primitive 타입은 불가 (박싱 필요)
Arrays.sort(arr, Collections.reverseOrder());
Arrays.toString(arr);
새로운 array를 반환받고 싶으면 stream을 사용해라
list.stream().sorted().toList();
이분탐색
- 정렬된 리스트, 특정 값 위치 찾는 탐색 알고리즘
- 시간복잡도 O(logN)
- Arrays.binarySearch(arr, target)
절반씩 줄여가면서 검사하니까 log n
Arrays.sort()
배열의 타입 primitive ->n^2 일 수 있음
래퍼클래스 타입이면 nlogn
https://codingnojam.tistory.com/38
파라매트릭 서치 (Parametric Search)
- 정의: 파라매트릭 서치는 이진 탐색을 응용하여 최적화 문제를 해결하는 기법입니다. 주어진 조건을 만족하는 최적의 값을 찾기 위해 이진 탐색을 사용합니다.
- 작동 방식: 시작 인덱스, 중간 인덱스, 끝 인덱스를 사용하여 리스트 내 특정 값을 찾습니다. 조건을 만족하는 후보 답의 범위를 조정해 가며 최적의 값을 찾아갑니다.
- 사용 예시: 최대 무게를 견딜 수 있는 다리에 트럭이 건널 수 있는지 여부를 판단하는 문제 등에서 사용될 수 있습니다.
Upper Bound와 Lower Bound
- Upper Bound: 정렬된 배열에서 주어진 키(key)보다 큰 값 중 가장 작은 값의 위치를 찾는 알고리즘입니다. 즉, 키보다 큰 첫 번째 위치를 반환합니다.
- Lower Bound: 정렬된 배열에서 주어진 키(key)보다 크거나 같은 값 중 가장 작은 값의 위치를 찾는 알고리즘입니다. 즉, 키보다 크거나 같은 첫 번째 위치를 반환합니다.
- 사용 방법: 이진 탐색을 활용하여 구현되며, 배열에서 특정 값의 상한선이나 하한선을 찾을 때 사용됩니다.
트리맵의 주요 연산 시간 복잡도
- 삽입(Insertion): 트리맵에 새로운 키-값 쌍을 삽입하는 연산의 시간 복잡도는 O(log n) 입니다.
- 삭제(Deletion): 특정 키-값 쌍을 트리맵에서 삭제하는 연산의 시간 복잡도 역시 O(log n) 입니다.
- 검색(Search): 트리맵에서 특정 키를 가진 값을 찾는 연산의 시간 복잡도는 O(log n) 입니다.
- 순회(Traversal): 트리맵의 모든 요소를 순회하는 연산의 시간 복잡도는 O(n) 입니다. 트리의 모든 노드를 방문해야 하기 때문입니다.
List<Integer> sortedList = new ArrayList<>(a);
List<Integer> list = new ArrayList<>(new LinkedHashSet<>(sortedList));
이렇게 변환하는 과정에서 시간이 오래 걸릴 수 있음 -> 조심해서 사용해라
원소가 백만개 있으면 set -> list 옮기는 과정이니까
중복제거 하는 방법
Stream API를 사용하여 배열 또는 리스트에서 중복을 제거할 수 있습니다. distinct() 메소드를 활용하여 중복된 요소를 제거하고, 필요한 경우 다시 배열이나 리스트로 변환할 수 있습니다. 예를 들어, int[] arr = Arrays.stream(arr).distinct().toArray();와 같이 사용할 수 있습니다
indexOf() -> O(n)
원소 위치 O(1)로 찾는 방법 고안해보기
- hashmap 사용
메소드마다 시간 복잡도가 어떻게 되는지 확인해봐라
contains() 오래 걸림
숫자 커보인다 싶으면 모두 long 으로 해라!
스트림 API와 for문의 차이점
스트림 API의 오버헤드: 스트림 API는 함수형 프로그래밍 언어의 시퀀스에 해당하는 개념으로, 추가적인 오버헤드가 발생합니다. 이는 스트림의 각 요소가 하나의 스트림 형태로 작동하기 때문입니다.
성능 차이의 상황적 의미: 데이터 양이 많고, 함수 내의 시간 복잡도가 충분히 클 경우, for문과 스트림 사이의 속도 차이는 거의 무시할 수 있습니다. 따라서, 이러한 상황에서는 두 방법 사이의 선택이 큰 의미를 가지지 않습니다.
댓글