기말

• 디피 돌놓기 문제
• 복잡도 분석은 안나옴
• 디피 행렬곱셈
• LCS
• 그래프 위상정렬(DFS, 진입간선X)
• 그래프 최단경로(다익스트라, 벨만포드, 플로이드 )

알고리즘 복잡도

점근적 분석

• 입력의 크기가 큰 경우의 분석

점근적 표기법 임의의 표기법 X에 대해 f(n) = X(g(n)), c는 양의 상수

시간복잡도 분석 종류

• Worst-case
• Average-case
• Best-case: 의미없음

재귀

점화식

• 현재 항을 한개 이상의 이전 항들로 표현한 식

점화식의 점근적 분석 방법

반복 대치

• 이전 항으로 반복해서 대치해가며 n에 대한 식으로 정리하는 방법

추정후 증명

• 점근적 복잡도를 미리 추정한다음 귀납적으로 증명

마스터 정리

• 특정한 형태의 재귀식에 대한 복잡도 공식
• T(n) = a*T(n/b) + f(n)이고 h(n) = n^(log b a)에서
  f(n) / h(n) = F라 하고 양의 상수 k에 대해
  1. F = O(n^(-k))이면 T(n) = Θ(h(n))
  2. F = Ω(n^k)이고, a*f(n/b) <= c*f(n)이면 T(n) = Θ(f(n))
  3. F = Θ(1)이면 T(n) = Θ(h(n) * log n)

마스터 정리 근사 버전

• 마스터 정리와 같은 의미는 아니지만 거의 일치, 반례를 찾기 어려움
• T(n) = a*T(n/b) + f(n)에서 h(n) = n^(log b a)라고 할 때
  1. h(n)이 더 무거우면 Θ(h(n))
  2. f(n)이 더 무거우면 Θ(f(n))
  3. h와 f가 같은 무게면 Θ(h(n)*log n)

정렬

선택정렬

• 각 루프마다 최대 원소를 찾아 정렬되지 않은 맨 오른쪽 원소와 교환
• O(n^2)

버블정렬

• 이웃한 쌍들을 비교해 교환. 루프의 결과로 맨 오른쪽에 가장 큰 값이 옴
• O(n^2)

삽입정렬

• 배열의 정렬된 구간을 1씩 증가
• O(n^2)

병합정렬

• 배열을 반으로 나누어 정렬
• O(n log n)

퀵정렬

• pivot(첫번째 원소)을 기준으로 좌우로 수 이동. 분할 정복
• O(n log n) ~ O(n^2)

힙정렬

• 배열을 힙으로 만들고 하나씩 힙에서 제거해 정렬
• 힙 : 균형잡힌 이진 트리, 부모는 자식보다 작다(최소힙)
  • 삽입: 마지막 리프에 삽입하고 부모와 대소 비교하여 교환
  • 삭제: 루트 삭제 후 마지막 리프를 루트로 놓고 자식과 대소 비교하여 교환
• O(n log n)

기수정렬

• 원소들이 모두 k이하의 자릿수일 때 1번째 자릿수부터 비교하며 정렬
• O(n)

계수정렬

• 원소들의 크기가 1~k일 때
• 원소의 값에 해당하는 인덱스에 원소의 개수를 저장
• O(n) 또는 O(k)

안정성 정렬

• 정렬 후에도 같은 값의 원소들이 기존 순서를 유지
• 버블, 병합, 삽입, 기수, 계수
• 다음은 아님-선택, 힙, 퀵
• 병합의 경우 왼쪽과 오른쪽이 같을 경우 왼쪽부터 꺼내야함
• 선택의 경우 최대값 중 가장 뒤에있는 것을 선택하면 안정성 유지할 수 있음

검색 트리

• 레코드: 개체에 대한 저장 단위
• 필드: 레코드에서 각각의 정보를 나타내는 부분
• 검색키=키: 각 레코드를 대표하는 고유한 필드
• 검색트리: 각 노드가 하나 이상의 키를 가지고 있음
• 내부검색트리: 메인 메모리에 위치하는 검색트리
• 외부검색트리: 일반적으로 디스크에 위치하는 검색트리
• 메인 메모리가 모든 키 값을 수용할 수 없다면 외부검색트리를 사용해야 하는데 이때 디스크 접근 시간이 검색의 효율을 결정(트리의 높이를 최소화해야함)
• MySQL에서는 B-트리 인덱스가 일반적으로 가장 많이 사용

이진검색트리

• 각 노드는 하나의 키 값
• 최대 두개 자식
• 왼쪽 자식 < 노드 < 오른쪽 자식
• 단점 : 균형이 깨지면 시간복잡도 증가

treeSearch(t,x)

• t가 NIL이거나 x면 t를 반환, 아니면 왼쪽 또는 오른쪽 자식 재귀로 탐색
• O(log n) ~ O(n)

treeInsert(t,x)

• 대소 비교해서 아래로 내려가서 삽입

treeDelete(t,x)

• 자식 0개 : 그냥 삭제
• 자식 1개 : 자식을 삭제 노드 위치로
• 자식 2개 : 오른쪽 자식의 왼쪽 서브 노드들 중 최소값을 삭제 노드 위치로

레드블랙트리

• 균형잡힌 이진검색트리
• 여기서의 리프 노드는 자식 중에 NIL을 하나로 연결한 노드를 뜻함

레드블랙특성

1. 루트는 블랙
2. 모든 리프(NIL)은 블랙(무시해도 됨)
3. 노드가 레드이면 그 노드의 자식은 반드시 블랙
4. 루트 노드에서 임의의 리프 노드까지 만나는 블랙의 수는 모두 같다

p가 레드일 경우 삽입(p2,y는 블랙)

• 레드로 삽입하여 레드블랙특성을 위반하는지 확인
• 대상노드:x, x의 형제:y, 부모:p, p의 부모:p2, p의 형제:s
• case1 s=레드: p2를 레드로 p,s를 블랙으로
• case2 s=블랙
  • case2-1 x가 오른쪽: p를 중심으로 왼쪽으로 회전, case2-2로
  • case2-2 x가 왼쪽: p2를 중심으로 오른쪽으로 회전

B-트리

• 균형잡힌 다진검색트리
• 외부검색트리로 사용됨
• 루트를 제외한 모든 노드는 k/2 ~ k개의 키를 갖는다
• 각 키 사이는 자식 노드와 연결된다
• 모든 리프노드는 같은 깊이를 가진다
• overflow, underflow의 경우 재조합을 해야함

BTreeInsert(t,x)

1. 삽입할 리프노드를 찾아 삽입
2. 오버플로우가 발생하면 형제 노드에 키를 넘기거나, 노드를 둘로 분할

BTreeDelete(t,x,v)

1. 삭제할 키가 리프가 아니면 리프까지 직후 키와 교환
2. 리프에 있는 키를 제거
3. 언더플로우가 발생하면 형제 노드에서 키를 받거나, 노드를 합병

다차원 검색

검색키가 두개이상의 필드로 구성(예를들어 좌표)

• KD-트리: 각 레벨에서 필드를 번갈아가며 검색에 사용
• KDB-트리:
• R-트리
• 그리드 파일

KD-트리

• 각 레벨에서 필드를 번갈아가며 검색에 사용
• 삭제: 해당 레벨에서 비교하는 필드가 가장 작은 노드를 삭제 위치로 가져옴

KDB-트리

• KD-트리와 B-트리의 합
• 균형트리
• 루트는 k차원 공간 전체를 커버
• 아래 노드는 전체 공간의 부분을 커버
• 리프노드는 데이터 페이지 정보를 저장

R-트리

• B-트리의 다차원 확장
• 균형잡힌 검색트리(모든 리프의 레벨이 같음)
• 모든 레코드는 리프노드에서만 가리킴
• 점, 선, 면, 공간도 저장 가능
• MBR로 근사(배타적이지 않음)

그리드 파일

• 트리는 아님
• 공간을 배타적인 격자 영역으로 나눔
• 일차스케일링 배열이나 그리드 배열로 영역 관리

해시 테이블

• 평균 삽입, 삭제, 검색 속도가 O(1)
• 원소의 값으로 주소를 결정
• but 테이블 속 최소,최대 원소를 찾는 것은 어려움

해시 함수

원소의 값을 주소 변환하는데 사용하는 함수

나누기 방법

• h(x) = x mod m
• m은 해시 테이블의 사이즈(보통 소수)

곱하기 방법

• h(x) = (xA mod 1) m
• mod: % 연산과 다르게 x의 소수 자리도 반환한다.
• 0 < A < 1, m = 2^p

충돌 & 충돌 해결

두 개 이상의 원소가 해시 테이블에서 주소가 같을 때

체이닝

• 같은 주소로 해싱되는 원소를 모두 하나의 연결리스트로 관리
• 추가적인 공간 필요

개방주소 방법

• 충돌이 일어나더라도 해시 테이블 내부에서 해결
• 추가적인 공간 필요하지 않음
• 선형 조사, 이차원 조사, 더블 해싱
• 삭제 시 표시를 해줘야함

선형 조사

• hi(x) = (h(x) + i) mod m
• 해당 주소에 i를 플러스
• 1차 군집: 특정 영역에 원소가 몰리는 현상

이차원 조사

• hi(x) = (h(x) + c1i^2 + c2i) mod m
• 2차 군집: 여러 개의 원소가 동일한 초기 해시 함수값을 가짐

더블 해싱

• hi(x) = (h(x) + i*f(x)) mod m
• h(x), f(x) 둘다 해시함수

해시 테이블 검색 시간

• 적재율 a = n/m (n:저장된 원소 개수, m:테이블 크기)
• 적재율이 높아지면 해시 테이블 효율이 떨어짐
• 임계 적재율을 정하고 초과하면 테이블 크기 키워서 다시 해싱

체이닝

• 실패할 경우: a
• 성공할 경우: 1+a/2-a/2n

개방주소 방법

• 실패할 경우: 1/(1-a)

• 성공할 경우: (1-a)log(1/(1-a))

• 체이닝에서-실패할경우(a), 성공할경우(1+a/2+a/2n)
• 개방주소에서-

상호 배타적 집합의 처리

연결리스트와 트리를 이용해 상호배타적 집합을 구현하고 연산 속도를 비교해 보자

상호배타적 집합: 중복이 없다

구현할 연산

• Make-Set(x): 원소 x로만 이루어진 집합을 만든다​
• Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다​
• Union(x,y): 원소 x를 가진 집합과 원소 y를 가진 ​집합의 합집합​

연결리스트로 구현

• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 한다.
• 모든 원소는 대표 원소를 포인터
• m번의 3연산을 할때 n번이 Make-Set이라면 수행시간: O(m + n log n)

Union

• 큰 집합 뒤에 작은 집합을 붙임(대표 원소 포인터 갱신 작업 최소화)
• m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set이라면: O(m+ nlogn)

트리로 구현

• 트리의 루트를 대표원소로 삼는다
• 자식만 부모를 가리킴, 루트는 루트를 가리킴

Make-Set(x) // 노드 x를 유일한 원소로 하는 집합을 만든다. ​
{ ​
    p[x] ← x ; ​
} ​

Union(x, y) // 노드 x가 속한 집합과 노드 y가 속한 집합을 합친다 ​
{ ​
    p[Find-Set(y)] ← Find-Set(x) ; ​
} ​

Find-Set(x) //노드 x가 속한 트리의 루트 노드를 리턴한다. ​ ​
{​
    if (x  = p[x]) then ​return x ; ​
    else return Find-Set(p[x]) ; ​
} 

연산의 효율 높이기

• Rank(트리 높이)로 Union: 랭크가 높은 집합에 낮은 집합을 붙임
• 경로압축: Find-Set에서 만나는 노드들의 부모를 루트로(단 랭크는 안바꿈)

Make-Set(x) // 노드 x를 유일한 원소로 하는 집합을 만든다. ​
{ ​
    p[x] ← x; ​
    rank[x] ← 0; ​
} ​

Union(x, y) // 노드 x가 속한 집합과 노드 y가 속한 집합을 합한다 ​
{ ​
    rx ← Find-Set(x); ​//x의 루트
    ry ← Find-Set(y); ​//y의 루트
    if (rank[rx] > rank[ry]) ​then p[ry] ← rx ; ​
    else { ​
        p[rx] ← ry ; ​
        if (rank[rx] = rank[ry]) then rank[ry] ← rank[ry] + 1; ​
    } ​
} 

Find-Set(x) //경로압축 - 부모를 루트로 하고 루트를 반환한다.
{ ​
    if (p[x] ≠ x) then p[x] ← Find-Set(p[x]); ​
    return p[x]; ​
} 

동적 프로그래밍

• 한번 수행한 연산을 기록함
• 재귀의 단점 : 같은 연산을 반복함(피보나치, 행렬곱셈 최적순서)
• 그러나 다음은 적당함 : 퀵정렬, 병합정렬, 팩토리얼, DFS…

적용 요건

• 최적 부분구조: 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨
• 재귀호출시 중복: 재귀 적용시 같은 연산이 심하게 중복됨

행렬 경로 문제

• n*n행렬에서 좌상단에서 우하단까지 방문한 칸에 합의 최소값
• 제약조건: 오른쪽이나 아래쪽으로만 이동할 수 있다.

돌 놓기

• 3*N 테이블 각 칸에 정수 기록
• 제약조건 : 가로, 세로 인접한 두 칸에 돌 못 놓음, 각 열에는 적어도 하나 이상 돌
• 목표 : 돌이 놓인 자리에 있는 수의 합의 최대값
• 해결 : 이전 상태(0,1,2,0과1)의 최대값을 저장

행렬

• 행렬곱 A1…An를 구하는 최소 비용 구하기
• 행렬 순서에 따라 곱셈 횟수가 다름
• 가장 큰것을 겹치게 해서 해결

LSC

• 두 문자열의 길이가 N,M이고, 마지막 원소가 n,m일때
• if n or m==0 then LCS(N,M)=0
• if n==m then LCS(N,M)=LCS(N-1,M-1)-1
• if n!=m then LCS(N,M)=max(LCS(N-1,M), LCS(N,M-1))

그래프

Graph G = (V,E)

• V(vertex): 정점 집합
• E(edge): 간선 집합
• 두 정점이 간선으로 연결되어 있으면 인접(adjacent)하다

그래프 종류

• 방향을 가졌는지
• 가중치를 가졌는지

그래프 구현 방법

정점의 개수가 n일때

• 인접행렬: n*n의 2차원 배열
• 인접리스트: n개의 연결리스트
• 인접배열: 인접리스트와 비슷하나 배열을 씀

그래프 탐색

모든 정점 방문하는 방법

너비우선탐색(BFS)

• 인접한 정점 먼저 탐색(큐 사용)

• Θ(

  V

  +

  E

  )

• 인접 정점에서 숫자가 작은 정점 먼저

깊이우선탐색(DFS)

• 한방향으로 계속가다가 막히면 이전으로 돌아옴(스택 또는 재귀 사용)

• Θ(

  V

  +

  E

  )

• 인접 정점에서 숫자가 작은 정점 먼저

최소신장트리(Minimum Spanning Trees)

• 무향 연결 그래프
• 싸이클이 없는 연결 그래프
• 정점이 n이고, 간선이 n-1개
• 그래프 G의 정점과 간선으로만 구성됨
• G의 신장 트리들 중 간선의 합이 최소인 신장트리

프림 알고리즘

• 시작 정점에서 최소신장트리를 구하는 알고리즘

크루스칼 알고리즘

위상정렬

• 모든 정점을 일렬로 나열하여 정점 x에서 y로 가능 간선이 있으면 x가 앞으로
• 임의의 유향 그래프에 대해 복수의 위상 순서가 존재
• 조건-싸이클이 없는 유향 그래프

최단 경로

• 가중치가 있는 유향 그래프에서
• 단일 시작점 최단경로 - 다익스트라, 벨만 포드, 싸이클이 없는 그래프
• 모든 쌍 최단경로 - 플로이드 워샬

다익스트라

• 시작 정점에서 다른 모든 정점의 최단경로
• 시작 정점을 0으로 다른 정점은 무한대로 놓고 인접한 정점을 방문해 가며 최단 거리를 기록
• 우선순위큐 사용

• 수행시간 O(

  E

  log

  V

  ) - 힙을 이용

벨만포드 알고리즘

• 다익스트라와의 차이점은 음의 가중치를 허용

• 수행시간 Θ(

  E

  V

  )

플로이드 워샬

• 모든 정점 간의 상호 최단거리 구하기

강연결요소 구하기

• 강연결 - 모든 정점쌍에 대해서 양방향 연결이 되어있음
• 강연결요소 - 강하게 연결된 부분 그래프

1. 그래프에서 DFS를 수행해 각 정점 v의 완료시간을 구함
2. G의 모든 간선들의 방

그리디

문자열 매칭

P & NP 문제

시간복잡도로

• P: 풀 수 있는 문제
• NP: 풀 수 없는 문제

상태공간 트리

문제 해결 과정 중 중간 상태를 하나의 노드로 표현

백트래킹

DFS와 비슷함

가능한 지점까지 가다가 막히면 이전으로 돌아감