선택 정렬

1. 배열에서 최솟값을 찾는다.
2. 최솟값과 정렬되지 않은 맨 앞의 수와 위치를 바꾼다.
3. 최솟값이 이동한 부분은 고정된다.
4. 고정된 부분 이 후부터 배열을 돌면서 1번부터 반복한다.

선택 정렬 구현(Java) 오름차순

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  
            if (arr[j] < arr[indexMin]) {           
                indexMin = j;  // 최솟 값 찾기
            }
        }
        // 최솟값과 제일 앞의 수를 바꿔 주기
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

선택 정렬 시간 복잡도

이중 for문에서 알 수 있듯이 O(N^2) 이다.

첫 번째 값을 찾기 위해 N번 확인 해야 하고, 두 번째 값을 찾기 위해 N+1번 확인하고.. 반복하면

N+ (N-1) + … + 2 + 1 = N(N+1) 이므로 O(N^2)이 된다.

퀵 정렬

배열을 두 부분으로 나누고, 나뉜 부분을 다시 퀵 정렬 하는 대표적인 *분할 정복 방법을 사용한다.

*분할 정복 방법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

1. 배열에서 하나의 원소를 골라 이 원소를 피벗(pivot)이라고 한다.
2. 피벗 앞에는 피벗보다 작은 원소가, 피벗 뒤에는 피벗보다 큰 원소가 오도록 이동 시킨다.(divide)
3. 피벗 기준으로 좌우 부분에서 재귀적(recursion)으로 1번부터 반복한다.

(책에서는 정렬해야 할 원소들이 알파벳으로 이루어진 이름이라는 것이 명확하여 알파벳 순서대로 반을 나누어 정렬했지만, 숫자를 정렬한다고 생각하면 범위를 알 수 없으니 고정된 기준으로 나눌 순 없고 배열의 원소를 기준으로 잡고 나눠야 한다)

퀵 정렬 구현(Java) 오름차순

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
  }

  private static void quickSort(int[] arr, int start, int end) {
    // start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
    if (start >= end)
      return;
    
    // 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
    int pivot = start;
    int lo = start + 1;
    int hi = end;
    
    // lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
    // 서로 엇갈리게 될 경우 while문 종료
    while (lo <= hi) {
      while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
        lo++;
      while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
        hi--;
      if (lo > hi)				 // 엇갈리면 피벗과 교체
        swap(arr, hi, pivot);
      else
        swap(arr, lo, hi);			 // 엇갈리지 않으면 lo, hi 값 교체 
      }
	
    // 엇갈렸을 경우, 
    // 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
    quickSort(arr, start, hi - 1);
    quickSort(arr, hi + 1, end);

  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

퀵 정렬 시간 복잡도

O(NlogN) - N이 1이 될 때까지 2로 나누는 횟수.

최악의 경우는 O(N^2)이 된다.

1 2 3 4 5 6

(리스트가 불균형하게 나누어 지는 경우 - 정렬하고자 하는 배열이 정렬이 되어 있는 경우)

정렬이 되어 있으면 가운데 수를 선택하면 좋다! 그니까 무조건 가운데를 피벗으로 선택하는게 이득!

선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview (gyoogle.dev)

이진 검색 (binary search)

• 시간복잡도
  • 이분 탐색 : O(logN)
• 정의
  • 항목들을 두 그룹으로 나누고 각 요소를 비교하는 단계를 거치면서 한 쪽 그룹은 다음 고려 대상에서 제외하는 방법
• 특징
  • 오름차순이나 알파벳 순 등으로 이미 정렬되어 있어야 함
  • 분할 정복(Divide and Conquer) 전략의 예
  • 각 단계마다 남아있는 항목이 절반이 됨
  • 작업의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가함
• 구성
  • 단계의 수(비교 횟수)
    • 전체 항목 크기를 2로 나눠 항목 크기가 1에 도달하게 되는 횟수
  • 2를 거듭지곱했을 때 전체 항목의 수가 되도록 하는 지수
• 사례
  • 로그 : 어떤 수를 2로 나눠 1에 도달하기 까지의 횟수 or 2를 거듭제곱해서 그 수까지 도달하기 까지의 횟수
  • 스포츠 경기의 단계별 토너먼트
  <aside> 💡 [예] 약 2만개의 이름이 포함된 전화번호가 있을 때, 20,000은 $2^{14}$(16,384) 와 $2^{15}$(32,768)의 사이에 있기 때문에 14~15번 사이에 특정 전화번호를 찾을 수 있다.
• </aside>

더 알아보기 (요약)

• 설명
  • 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
  • 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.
• 장점
  • 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.
• 단점
  • 검색 원리상 정렬된 리스트에만 사용할 수 있다.
• 의사코드

BinarySearch(A[0..N-1], value, low, high) {
  **if** (high < low)
    **return** -1 *// not found*  
	mid = (low + high) / 2
  **if** (A[mid] > value)
    **return** BinarySearch(A, value, low, mid-1)
  **else** **if** (A[mid] < value)
    **return** BinarySearch(A, value, mid+1, high)
  **else**
    **return** mid *// found*
}

• high와 low를 지정

binarySearch(A[0..N-1], value) {*//k*  
	low = 0
  high = N - 1
  **while** (low <= high) {
      mid = (low + high) / 2
      **if** (A[mid] > value)
          high = mid - 1
      **else** **if** (A[mid] < value)
          low = mid + 1
      **else** 
          **return** mid *// found k*  
	}
  **return** -1 *// not found k*
}

분할 정복(Divide and conquer)

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법
• 예) 퀵정렬 (quick sort), 병합 정렬 (merge sort), 고속 푸리어 변환 (FFT) 문제 등
• 대표적인 사례: 하노이의 탑

장점

• 어려운 문제를 간단하게 해결할 수 있다.

단점

• 스택에 많은 데이터를 담고 있어 스택 오버플로가 발생하거나 메모리를 과하게 사용하게 된다.
• 재귀적으로 많은 함수호출이 이루어지면 오버헤드가 발생할 수 있다.
• 문제를 쪼개는 방법 자체가 상당히 어려울 수 있다.

재귀함수로의 표현

function F(x):
  if F(x)의 문제가 간단 then:
    return F(x)을 직접 계산한 값
  else:
    x를 y1, y2로 분할
    F(y1)과 F(y2)를 호출
    return F(y1), F(y2)로부터 F(x)를 구한 값

빠른 실행이나 문제 해결 순서 선택을 위해, 재귀호출을 사용하지 않고 스택, 큐 등의 자료구조로 분할 정복법을 구현할 수 있다.

참고자료

• Branch and Bound - Binary Search
• 이진 검색 알고리즘
• 분할 정복 알고리즘
• 분할 정복

1. 반에서 가장 키 큰 사람을 찾는 방법

• 한 명씩 물어보면서 키가 제일 큰 사람을 기억하고 다음 사람이 이전에 제일 큰 사람보다 크다면 그 사람을 기억한다. 이 과정을 끝까지 진행하면 가장 큰 사람을 찾을 수 있다.

2. 상황이 복잡해 진다면?

• 가장 키 큰 사람이 두명이라면?
• 가장 같은 키를 많이 가진 수의 사람들을 구한다면?

3. 자료구조의 중요성

• 이 로그에서는 자세히 설명해주지는 않지만 보다 빠르고 편리하게 계산하기 위해서는 적절한 자료구조를 선택해야 한다.
• 배열, 리스트, 맵, 셋 등등 자료구조의 특성과 장단점을 이해하고 사용해야 한다.

4. 예외 처리(멍청한 컴퓨터 말썽 못부리게 하기)

• 평균 값을 구하는 알고리즘을 만들 때 sum이라는 변수에 모든 값을 더한다.
• N이라는 변수에 개수를 구한다.
• 하지만 N이 0개라면? > 컴퓨터는 sum/N을 진행해버리고 0으로 나누는 참사(에러)가 발생할 것이다.
• 따라서 N이 0일 때는 계산을 하지 말라는 예외 처리가 필요하다.

5. 선형 알고리즘

• 처리 시간이 데이터양에 정비례 하는 알고리즘을 의미한다.
• 이 로그에서는 선형 알고리즘만 딱 말했지만 정비례하지 않는 알고리즘이 있을 것이다.
  • for 문을 n만큼 2번 돌면 n의 제곱만큼 계산된다. 이것은 정비례가 아닌 제곱에 비례하는 것이다.

6. 빅-오 표기법

• 책에서는 안알려주는 것 같지만 자주 사용하는 용어이다.
• 가장 높은 차수의 항만 표기하는 것이다.
  • for문을 n+1만큼 2번 돌면 n^2+2n+1만큼 돈다.
  • 이것을 O(n^2)으로 아주 쉽게 표현해주는 것이다.
  • 수학적으로 접근한다면 n이 3일때는 n^2=9, 2n+1=7이다 . 거의 반반씩 비율을 차지하고있다.
  • 하지만 n이 10000이라면? n^2=100000000, 2n+1=20001이다. 0.02% 비율이다.
  • 숫자가 커질 수록 가장 높은 차수의 항만 의미를 가지며 빅-오 표기법을 통해 시간 복잡도의 경향성만 표기하는 것이다.
• O(1) : 데이터 양에 상관없이 처리 시간이 일정함
• O(n) : 데이터 양에 비례하여 처리 시간이 증가
• NLogN, n^2, n^3, 2^n 등등 이 있다.
• 참고로 시간 복잡도를 구하는 방법은 최악의 경우를 생각하는 것이다.
  • n명의 사람 중 유재석를 찾으라고 했을 때 마지막(n) 번째 사람이 유재석인 경우