[TIL] 2024-07-30

중요 학습 내용 [ALGORITHM]

REMIND: scanner vs buffered
scanner: 문자가 입력될 때마다 cpu에서 하나씩 입출력을 한다.
buffered: 버퍼에 일정 용량이 가득 차거나 개행 발생 시(or 인위적 flush), 입출력 처리

Time-complexity

• 상수 시간: O(1)

      private static int getFirst(int[] arr) {
          return arr[0];
      }

• 로그 시간: O(log n)

  private static int binarySearch(int[] arr, int target) {
  
      // 배열을 오름차순 정렬하고 시작
      Arrays.sort(arr);       // 퀵정렬(nlogn), 정렬되었음을 알고리즘 시작 전에 가정
      int left = 0, right = arr.length - 1;
  
      while (left <= right) {
          int mid = left + (right - left) / 2;
          if(arr[mid] == target) {
              return mid;
          } else if (arr[mid] < target) {
              left = mid + 1;
          } else {
              right = mid - 1;
          }
      }
  
      // 찾고자 하는 값이 배열에 없다면 -1을 반환
      return -1;
  }

• 선형 시간 O(n)

      public static int[] reverse(int[] arr) {
          int[] reversed = new int[arr.length];
          for (int i = 0; i < arr.length; i++) {
              reversed[arr.length - 1 - i] = arr[i];
          }
          return reversed;
      }

• 지수 시간 O(2^n)

      public static int fibonacci(int n) {
          if(n <= 1) return n;
          return fibonacci(n - 1) + fibonacci(n - 2);
      }

sorting

• Bubble sorting(버블 정렬)

  • 인접한 두 데이터를 비교하여 swap하는 로직을 반복
  • 시간 복잡도: O(n^2)

• Selected sotring(선택 정렬)

  • 대상 데이터에서 최대나 최소 데이터를 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법
  • 시간 복잡도: O(n^2)

• Insert sorting(삽입 정렬)

  • 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식
  • 시간 복잡도: O(n^2)

• Quick sorting(퀵 정렬)

  • 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해서 정렬
  • 내부적으로 가장 많이 사용되는 알고리즘
  • 재귀 호출을 사용하여 하나의 연산이 마무리된 이후 다음 연산을 진행
  • 시간 복잡도: O(nlogn)

• Merge Sort(병합 정렬)

  • 데이터를 분할하고 분할한 집합을 정렬해서 합치는 방식(분할 정복 방식)으로 정렬
  • 시간 복잡도: O(logn)