[항해99 취업 리부트 코스 학습일지] 17일차

(인강) 정렬, 이분 탐색 #

정렬 #

• 시간복잡도 : O(N*logN)
• Comparator 사용 시에는 primitive 타입은 불가능 함
• Array Arrays.sort(arr). Arrays.sort(arr, Collections.reverseOrder())
• Collection Collections.sort(list), Collections.sort(list, Collections.reverseOrder())
• Stream .stream.sorted().toList(), .stream.sorted(Collections.reverseOrder()).toList()

이분 탐색 (Binary Search) #

• 시간 복잡도 : O(logN)
• 정렬 된 컬렉션에서 원하는 값을 빠르게 찾는 방법
• 중간 값을 선택 후 타겟 값과 비교하는 방식
• 파라메트릭 서치에 활용됨

public static void main(String[] args) {
  var arr = new int[]{1, 3, 5, 7, 9, 11, 13, 15, 17, 19};

  System.out.println(binarySearch(arr, 7));
  System.out.println(Arrays.binarySearch(arr, 7));
}

private static int binarySearch(
    int[] arr,
    int target
) {
  int start = 0;
  int end = arr.length - 1;

  while (start <= end) {
    int mid = (start + end) / 2;
    if (arr[mid] == target) {
      return mid;
    } else if (arr[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  throw new IllegalArgumentException("해당되는 값이 없습니다.");
}

연습 문제 #

• 이분탐색 - 1920번: 수찾기
• 이분탐색 (파라메트릭 서치) - 1654번: 랜선 자르기

오늘의 과제 #

1. 11399번: ATM
2. 2805번: 나무 자르기
3. 18870번: 좌표 압축
4. 3079번: 입국심사
5. 2470번: 두 용액
6. 2110번: 공유기 설치
7. 2473번: 세 용액
8. 1202번: 보석 도둑

마지막 정리 #

Q. 오늘 진행된 강의에서 학습한 내용은 무엇인가요? #

• 정렬, 이분탐색
• 파라메트릭 서치

Q. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요? #

• 입력 값은 많은데 제한 시간이 짧을 경우 이진 탐색 관련일 가능성이 높다.
• ATM
  • 그리디 (greedy) 알고리즘
  • 우선순위 큐 사용 시 성능이 더 좋아 질 수 있다.
  • 누적 합 공식
• 입력을 받고 sort하는 것 보다 정렬이 되는 자료형을 사용 하는 것이 시간 복잡도 측면에서 유리하다.
  • 예) 좌표 압축 -> 중복이 있으며, 정렬이 필요 함 -> 힙
• 투 포인터 알고리즘
  • 예) 두 용액
• 많이 쓰이는 알고리즘은 템플릿 형식으로 남겨두면 좋음 (IDE를 쓸 수 있는 코테의 경우 활용 가능)

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

#개발자포트폴리오 #개발자이력서 #개발자취업 #개발자취준 #코딩테스트 #항해99 #취리코 #취업리부트코스 #재취업