알고리즘 Flashcards
동적계획법
[정의] 최적성 원리 문제 대한 점화관계 도출, Memoization기법 활용하여 부분 반복 문제 상향식 최적화 해결 알고리즘
[특징] 모든 가능성 고려, 최적해 보장, 상향식 접근
[전제조건]
- 최적성 원리 만족 점화/재귀 관계식 도출 가능 문제
- 점화/재귀 관계식 도출 : an+1 = f(an) [함수 f(an): 수열 {an}의 점화식, an/ an+1: 인접 항]
[학습절차]
1. 점화/재귀 관계식 도출 : 부분문제 해 도출
2. Memorization : 점진적 상위문제 해결 (최소 문제 점화식 해 계산, 테이블 저장)
3. Bottom-Up Approach : 상위 문제 해 계산 시 저장된 부분 문제 해 활용 최종 최적해 도출
* 반복 요소 존재, 하위 문제가 기하급수적으로 증가하는 경우 효과적 최적해 도출 기법으로 활용
[알고리즘] 벨만포드, 플로이드
[사례] 피보나치 수열
점근표기법
[정의] 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학적 표기법
* 알고리즘의 복잡도를 단순화하거나 무한급수의 뒷부분을 간소화할때 사용
[알고리즘 표기 유형]
1. O(빅오) 표기법 : 입력 데이터가 최악일때 기준 효율 평가, 수행시간의 상한을 표시
2. Ω(빅오메가) 표기법 : 입력 데이터가 최상일때 기준 효율 평가, 수행시간의 하한을 표시
3. Θ(빅세타) 표기법 : 빅오+빅오메가, 수행시간의 하한인 동시에 상한을 표시
O-Notation
[정의] 데이터 수 N에 대해서 복잡도의 함수 양상을 표현위한 알고리즘의 시간 복잡도를 표현하는 상한 점근 표기법
[유형]
- O(1) : 상수 함수, 해시 함수(Hash Function)
- O(log N) : 로그형, 이진탐색(Binary Search)
- O(N) : 선입, 단순탐색(Find Item)
- O(N log N) : 분할과 합병형, 퀵 정렬(Quick Sort)
- O(N^2) : 제곱형, 버블 정렬(Bubble Sort), 삽입 정렬, 선택 정렬
- O(N^3) : 세제곱형, Finding the Shortest Path
- O(2^n) : 지수형, 동적 프로그래밍
[유형별 연산 시간 순서] O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(N^3) < O(2^n)
알고리즘 성능평가
[정의] 알고리즘 수행 시 시간 및 공간에 대한 지표를 기준으로 알고리즘 성능을 판단하는 프로세스
[평가유형]
- 성능 분석 : 알고리즘 복잡도 분석
- 성능 측정 : 수행시간 측정
- 효율성 평가 : 시간 복잡도, 공간 복잡도
[평가척도]
1. 시간 복잡도 : 프로그램의 컴파일 시간과 실행 시간의 합
2. 공간 복잡도 : 알고리즘 수행에 필요한 메모리의 양을 평가
시간복잡도
[정의] 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지 계산, 수행 시간을 측정한 복잡 정도
[표현척도] 단위 연산 (비교, 지정), 입력 크기 (배열의 크기, 리스트의 길이)
[유형] 모든 경우를 분석, 최악의 경우 분석, 평균치 분석, 최적 경우 분석
* 최근 대용량 시스템 보편화로 공간복잡도 보다는 시간복잡도를 우선
공간복잡도
[정의] 공간효율성을 평가를 위해 알고리즘 수행에 필요한 공간(메모리)의 양을 측정하는 복잡 정도
[공간 계산]
- 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구
- 수식 S(P)=c+SP(n) 으로 표기
[유형] Fixed Area(명령어 공간, 단순 변수), Variable Area(가변적인 공간)
탐색 알고리즘
[알고리즘 원리 측면 개념] 순서 또는 비순서화된 리스트 등에서 어떤 원소/대상의 존재 및 그 위치를 찾는 기법
[활용 측면의 개념] 문제를 풀기 위한 최적의 해 또는 목표 데이터를 효율적으로 찾아내기 위한 전략
[문제 해결 수식] F(s) = g(s) + h(s)
- s : 각 상태. F: 해 적합성 평가 함수
- g : 현재까지 지나쳐 온 행동들에 소모된 비용의 총 합
- H : 추정치(heuristic)로서, 문제에서 추가적으로 주어진 정보를 통해서 얻을 수 있는 값
[유형]
1. Uniformed 전략 : h(s)의 값은 0으로 고정, 도착 지점까지의 비용만으로 판단 (백트래킹, 분할정복)
2. Informed 전략 : 추가적인 정보(h(s))를 활용하여 탐색 수행 (탐욕법, 동적계획법, A*)
분할정복법
[정의] 문제를 작은 2개로 분리하여 각각 해결후, 결과 모아서 원래 문제 해결 하향식 알고리즘
[특징] 하향식 접근법(Top-Down)
[학습절차]
1. 분할 : 2개이상 하위문제 분할
2. 정복 : 분할된 하위문제 해결
3. 결합 : 정복된 답을 취합
[알고리즘] Merge / Quick Sort, Binary Search
[사례] 병합 정렬 알고리즘, 이진 탐색 알고리즘
탐욕법
[리드] 국부적 최적해 선택
[정의] 매 선택시 최적해 선택 통한 최종해 도출하는 근시안적 알고리즘
[특징] 최적성의 원리(현재 상태에서의 최적 판단), 최적해 미보장(문제에 따라 최적이 아닐 가능성 존재), 근사치 추정
[학습절차] 해적검
1. 해 선택 : 부분 문제의 최적해를 구하고 결과를 부분해 집합에 추가
2. 적합성 검증 : 제약조건, 위반여부 검사
3. 해 검증 : 문제의 해가되는지 확인
* 최종 해 도출까지 과정을 반복 & 적합성 확인
[알고리즘] 크루스칼, 배낭문제, 다익스트라
[사례] 허프만 트리
백트래킹
[정의] 모든 경우의 수를 도출하기 위해 DFS와 Pruning 기법 기반 특정 조건 만족하는 모든 해 탐색 기법
[특징] 깊이우선탐색 (무정보 탐색(Uninformed or Blind Search) 방법) Pruning (가지치기 표시 기법 (유망하지 않는 노드 제거))
[절차] (DPSB)
1. 깊이 우선 탐색(DFS) 수행 : 상태 공간 트리
2. Promising 검토 : 유망성 검토
3. 서브트리 이동 : 재귀 호출
4. 백트래킹 수행 : Pruning - 유망성(promising)이 없으면 Pruning(가지치기)을 수행하여 시간 단축
[구성요소]
- 노드 : Non-Promising, Promising(해가 나올만한 유망한 마디)
- 해 : 모든 해, 후호 해
- 기법 : DFS, Back-Tracking(가능성이 없는 마디 제거)
[사례] N-Queen Problem, 외판원 문제(TSP)
최단 경로 탐색 알고리즘
[정의] 정점을 연결하는 경로중 간선들의 가중치 합이 최소가 되는 경로를 찾는 알고리즘
[알고리즘]
- 다익스트라 : 최소 비용 경로 설정 (링크상태 라우팅)
- 벨만-포드 : 음의 가중치 계산 (거리백 라우팅)
- A*(A star) : 휴리스틱 순서 탐색, 탐색 속도 높 (네비게이션)
- 플로이드-와샬 : 동적 계획 기반, GIS 네트워크 분석
- BFS (Best First Search) : 모든 가중치가 동일한 경우 사용
다익스트라 알고리즘
[정의] 방향 가중 그래프에서 주어진 출발점과 도착점 사이의 최단경로 탐색하는 Greedy 기반 알고리즘
[특징] 방향그래프, 가중 그래프(음 값은 불가), 모든정점 대상, 단일-쌍 기준(출발점>도착점), O(ElogE) 시간 복잡도, Greedy 알고리즘
[경로탐색절차]
1. 그래프 인접행렬 작성 : 트리정점(“0”표시), 인접정점(“가중치”표시), 비인접정점(“무한대”표시)
2. 시작 노드부터 각 노드 별 최소비용 간선 연결
3. 2번을 반복하여 모든 정점 연결 시 종료
[문제풀이 시 표시 내역]
1. S={} : 방문한 노드 집합 : 방문 시 인접 노드 d 값 계산하며 이때 인접 노드는 아직 방문한 상태가 아니므로 S에 포함되지 않고 d 값만 계산한 상태가 됨
2. d{A}=0/무한대 : 각 정점 d 값
3. Q={A, B, … , Z} : 방문하지 않은 노드 집합
벨만 포드
[정의] 음의 가중치 문제 해결위하여 가중 유향 그래프에서 음수 허용 임의 실수인 경우의 최단경로 탐색 알고리즘
[특징] 음의 가중치 문제 해결(다익스트라 알고리즘 사용불가), 느린 속도(시간 복잡도 O(EV) )
[경로탐색절차]
1. 조사하지 않은 노드중 가장 효율적이라고 판단되는 노드 검색(휴리스틱 함수사용)
2. 찾아진 노드가 도착점이면 종료. 아니면 인접한 다른 노드 검색
3. 조사한 노드들은 close list 소속, 조사하지 않은 노드들은 open list 소속
4. 목표정점 도달까지 열린 목록 조사, 닫힌목록 변환작업 반복 수행
깊이 우선 탐색
[원리] 스택 또는 재귀함수를 이용하여 가장 깊은 곳까지 검색하는 동안 경로를 스택에 저장한 뒤, 나아갈 길이 없다면 스택의 Data를 하나씩 꺼내 분기점까지 돌아가는 방법으로 탐색
[비교] DFS vs BFS
- 원리 : 백트래킹 | 첫 정점을 보고 인접 정점 우선 탐색
- 저장방식 : Stack, 후입선출(LIFO) | Queue, 선입선출(FIFO)
- 활용 : 사이클 탐지, 위상정렬 | 최소신장트리, 최단경로
- 장점 : 무한히 넓은 트리에 효과 | 무한히 깊거나 무한에 가까운 트리에 효과
- 단점 : 스택 오버플로우 발생 | 목표노드로 가는 경로들이 모두 같은 거리일때 비효율적
- 복잡도 : 동일 (인접행렬 - O(V^2), 인접 리스트 - O(V+E) V:정점, E:간선
너비 우선 탐색
[원리] Queue를 사용하며 시작 정점으로부터 인접 정점을 먼저 방문하는 탐색 방법
