알고리즘 총 정리

데이터분석/CS 기초

알고리즘 총 정리

neonii 2025. 2. 21. 14:14

728x90

알고리즘 표현 방법

순서도 flow chart: 문제 해결 과정을 기호와 도형을 사용하여 표현
의사 코드 pseudocode: 프로그램 명령문 형식을 취하고 각 명령을 사람이 이해하기 쉬운 단어로 나타냄
자연어 natural language

알고리즘 성능 평가

성능 측정: 실제 구현 필요, 구체적으로 실행해 시간을 확인
- 하드웨어/운영체제/언어/컴파일러 등 실행 환경에 따라 달라짐
성능 분석: 실제 구현 불필요
- 시간 복잡도: 연산의 실행 횟수를 데이터 크기에 관한 함수로 표현. 최고차항의 차수 만으로 표시
  - Big-O 표기법: worst case analysis
  - Big-Omega 표기법: best case analysis
  - Big-Theta 표기법: 최악의 경우와 최선의 경우 모두 적
- 공간 복잡도: 메모리가 많이 저렴해져서 공간 복잡도보다는 시간 복잡도가 중요함

점화식 Recurrence Relation 풀이

반복 대치 repeated substitution: 더 작은 문제에 대한 함수로 반복해서 대치
추정 후 증명: 결론을 추정하고 참이라 가정한 후, 수학적 귀납법을 이용하여 증명
마스터 정리: 형식에 맞는 점화식의 복잡도는 복잡한 계산이나 증명 없이 바로 알 수 있음

정렬 알고리즘

내부 정렬: 입력 데이터 크기가 작을 때 주 기억 장치 내에 저장한 자료를 대상으로 정렬하는 방법
- 선택 정렬 selection sort
  - 원소 하나 남을 때까지 반복: 최대 원소를 찾음 → 맨 오른쪽 원소를 교환 → 맨 오른쪽 원소를 제외
  - input insensitive 알고리즘: 입력이 정렬되어 있는 정도와 무관하게 항상 일정한 시간 복잡도
  - 시간 복잡도: O(n^2)
- 버블 정렬 bubble sort
  - 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복
  - 시간 복잡도: O(n^2)
- 삽입 정렬 insertion sort
  - 새로운 데이터를 정렬된 데이터에 삽입하는 과정을 반복
  - input sensitive 알고리즘: 입력의 상태에 따라 수행시간이 달라질 수 있음
  - 시간 복잡도: O(n^2)
- 내부 병합 정렬 merge sort
  - 정렬할 데이터들을 2개로 나누고 각각 정렬한 다음, 다시 합병하여 하나의 정렬된 데이터로 완성
  - 시간 복잡도: O(nlogn)
- 쉘 정렬 shell sort
  - 주어진 입력 데이터를 적당한 매개 변수의 값만큼 떨어진 데이터들과 비교하여 교환하는 과정을 반복
  - 각 그룹을 동시에 정렬할 수 있어 병렬 처리가 가능한 알고리즘
  - 시간 복잡도: O(n^2)
- 퀵 정렬 quick sort
  - 기준 키를 기준으로 작거나 같은 값은 앞으로, 큰 값은 뒤로 가도록 분리하여 정렬
  - 현장에서 가장 많이 쓰는 정렬 알고리즘!
  - 시간 복잡도: O(n^2)
- 힙 정렬 heap sort
  - 주어진 배열을 힙으로 만든 다음 차례로 하나씩 힙에서 제거
  - 힙 heap: 완전 이진 트리 (i.e. 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 채워져 있음), 각 노드의 값은 자식의 값보다 작거나 같음
  - 시간 복잡도: O(nlogn)
- 내부 기수 정렬 radix sort
  - 제한적인 범위 내에 있는 숫자에 대해서 각 자릿수 별로 정렬
  - stable sort: 값이 같은 원소끼리는 정렬 후에도 원래의 순서가 바뀌지 않음
  - 시간 복잡도: O(n)
- 계수 정렬 counting sort
  - 각 데이터가 등장한 횟수를 세서 그 기준으로 정렬
  - 비교 정렬이 아님
  - 시간 복잡도: O(n)
외부 정렬: 입력 데이터 크기가 주 기억 장치 공간보다 큰 경우, 보조 기억 장치에 우선 저장하고, 여러 번에 나누어 주 기억 장치에 읽어들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복.
- 외부 병합 정렬
- 외부 기수 정렬

탐색 알고리즘

탐색 키 search key: 각 레코드 record를 대표, 하나 이상의 필드 field로 구성 가능
순차 탐색 sequential search = 선형 탐색 linear search
- 첫 번째 데이터부터 차례로 비교
- 시간 복잡도: O(n)
자기 구성 순차 탐색 self-organizing sequential search
- 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치하여 순차 탐색의 검색 효율을 높임
- 전진 이동법 move to front: 탐색된 항목을 데이터 집합의 가장 앞으로 이동
- 전위법 transpose: 탐색된 항목을 바로 이전 항목과 교환
- 빈도 계수법 frequency count: 각 항목이 탐색된 횟수를 별도의 공간에 저장해두고 탐색된 횟수가 높은 순으로 데이터 집합 재구성
이진 탐색 binary search
- 정렬된 데이터 집합을 이분화하면서 탐색
- 시간 복잡도: O(logn)

효율적인 탐색을 위한 자료구조

탐색 트리 search tree
- 내부 탐색 트리: 주 기억 장치가 전체 키를 수용할 수 있어, 탐색 트리가 주 기억 장치 내에 존재함
  - 이진 탐색 트리 binary search tree
    - 이진 트리(왼쪽 자식 < 부모 < 오른쪽 자식)이면서 같은 값을 갖는 노드가 없어야 함
    - 좌우 균형이 잘 맞으면 탐색의 효율이 높음
    - 시간 복잡도: O(h) 이때 h는 트리의 높이, 최악의 경우 (사향 이진 트리) O(n)
    - 데이터의 탐색
      - 루트 노드부터 시작
      - 노드와 찾으려는 데이터가 같으면 탐색은 성공적으로 종료됨
        노드가 찾으려는 데이터보다 작으면 오른쪽 서브 트리를 탐색함
        노드가 찾으려는 데이터보다 크면 왼쪽 서브 트리를 탐색함
    - 데이터의 삽입
      - 탐색에 성공하면 삽입은 실패함. 같은 데이터를 갖는 노드가 있을 수 없기 때문
      - 탐색과 비슷한 알고리즘으로 이동하여 삽입
    - 데이터의 삭제
      - 삭제하고자 하는 노드가 리프 노드인 경우, 그냥 삭제
      - 삭제하고자 하는 노드의 자식 노드가 한 개인 경우, 삭제하고자 하는 노드의 부모가 삭제하고자 하는 노드의 자식을 직접 가리키도록 함
      - 삭제하고자 하는 노드의 자식 노드가 두 개인 경우, 삭제하고자 하는 노드의 오른쪽 서브 트리의 최소 원소 노드를 삭제하고 삭제한 노드를 삭제하고자 하는 노드의 자리에 놓음
  - 균형 트리 balanced tree - 레드 블랙 트리
    - 이진 탐색 트리에 삽입과 삭제 후 스스로 균형을 유지하는 기능 추가
      - 각 노드는 레드나 블랙
      - 루트는 블랙
      - 모든 리프는 블랙
      - 레드 노드는 연속적으로 나타나지 않음
      - 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같음
    - 시간 복잡도: O(logn)
  - 해시 테이블 hash table
    - 저장된 자료와 비교하여 자리를 찾지 않고 단 한 번의 계산으로 자리를 찾음
    - 해시 함수 hash function: 입력 원소가 해시 테이블에 골고루 저장될 수 있도록 해야 함
      - 나누기 방법 division method: h(x) = x mod (해시 테이블 사이즈)
      - 곱하기 방법 multiplication method: h(x) = (xA mod 1) * (해시 테이블 사이즈), 이때 A는 0
      - 중간 제곱법 mid-square: 키 값을 제곱한 후에 그 결과의 중간에 있는 적당한 수의 비트를 취하여 버켓 주소로 하는 것
      - 접지법 folding: 종이를 접듯이 숫자를 접어 일정한 크기 이하의 수로 만드는 방법
    - 시간 복잡도: O(1)
- 외부 탐색 트리: 주 기억 장치가 전체 키를 수용할 수 없어, 탐색 트리가 보조 기억 장치에 존재함
  - B 트리
    - 다진 검색 트리: 루트를 제외한 모든 노드가 k/2개 이상 k개 이하의 key를 가짐
    - 데이터의 탐색
      - key가 정렬된 상태로 저장되어 있으므로, 찾으려는 데이터 값과 비교하여 데이터가 포함된 범위로 내려감 (e.g. key가 10, 20, 30인 경우 내가 찾는 값이 25라면 20과 30 사이의 자식 노드로 내려감)
    - 데이터의 삽입
      - 삽입할 위치에 공간의 여유가 없다면 형제 노드가 key 하나 넘긴 후 삽입. 만약 형제 노드에도 공간의 여유가 없다면 가운데 key를 부모 노드로 넘기고 노드를 두 개로 분리
    - 데이터의 삭제
      - 제거 후 노드에 underflow 발생하면 key를 가져올 수 있는 형제 노드 있는지 확인. 없다면 형제 노드와 병합

그래프 이론

오일러 경로 euler path: 모든 간선들을 정확히 한 번씩만 경유하는 경로
- 필요충분조건
  - 연결 그래프
  - 모든 정점의 차수가 짝수 (단, 홀수 차수인 정점이 2개인 그래프는 한쪽을 출발점 나머지 한쪽을 도착점으로 하면 한 붓 그리기 가능함)
오일러 사이클 euler cycle: 시작점과 끝점이 같은 오일러 경로
해밀턴 경로 hamilton path: 모든 정점들을 정확히 한 번만 경유하는 경로
해밀턴 사이클 hamilton cycle: 시작점과 끝점이 같은 해밀턴 경로

그래프 순회 Graph Traversal

그래프 내의 모든 정점을 방문하는 방법
너비 우선 탐색 Breath First Search BFS
- 동심원의 형태로 차례로 퍼져나가면서 방문
- 큐를 이용해 구현
- 최단 경로 구할 때 활용
깊이 우선 탐색 Depth First Search DFS
- 한 방향으로 갈 수 있는 곳까지 깊이 탐색
- 스택이나 재귀함수를 이용해서 구현
- 사이클 방지와 위상 정렬에서 활용

위상 정렬 Topological Sorting

유향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점들을 나열하는 것
여러 답이 나올 수 있음
비순환 방향 그래프 DAG directed acyclic graph에만 적용할 수 있음
시간 복잡도: Theta(|V| + |E|)

최단 경로 구하기 Shortest Path

두 정점 사이를 연결하는 경로 중 가장 짧은 경로를 찾음
주요 개념
- 최적 부분 구조 optimal substructure: 최단 경로의 부분 경로는 역시 최단 경로
- 간선 이완: edge relaxation: 현재 경로 값보다 더 적은 경로가 존재한다면 값을 변경함
어떤 알고리즘을 사용해야 하는가?
- 다익스트라 알고리즘
  - 단일 쌍 최단 경로 single-source & single-destination 또는 단일 출발 최단 경로 single-source 이면서
    모든 간선 가중치가 음이 아닌 경우
  - 다양한 자료구조를 통해 구현할 수 있지만, 우선 순위 큐를 활용하면 비용을 줄일 수 있음
  - 우선 순위 큐를 활용한다면 시간 복잡도: O(|E| log|V|)
  - 그리디 알고리즘
    1. 시작 정점에서 각 정점으로 이르는 경로의 길이를 저장할 배열을 준비하고, 무한대로 초기화
    2. 시작 정점에서 시작 정점까지의 경로 길이를 0으로 초기화하고 최단 경로에 추가
    3. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고, 이들을 최단 경로에 추가
      - 만약 추가하려는 인접 정점이 이미 최단 경로에 속해 있고 새로 갱신하려는 경로가 더 짧다면, 기존 경로를 현재 정점을 경유하도록 수정
    4. 그래프 내의 모든 정점이 최단 경로에 속할 때까지 3을 반복
- 플로이드 와샬 알고리즘
  - 전체 쌍 최단 경로 all-pairs 인 경우 (단일 쌍, 단일 출발, 단일 도착에서도 사용할 수 있으나 비효율적)
  - 반복문을 3번 중첩해서 구현
  - 시간 복잡도: O(|V|^3)
  - 동적 계획법
    1. 모든 정점에서 모든 정점으로 이르는 경로의 길이를 저장할 행렬을 준비하고, 무한대로 초기화
    2. 자기 자신으로 가는 경로의 길이는 0으로 설정
    3. 각 간선의 가중치를 활용해 직접 연결된 정점들의 경로 길이를 초기화
    4. 각 정점을 경유지로 사용하며 모든 정점 쌍의 경로 길이를 더 짧은 경로로 갱신
- 벨만-포드 알고리즘
  - 음의 가중치를 가진 간선이 존재하는 경우 (그래도 가중치의 합이 음인 사이클은 허용하지 않음, 해당 사이클을 무한반복하게 될 수 있기 때문)
  - 알고리즘
    1. 시작 정점에서 각 정점으로 이르는 경로의 길이를 저장할 배열을 준비하고, 무한대로 초기화
    2. 시작 정점에서 시작 정점까지의 경로 길이를 0으로 설정
    3. 모든 정점에 대해 각 간선을 확인하여 더 짧은 경로가 있으면 갱신
      - 음수 가중치가 있는 경우, (V-1)번 반복 후에도 경로가 갱신되면 음수 사이클이 존재한다고 판단
    4. 최단 경로가 갱신되지 않을 때까지 반복하면 최단 거리 완성
단일 시작점으로부터 각 정점에 이르는 최단 경로를 구하는 single source shortes path problem,
모든 정점 쌍에 대하여 최단 경로를 구하는 all pairs shortest path problem에서 활용

트리 순회 Tree Traversal

트리 내의 모든 노드를 한 번씩 방문하는 방법 (i.e. 사이클이 없고 각 정점을 한 번씩만 방문하는 그래프 순회)
전위 순회 preorder traversal: 루트 → 왼쪽 서브 트리 → 오른쪽 서브 트리
중위 순회 inorder traversal = 대칭 순회 symmetric traversal: 왼쪽 서브 트리 → 루트 → 오른쪽 서브 트리
후위 순회 postorder traversal: 왼쪽 서브 트리 → 오른쪽 서브 트리 → 루트

최소 신장 트리 Minimum Spanning Tree

신장 트리: 그래프 G = (V, E)의 정점 집합 V는 그대로 가져오고, 간선을 |V|-1개만 남겨 트리가 되도록 만든 것
최소 신장 트리: 무향 연결 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리
프림 알고리즘
- 정점과 연결된 모든 간선들 중 가중치가 가장 작은 간선을 선택
- 시간 복잡도: O(|E|log|V|)
크루스칼 알고리즘
- 정점과 연결되어 있지 않은 간선이라도 가장 작은 간선을 선택:
  프림 알고리즘처럼 하나의 트리를 키워나가는 방식이 아니라, 여러 개의 트리로 구성된 숲에서 하나의 트리로 변해가는 방
- 시간 복잡도: O(|E|log|V|)

그리디 알고리즘

매 순간, 최선의 선택을 하는 방식으로 최적의 해를 찾는 알고리즘
빠르고 간단한 방법이지만, 항상 최적해를 보장하지는 않음

문자열 매칭 String Matching

텍스트 문자열 A[1 ... n]이 패턴 문자열 P[1 ... m]을 포함하고 있는지 알아보는 것
원시적인 매칭: 본문의 길이가 n, 패턴의 길이가 m이라고 하면 n*m번의 비교를 수행해야 하므로 느림
오토마타를 이용한 매칭: 한 글자씩 이동하면서도 불일치 시 불필요한 재비교를 하지 않도록 적절한 상태로 점프하여 효율적으로 탐색하는 방식
라빈-카프 Rabin-Karp 알고리즘
- 문자열을 해시값(숫자)으로 변환하여 빠르게 비교하는 방식
- 텍스트에서 패턴과 같은 길이의 부분 문자열을 슬라이딩하며 해시값 비교
KMP Knuth-Morris-Pratt 알고리즘
- 불일치할 경우, 처음부터 다시 비교하지 않고 이미 맞았던 부분을 활용해 불필요한 연산을 줄임
- 패턴 내부에서 앞부분과 동일한 부분을 찾아 점프함

728x90