4주차 알고리즘

선형 탐색과 이진 탐색

💡 검색이나 정렬과 같은 문제를 푸는 알고리즘을 배워보겠습니다. 먼저 주어진 배열 속에서 특정 값을 찾는 방법부터 시작해봅니다.

• 선형 탐색 (Linear Search)

  배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사한다.

  효율성 그리고 비효율성: 선형 탐색 알고리즘은 정확하지만 아주 효율적이지 못한 방법이다.

  최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행된다. (최악의 상황 = 찾는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우 / 반대로 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우)

  선형 탐색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다. 이러한 경우 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적이다.

  // 선형 탐색 의사코드
  For i from 0 to n–1
      If i'th element is 50
          Return true
  Return false // loop를 다 돌았는데 없다면 false

• 이진 탐색 (Binary Search)

  배열이 정렬되어 있을 경우에만 사용 가능하다.

  만약 배열이 [오름차순으로] 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복한다.

  // 이진 탐색 의사코드
  If no items // 더 이상 배열 값이 없을 경우
      Return false
  
  If middle item is 50
      Return true
  
  Else if 50 < middle item
      Search left half
  
  Else if middle item < 50
      Search right half

• 항상 이진 탐색이 선형 탐색보다 더 좋다고 할 수는 없다. 이진 탐색을 하려면 먼저 정렬을 해야 하기 때문에 시간이 들기 때문이다.

  상황에 따라 다른데, 여러번 확인해야 하는 경우는 이진 탐색이, 몇 번만 보면 되는 경우엔 선형 탐색이 더 빠를 수도 있다.

실행 시간 표기법 - Big O, Big Ω

💡 처리하는 데이터가 많아지고 처리하는 작업이 복잡해질수록 실행 시간은 매우 중요해집니다. 특정 알고리즘을 작성하였을 때 그 실행 시간을 표기하는 방법을 배워보겠습니다.

• Big-O : 실행 시간, 알고리즘을 수행하는 데 필요한 시간의 상한선 / 최악의 경우에 필요한 상한선

  

  O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것

  실행시간의 상한

  O(n^2) - 버블 정렬, 선택 정렬
  O(n log n) - 병합 정렬
  O(n) - 선형 탐색
  O(log n) - 이진 탐색
  O(1)

  👉 밑으로 내려갈 수록 속도 빠름, 맨 위가 가장 느림

• Big-Ω : 반대로 Big Ω는 알고리즘 실행 시간의 하한선 / 최선의 경우의 (운이 좋은 경우) 하한선

  실행시간의 하한

  Ω(n^2) - 선택 정렬
  Ω(n log n) - 병합 정렬
  Ω(n) - 버블 정렬, ex.상자의 개수를 셀 때
  Ω(log n)
  Ω(1) - 선형 탐색, 이진 탐색

  선형 탐색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이지만, 운이 좋으면 1번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 된다. 이진 탐색도 마찬가지이다.

• Ω보다는 O이 좋은 것이 좋은 알고리즘이다[실행시간의 상한이 낮은 알고리즘이 하한이 낮은 알고리즘보다 더 좋다.] 최악의 경우 or 평균적으로 어떻게 동작할 지를 걱정하기 때문

버블 정렬 [Bubble Sort]

// 버블 정렬 의사코드
Repeat n–1 times // 바깥쪽 loop
    For i from 0 to n–2 // 안쪽 loop
        If i'th and i+1'th elements out of order
            Swap them

중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로 (n-1)*(n-2) = n^2-3n+2번의 비교 및 교환이 필요합니다.

여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있습니다.

버블 정렬은 무식해서, 정렬이 돼있어도 중간에 탈출하는 것 없이 처음부터 끝까지 루프를 돌며 비교하므로, 위의 의사 코드에 한해서는 버블 정렬의 실행 시간의 하한도 역시 Ω(n^2)이 됩니다. [실제 버블 정렬의 하한은 Ω(n), 뒤에 나오는 실행 시간 줄이기 참고]

https://bowbowbow.tistory.com/10 ← 추가로 꼭 읽어보기

선택 정렬 [Selection Sort]

배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.

For i from 0 to n–1 // 바깥 루프, 처음부터 순서대로 방문
    Find smallest item between i'th item and last item // 안쪽 루프, 가장 작은 값을 찾음, i~(n-1)
    Swap smallest item with i'th item // 안쪽 루프가 끝나면 인덱스 i의 값과 smallest 값을 swap

ex. 6 3 8 5 2 7 4 1 "가장 작은 수"를 기준으로 한다면, 처음부터 끝까지 확인하면서 smallest 변수에 가장 작은 수를 저장합니다. 도중에 smallest 값보다 작은 수를 발견하면 그 수를 smallest에 저장합니다. → n회

끝까지 1회 돈 뒤에 smallest에 해당하는 값을 맨 앞의 값과 위치를 바꿉니다.[swap] 1 3 8 5 2 7 4 6

이제 두 번째부터 끝까지 돌면서 그 중의 smallest 값을 찾습니다. 앞의 방식과 동일. 1 2 8 5 3 7 4 6 → (n-1)회

결국 선택 정렬은 n + (n-1) + (n-2) + ... + 1 회 실행하므로, 부분합 공식에 따라 n(n+1)/2 회 실행합니다.

따라서 실행 시간의 상한은 O(n^2)가 됩니다. 마찬가지로 하한도 Ω(n^2)가 됩니다. 정렬여부에 관계없이 전부 다 돌아야 smallest(or largest) 값을 찾을 수 있기 때문입니다.

버블 정렬 알고리즘의 실행 시간 줄이기

// 버블 정렬 의사코드 수정
Repeat **until no swaps**
    For i from 0 to n–2
        If i'th and i+1'th elements out of order
            Swap them

안쪽 루프에서 만약 교환이 하나도 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황일 것입니다.

따라서 바깥쪽 루프를 ‘교환이 일어나지 않을때’까지만 수행하도록 하면 실행 시간을 줄일 수 있습니다.

처음부터 정렬이 다 되어있는 경우 n-1번만[n에 가까움] 실행하므로 최종적인 버블 정렬의 하한은 Ω(n)이 됩니다.

상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것이죠.

[참고] 선택 정렬의 실행 시간 하한선을 더 줄이는 것은 불가능하다. 선택 정렬의 하한은 Ω(n^2)

재귀

함수가 본인 스스로를 호출해서 사용하는 것

병합 정렬 [Merge Sort]

• 가장 작은 부분 (숫자 1개)으로 나눠진 결과 [크기가 1인 배열]
• 숫자 1개씩을 정렬하여 병합한 결과 [크기가 2인 배열]
• 숫자 2개씩을 정렬하여 병합한 결과 [크기가 4인 배열]
• 마지막으로 숫자 4개씩을 정렬하여 병합한 결과 [크기가 8인 배열]

병합 정렬 실행 시간의 상한은 O(n log n) 입니다.

숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문입니다.

실행 시간의 하한도 역시 Ω(n log n) 입니다. 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문입니다.

Big-θ

어떤 알고리즘의 상한선과 하한선이 같을 때 사용함. 실행 시간의 표기법 중 하나.

θ(n^2) - 선택 정렬
θ(n log n) - 병합 정렬