Skip to main content

기술사 - 알고리즘

· 8 min read
Gracefullight
Gracefullight
Owner

알고리즘​

트리​

이진탐색트리​

  • Binary search
  • O(log⁡n)O(\log n)

균형이진탐색트리​

  • AVL Tree: Adelson-Velskii-Landis Tree
  • Balance Factor: BF(T)=Hl−HrBF(T) = H_l - H_r = T의 왼쪽 서브트리 높이 - T의 오른쪽 서브트리의 높이
  • BF(T)가 -1, 0, 1 중 하나를 만족해야함.
  • LL, LR, RR, RL 용어를 보기보단 그림을 보고 이해해야함.
  • 최적화되어 O(log⁡n)O(\log n) 탐색 시간 보장

m-원 탐색트리​

  • m-way Search Tree, Multiway Search Tree

B- 트리​

B* 트리​

  • B애스터 트리

B+ 트리​

  • 모든 키의 값이 단말 노드에 순차 나열된다, 링크드 리스트로

Red Black 트리​

T 트리​

  • AVL Tree + B tree

그래프​

  • Node: 정점, Edge: 간선
  • 신장트리: Spanning Tree
    • 그래프의 모든 정점과 일부 간선을 포함한 트리로 표현
    • T=(V,F)T = (V, F)

최소 신장 트리​

  • Minimal Spanning Tree
  • 가장 적은 비용/거리로 그래프의 모든 정점을 연결할 수 있는 구조

프림 알고리즘​

  • Prim
  • 노드 기준
  • O(n2)O(n^2)

크루스칼 알고리즘​

  • Kruscal
  • 엣지 기준
  • 간선 최소 개수: O(nlog⁡n)O(n \log n)
  • 간선 최대 개수: O(n2log⁡n)O(n^2 \log n)

최단경로 문제​

  • Shortest Path

다익스트라​

  • Dijkstra
  • 노드 수가 n이라면 n-1개의 목적지가 모두 확정될 때까지 반복
  • 다익스트라를 노드마다 반복한게 프림 알고리즘

벨만포드​

  • 가중치가 음수일 경우, 불이익이 있는 경우 다익스트라 알고리즘으로 최단 경로가 계속 갱신되므로 이를 방어하기 위한 방법

정렬​

선택 정렬​

  • Selection Sort
  • O(n2)O(n^2)
  • 가장 작은 값을 순서대로 찾아내어 첫 번째 배열부터 채워나가며 정렬

버블 정렬​

  • Bubble Sort
  • O(n2)O(n^2)
  • 왼쪽에서 오른쪽으로 비교해가며 오름차순으로 자리를 교환하여 정렬

합병 정렬​

  • Merge Sort
  • O(nlog⁡n)O(n \log n)
  • 분할 정복
  • 데이터 분포의 영향을 덜 받는다, 최악의 경우에도 효율적.

퀵 정렬​

  • Quick Sort
  • O(nlog⁡n)O(n \log n)
  • 피봇을 정한다. 전체 값을 읽어 중간값이나 몇 개의 값의 평균을 피봇으로 정함.
  • 프로그래밍 랭기지에서는 왼쪽에서 큰 값, 오른쪽에서 작은 값을 찾는 방식으로 구현.

삽입 정렬​

  • Insert Sort
  • O(n2)O(n^2)
  • 추가적인 메모리를 안 씀: in-place sort

힙 정렬​

  • Heap Sort
  • O(nlog⁡n)O(n \log n)

Max Heap​

Min Heap​

Min-Max Heap​

Deap​

  • 왼쪽은 Min Heap, 루트는 비어있음, 오른쪽은 Max Heap
  • 왼쪽 서브트리의 임의 노드는 오른쪽 서브트리 같은 위치에 있는 노드와 대응된다.

기수 정렬​

  • Radix Sort
  • O(n)O(n)

MSD​

  • Most Significant Digit

LSD​

  • Least Significant Digit

탐색​

깊이 우선 탐색​

  • DFS, Depth First Search
  • Solution 을 찾기 위해 Candidate Solution 인 노드들을 순회
  • Optimal Path (최적의 해)가 아닐 가능성이 높음, 보장할 수 없음.

너비 우선 탐색​

  • Breadth First Search
  • Optimal Path를 보장
  • 탐색 과정에서 나타나는 모든 상태를 저장해야하기 때문에 메모리 비효율적.

최고 우선 탐색​

  • Best-First Search

백트래킹​

  • 탐색을 진행하면서 필수적인 부분의 그래프만 유지하여 시간과 공간을 절약.
  • 노드 부모로 돌아가서 다음 자식 노드의 검색을 계속.

N-Queen 문제​

0-1 배낭문제​

인공지능​

휴리스틱 탐색​

  • Heuristic Search
  • 논리적으로, 수학적으로 증명할 수 없으나 경험이나 직관에 의해 효율적으로 해를 얻을 수 있으리라는 기대를 갖게하는 근거에 의한 방법
  • 사람처럼 학습을 통해서 직관적으로 탐색

Hill-Climbing 탐색​

  • 남은 경로에 대한 비용만 고려
    • 가장 가파른 길이 정상까지 가장 짧으니까
    • 가파른 다음에 내리막일 수도 있고, 평지일 수도 있고, 다음 가파른 길을 찾을 수 없을 수도 있음
  • 남은 길 중에 가장 가파른 길을 찾는 평가함수 사용
    • Evaluatio Function, Objetive Function

A* 탐색​

에이전트​

  • 특정 목적을 가지고 자동으로 해결해주는 소프트웨어

신경회로망​

K-means 클러스터링​

패턴인식​

딥러닝​

선형회귀​

  • Linear Regression
  • 기울기: 가중치, Weight
  • 절편: 바이어스, Bias
  • 최소 제곱법: LSM, Method of Least Squares
  • 평균 제곱근 오차: RMSE, Root Mean Square Error
    • 오차의 값이 더 이상 줄어들지 않을 때가 최적화
  • 경사하강법

다중선형회귀​

로지스틱회귀​

시그모이드 함수​

  • Sigmoid Function

단층 퍼셉트론​

다층 퍼셉트론​

오차 역전파 알고리즘​

  • Back Propagation

다중 분류 문제​

  • 원 핫 인코딩
  • 소프트맥스

과잉 적합, 과소 적합​

  • over fitting, under fitting
  • 해결방안
    • 조기 종료: Early Stopping
    • 가중치 규제 방법: Weight Regularization
    • 드롭 아웃: Drop out
    • 데이터 증강: data augmentation
    • 앙상블: Ensemble

유전자 알고리즘​

  • 재생산: Reproduction
  • 교차: Crossover
  • 치환
  • 교배/돌연변이: Mutation

그래픽 알고리즘​

베지어 곡선​

압축 알고리즘​

Run-Length 코딩​

LZ77​

허프만 코딩​

논리회로​

논리게이트​

불대수​

카노맵​

전가산기​

반가산기​

비교기​

베이즈 이론​

조건부 확률​

베이즈 정리​