알고리즘

문제 해결을 위한 단계적인 절차

알고리즘의 조건

• 입력: 0 개 이상 데이터
• 출력: 1개 이상 결과
• 명확성: 순서도나 의사코드도 가능
• 유한성: 반드시 종료
• 효과성: 각 수행단계는 유한시간안에 단순하게 수행 가능해야함

알고리즘 설계 기법⭐️

(20.8)

• 분할정복(Divide&Conquer): 문제를 나눌 수 없을 때까지 나누고, 다시 병합해가며 해결
  • 예: 퀵정렬, 합병정렬, 이진탐색
• 동적계획법(Dynamic Programming): 큰문제를 작은 문제 나누고, 작은 문제들에서 구한 해를 활용해 문제를 해결(Memorization)
  • 예: 최단경로 알고리즘
• 탐욕법(Greedy): 결정을 해야할 때마다 그순간 가장 좋은 선택을 하는 방법
  • 예: 최소비용신장트리 알고리즘(크루스칼, 프림)
• 백트랙킹(Backtrackin): 해가 없으면 이전 단계로 돌아가 다른선택을 하는 방법
  • 예: 깊이우선우선(DFS)

알고리즘 성능 분석

시간복잡도(Time Complexity)

• 알고리즘 수행 시간의 분석 결과
• 표기법: 빅오, 빅오메가, 빅세타

시간복잡도 종류⭐️

• O(1)
  • 상수시간
  • 자료크기와 무관하게 항상 일정한 속도로 작동(20.6)
  • 예: 해시함수
• O(logn)
  • 로그시간
  • 단계수가 logn만큼 필요
  • 예: 이진탐색
• O(n)
  • 선형시간
  • 입력자료를 차례로 하나씩 모두 처리
  • 시간이 입력값에 정비례
  • 예: 순차탐색
• O(nlogn)
  • 선형로그시간
  • 단계수가 nlogn만큼 필요
  • 예: 퀵정렬, 합병정렬(20.6)
• O(n^2)
  • 제곱시간
  • 이중 반복문인 경우
  • 예: 버블정렬, 삽입정렬, 선택정렬
• O(2^n)
  • 지수시간
  • 단계수가 2^n만큼 필요
• O(n!)
  • 펙토리얼시간
  • 단게수가 n!만큼 필요

공간복잡도(Space Complexity)

• 알고리즘 수행 종료까지 필요한 메모리 공간 양
• 주로 변수 저장을 위한 공간

정렬⭐️⭐️

버블 정렬(Bubble Sort)⭐️

• 인접한 두 요소 간 대소 비교
• 뒤에서부터 정렬됨
• 모든 인접값끼리 비교해 비효율적
• O(n^2)

def bubble_sort(arr):
  n = len(arr)
  for i in range(n-1):
      for j in range(0, n-1-i):
          if arr[j] > arr[j+1]:
              arr[j], arr[j+1] = arr[j+1], arr[j]

삽입 정렬(Insertion Sort)

• 정렬을 진행할 인덱스 이전 원소를 탐색하며 알맞은 위치에 삽입
• 앞에서부터 정렬됨
• 자료가 부분적으로 정렬되어있으면 빠름
• O(n^2)

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]

선택 정렬(Selection Sort)⭐️

(20.8)

• 배열에서 최소값을 반복적으로 찾아 정렬
• 앞에서부터 정렬됨
• 비교횟수는 많지만 실제교환횟수는 적음
• O(n^2)

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

퀵 정렬

• 피봇을 기준으로 작은값은 왼쪽, 큰값은 오른쪽으로 분해시키는 방식
• 분할정복과 재귀를 사용해 정렬
• 평균 O(nlogn) 최악 O(n^2)

힙 정렬

• 완전이진트리를 이용한 정렬방식
• 최대힙/최소힙
• 항상 O(nlogn)
• 추가 메모리 필요없음

합병정렬

• 원소가 하나만 남을때까지 분할한 후, 재배열하며 병합해나감
• 분할정복과 재귀를 사용해 정렬
• 항상 O(nlogn)
• 추가적인 메모리 필요

쉘 정렬

• 삽입 정렬의 단점을 개선
• O(n^2)

기수 정렬

• 키값에 따른 버킷에 원소를 분배하고 순서대로 꺼내어 정렬

검색기법

선행검색(Linear Search)

• 배열의 좌측부터 시작해 순차적으로 각 요소 비교
• O(n^2)

이진검색(Binary Search)⭐️

• 검색범위를 반으로 줄여가며 검색
• 주어진 배열은 반드시 정렬되어야함
• O(logn)

def binary_search(arr, target):
	start = 0
    end = len(arr) - 1
    while start <= end:
		mid = (start+end)//2
        if arr[mid] == target:
        	return mid
        elif arr[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1
	return None

보간검색(Interpolation Search)

• 이미 정렬된 리스트에서 검색값이 있을 법한 위치를 예측하여 검색

해싱(Hashing)

• 해시테이블을 사용하여 데이터의 저장위치를 빠르게 찾아 검색
• O(1)

이진트리검색(Binary Tree Searching)

• 이진트리구조를 사용하여 검색범위를 줄여나가며 검색
• 평균 O(logn), 최악 O(n)

블록검색(Block Search)

• 배열을 여러블록으로 나눈 후, 각 블록의 최댓값을 추출하여 찾고자 하는 값의 위치 블록을 파악한 뒤, 해당블록 내엥서 선형 검색을 수행하는 방법