Radix sort의 In-Place가 Yes로 되어있지만 No가 맞다. Yes가 되는 정렬도 존재하지만 특수한 경우다. https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations

<aside> 💡 알고리즘은 문제를 해결하기 위해 사용하는 일련의 단계다. 정해진 순서대로 문제를 해결하는 방법이며 줄여서 ‘절차’라고 할 수도 있다. 정렬 알고리즘의 평균 시간복잡도는 $O(nlogn)$ 이상으로 빠를 수 없다.

</aside>

PS 아카이브

알고리즘 용어

• 시간 복잡도

  • 문제를 해결할 때 걸리는 시간

• 공간 복잡도

  • 문제를 해결할 때 점유하는 컴퓨터 메모리의 공간

• 점근적 분석(asymptotic analysis)

  • 알고리즘의 효율성을 수학적으로 판단하는 방법
  • 입력 데이터양의 증가에 따른 처리 시간의 변화율을 뜻한다.
  • 수학적으로 알고리즘 성능의 한계를 증명하는 것으로 점근적 증가율(asymptotic growth rate)을 비교하기 위해 빅 오 표기법을 사용한다.

• 빅 오 표기법

  • 시간이 가장 긴 최악의 경우를 측정하는 것
  • 최상의 경우, 평균의 경우도 있다.

    • 빅 오메가, 리틀 오메가, 리틀 오, 세타 등 다양한 표기법이 존재한다.

    • 빅 오 표기법

      • 최고 차항과 같거나 더 큰 수를 나타낸다.
      • $n^3+n^2+n−1$ 에서 최고 차항은 $n^3$ 이므로, $O(n^3), O(n^5), O(n^{100})$ 모두 맞는 표현 방식이다. 다만 정확한 표현을 위해 최고 차항과 동일하게 표현한다.

    • 빅 오메가 표기법

      • 최고 차항과 같거나 더 작은 수를 나타낸다.
      • 빅 오 표기법 예시에서 $Ω(n^3), Ω(n), Ω(logn)$ 모두 맞는 표현 방식이다.

    • 빅 세타 표기법

      • 최고 차항과 같은 수를 나타낸다.
      • $Θ(n^3)$

    • 이 모든 경우는 n이 무한대로 나아갈 경우를 가정하기 때문에, 앞에 3n이든 100n이든 무한대에서는 의미가 없으므로 더 작은 차항과 상수는 무시하고 최고 차항만 사용한다.

      • $O(1 * 10) = O(10)$

      set x = 0
      for i = 0 ... i < 10
        x += 1
        print(x)
      

      • $O(n)$

      function example(n)
        set x = 0
        for i = 0 ... i < n
          x += 1
          print(x)
      

      • $O(\dfrac{n}{2}) = O(n)$

      set x = 0
      for i = 0 ... i < n / 2
        x += 1
        print(x)
      

      • 약간 어려운 계산식을 표현하자면 다음과 같다.

        • 1번 예시

          • 다음과 같은 함수가 있을 때

          function example(n)
            while 0 > n or n > 100
              if n < 0
                n++
              else
                n--
            return n
          

          • n이 0~100의 범위일 땐 아무 계산도 실행하지 않기 때문에 $O(1)$ 이다.
          • 그리고 n이 매우 큰 숫자일 때, n은 n-100번 실행된다.
          • 따라서 $O(1\times (n-100) = O(n)$ 이다.

        • 2번 예시

          set x = 0
          for i = 0 ... i < n
            for j = 5 ... j < n
                x += 1
                print(x)
          
          for i = 0 ... i < n
              x += 1
          
          print(x)
          

          • $O(n^2)$과 $O(n)$ 이 동시에 존재하지만, 최고 차항만 남기는 규칙으로 인해 위 함수의 시간복잡도는 $O(n^2)$ 이다.
  • 빅 오의 O는 차수(order) 또는 복잡도의 차수(order of complexity)를 뜻한다.
  • 일반적으로 다음처럼 표현할 수 있다. (성능 순)

    • $O(1)$ - 상수 시간

      

      • 상수형 알고리즘으로 데이터 입력량과 무관하게 실행 시간이 일정하다.

        # Array
        nums = [1, 2, 3]
        nums.append(4)    # push to end
        nums.pop()        # pop from end
        nums[0]           # lookup
        nums[1]
        nums[2]
        
        # HashMap / Set
        hashMap = {}
        hashMap["key"] = 10     # insert
        print("key" in hashMap) # lookup
        print(hashMap["key"])   # lookup
        hashMap.pop("key")      # remove
        

    • $O(n)$ - 선형 시간

      

      • 선형 알고리즘으로 데이터 입력량에 비례하여 실행시간이 늘어난다.

      nums = [1, 2, 3]
      sum(nums)           # sum of array
      for n in nums:      # looping
          print(n)
      
      nums.insert(1, 100) # insert middle
      nums.remove(100)    # remove middle
      print(100 in nums)  # search
      
      import heapq
      heapq.heapify(nums) # build heap
      
      # sometimes even nested loops can be O(n)
      # (e.g. monotonic stack or sliding window)
      

    • $O(logn)$ - 로그 시간

      

      • 로그형 알고리즘으로 시간이 선형적으로 증가하면 n이 기하급수적으로 증가한다. 즉 데이터 입력량이 늘어날수록 단위 입력당 실행시간이 줄어든다는 뜻이다.

      # Binary search
      nums = [1, 2, 3, 4, 5]
      target = 6
      l, r = 0, len(nums) - 1
      while l <= r:
          m = (l + r) // 2
          if target < nums[m]:
              r = m - 1
          elif target > nums[m]:
              l = m + 1
          else:
              print(m)
              break
      
      # Binary Search on BST
      def search(root, target):
          if not root:
              return False
          if target < root.val:
              return search(root.left, target)
          elif target > root.val:
              return search(root.right, target)
          else: 
              return True
      
      # Heap Push and Pop
      import heapq
      minHeap = []
      heapq.heappush(minHeap, 5)
      heapq.heappop(minHeap)
      

    • $O(\sqrt{n})$ - 제곱근 시간

      

      # Get all factors of n
      import math
      n = 12
      factors = set()
      for i in range(1, int(math.sqrt(n)) + 1):
          if n % i == 0:
              factors.add(i)
              factors.add(n // i)
      

    • $O(nlogn)$ - 선형 로그 시간

      

      • 선형-로그형 알고리즘으로 데이터 입력량이 n배 늘어나면 실행 시간은 n배 조금 넘게 늘어난다.

      # HeapSort
      import heapq
      nums = [1, 2, 3, 4, 5]
      heapq.heapify(nums)     # O(n)
      while nums:
          heapq.heappop(nums) # O(logn)
      
      # MergeSort (and most built-in sorting functions)
      

    • $O(n\times m)$ - 이중 선형 시간

      

      # Get every pair of elements from two arrays
      nums1, nums2 = [1, 2, 3], [4, 5]
      for i in range(len(nums1)):
          for j in range(len(nums2)):
              print(nums1[i], nums2[j])
      
      # Traverse rectangle grid
      nums = [[1, 2, 3], [4, 5, 6]]
      for i in range(len(nums)):
          for j in range(len(nums[i])):
              print(nums[i][j])
      

    • $O(n^2)$ - n차 시간

      

      • 2차 알고리즘으로 데이터 입력량의 제곱에 비례해서 실행 시간이 늘어난다.

      # Traverse a square grid
      nums = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
      for i in range(len(nums)):
          for j in range(len(nums[i])): 
              print(nums[i][j])
      
      # Get every pair of elements in array
      nums = [1, 2, 3]
      for i in range(len(nums)):
          for j in range(i + 1, len(nums)):
              print(nums[i], nums[j])
      
      # Insertion sort (insert in middle n times -> n^2)
      
      # n^3
      # Get every triplet of elements in array
      nums = [1, 2, 3]
      for i in range(len(nums)):
          for j in range(i + 1, len(nums)):
              for k in range(j + 1, len(nums)):
                  print(nums[i], nums[j], nums[k])
      

    • $O(2^n)$ - 지수 시간

      

      • 지수형 알고리즘으로 데이터 입력이 추가될 때 마다 실행 시간이 2배로 늘어난다.

      # Recursion, tree height n, two branches
      def recursion(i, nums):
          if i == len(nums):
              return 0
          branch1 = recursion(i + 1, nums)
          branch2 = recursion(i + 2, nums)
          
          
      # c^n
      # c branches, where c is sometimes n.
      def recursion(i, nums, c):
          if i == len(nums):
              return 0
          
          for j in range(i, i + c):
              branch = recursion(j + 1, nums)
      

    • $O(n!)$ - 팩토리얼 시간

      

      • 계승(팩토리얼)형 알고리즘으로 데이터 입력이 추가될 때 마다 실행 시간이 n배 늘어난다.

      # Permutations
      def permute(nums):
          def backtrack(path, nums):
              if not nums:
                  res.append(path)
                  return
              for i in range(len(nums)):
                  backtrack(path + [nums[i]], nums[:i] + nums[i + 1:])
          res = []
          backtrack([], nums)
          return res
      

• 빅 오 표기법으로 실제 코드를 계산하는 방법

  • 보통 재귀나 반복문이 코드에 들어가면 여기에 대한 절대적인 연산량을 계산하기란 매우 복잡하기 때문에 통상 빅 오 표기법으로 대략적으로 표기한다.

  • 1회 계산하고 끝나는 것들은 $O(1)$ 이다

    set a = 10
    
    set a = 5
    if a != 10
      print('hello')
    

  • 좀 더 직관적으로 파악하기 위해서 딱 1초 만큼의 제한이 있는 계산기가 있을 때 가능한 계산 범위를 상상해보면 좋다.

    • $N≤10$
      • $O(N!), O(2^N), O(3^N)$
    • $N≤20$
      • $O(2^N)$
    • $N≤100$
      • $O(N^4)$
    • $N≤500$
      • $O(N^3)$
    • $N≤1,000$
      • $O(N^2), O(N^2logN)$
    • $N≤100,000$
      • $O(N), O(NlogN), O(logN), O(1)$
    • 해결하려는 문제의 솔루션이 해당 범위 내에 있지 않은 경우, 다른 솔루션을 탐색해보는 것을 추천한다.
    • 웬만한 단일 for-loop인 경우, 1억번의 반복을 수행하는데 대략적으로 1초가 걸린다고 간주한다.

  • 빅 오 노테이션 시간을 계산하는데 단순히 for 문만 따져서는 안된다.

    function solution(n, m) {
        let sum = 0;
        let visited = Array.from(Array(n), () => Array(m).fill(0));
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= m; j++) {
                if (visited[i][j] === 0) {
                    for (let k = j; k <= m; k++) {
                        visited[i][k] = 1;
                    }
                }
            }
        }
    }
    

    • 간단히 보면 $O(NM^2)$ 처럼 보이지만, if문에 의해 j가 2일 때 부터는 무시된다. 따라서 M의 계산은 $O(M)+O((M−1)×1)=O(M)$ 이므로 $O(NM)$ 이다.

  • 로그 계산법

    function solution(n, count) {
      if (n <= 1) {
        return count;
      }
      return solution(n / 3, count * 3);
    }
    

    • 쉽게 말하자면, n이 1일 경우 결괏값은 3으로 함수가 즉시 종료되고, n이 9일 경우 3번의 함수 호출을 거치고 종료된다.
    • n이 커지면 커질 수록 횟수는 3분의 1 만큼 감소하기 때문에 시행 횟수는 n이 아니다. (로그n)

    호출 횟수	첫 번째 인자 (n)	두 번째 인자 (count)
    1	N	cnt
    2	N / 3	cnt * 3
    3	(N / 3) / 3 = N / 3^2	(cnt * 3) * 3 = cnt * 3^2

    • 위 테이블을 토대로 하면 n번째 재귀 함수의 호출은 $\dfrac{N}{3^{k-1}} = N≤3^{k−1}=log_3​N≤k−1$이다.
    • 따라서 빅 오 노테이션의 상수 무시 규칙에 따라 해당 함수의 시간 복잡도는 $O(logN)$이다.

• 안정(Stable)한 정렬

• In-Place 한 정렬

• Lower Bound와 Upper Bound

기본 알고리즘 개념

• 정렬
• 탐색
• 트리
• 힙
• 그래프