티스토리 뷰
- 최단경로
- 가중방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
- 플로이드 알고리즘
- 모든 정점 간의 최단 경로
- 동적 프로그래밍 방법 적용
- O(|V|^3)
- 가중치의 합이 음수인 사이클이 없다고 가정
플로이드 Floyd 알고리즘 | 다익스트라 Dijkstra 알고리즘 |
모든 정점 간의 최단 경로 | 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 (단일 출발점 최단 경로) |
동적 프로그래밍 방법 적용 | 그리디 방법 적용 |
O(|V|^3) | O(|V|^2) |
가중치의 합이 음수인 사이클이 없다고 가정 | 음의 가중치를 갖는 간선이 없다고 가정 |
-
- 다익스트라 알고리즘
- 거리 d[v]
- 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이
- 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법
- 초기화 -> 출발점 d[s] = 0, 나머지 모든 정점 v의 d[v] = ∞, 선택 정점 집합 S= {}
- 미선택 정점 집합 V-S에서 d[] 가 가장 작은 정점 u를 선택
- u의 인점 정점에 대해서 u를 경유하는 거리와 기존 거리 중에서 작은 것을 새로운 거리값으로 조정
- 특징
- 음의 가중치를 갖는 간선이 없어야 함
- 거리 d[v]
- 다익스트라 알고리즘
- 작업 스케줄링 문제
- 가장 적은 개수의 기계를 사용해서 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제
- 작업의 집합 T = {t1, t2, ... , tn}, ti = (si, fi) (1<=i<=n)
- si: 작업 시작 시간, fi: 작업 완료 시간
- 작업간의 충돌이 없어야 함
- 작업 간의 충동 -> 한 기계에서 두개 이상의 작업이 동시에 수행되는 것
- 작업 i와 j가 충돌을 피하기 위한 조건 -> fi<=sj 또는 fj<=sj
- 각 작업이 시작되면 중단됨 없이 해당 기계에서 완료되어야 함
- 작업의 집합 T = {t1, t2, ... , tn}, ti = (si, fi) (1<=i<=n)
- 기본 아이디어
- 각 단계에서 시작시간이 빠른 작업을 우선적으로 선택해서
- 충돌이 발생하지 않으면 -> 해당 기계에 배정
- 충돌이 발생하면 -> 새로운 기계에 배정
- 각 단계에서 시작시간이 빠른 작업을 우선적으로 선택해서
- 성능 분석
- O(nlogn)
- 가장 적은 개수의 기계를 사용해서 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제
- 작업선택
- 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제
- 작업의 집합 T = {t1, t2, ... , tn}, ti = (si, fi) (1<=i<=n)
- 기본 아이디어
- 각 단계에서 완료 시간이 빠른 작업을 우선적으로 선택해서
- 충돌이 발생하지 않으면 -> 기계에 배정
- 충돌이 발생하면 -> 해당 작업을 버림
- 각 단계에서 완료 시간이 빠른 작업을 우선적으로 선택해서
- 성능 분석
- O(nlogn)
- 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제
- 호프만 코딩
- 문제의 빈도 또는 확률 정보를 이용한 통계적 압축 방법
- 텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여
- 출현 빈도수가 높은 문자 -> 짧은 코드
- 출현 빈도수가 낮은 문자 -> 긴 코드
- 텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여
- 텍스트 "ababcdbad"
- 8비트 아스키 코드로 표현하는 경우 -> 9문자 * 8비트 = 72비트
- 고정 길이 변환 코드로 표현하는 경우 -> 9문자 * 2비트 = 18비트
- 문자 집합 = {a, b, c, d} -> a: 00, b: 01, c: 10, d: 11
- 단순히 빈도수에 따른 가변 길이 변환 코드로 표현하는 경우
- 빈도수 -> a(3), b(3), c(1), d(2)
- a -> '0'
- b -> '1'
- c -> '00'
- d -> '01'
- 인코딩: 010100011001
- 디코딩하는 경우 여러가지 해석이 가능하여 모호성이 발생
- 빈도수 -> a(3), b(3), c(1), d(2)
- 모호성 없이 디코딩하려면 접두부 코드 prefix code이어야 함
- 각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드
- 허프만 코딩
- 접두부 코드, 최적 코드
- 최적 코드 -> 인코딩된 메시지의 길이가 가장 짧은 코드
- 인코딩 과정
- 주어진 텍스트에서 각 문자의 출현 빈도수를 계산
- 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여
- 주어진 텍스트의 각 문자를 이진 코드로 변환하여 압축된 텍스트를 생성
- 허프만 트리
- 허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진트리
- 그리디 알고리즘 방법 적용
- 리프 노드가 각 문자를 표시하는 전 이진트리
- 각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 작은 두 트리를 합쳐서 보다 큰 트리를 생성하는 과정을 반복
- 각 노드는 빈도수로 표시
- 좌우의 두 간선은 각각 0과 1로 레이블됨
- 합쳐지는 두 트리를 자식 노드로 갖는 부모 노드를 생성
- 부모 노드의 빈도수는 두 자식노드의 빈도수의 합으로 표시
- 예제
- "abracadabra"
- 허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진트리
- 접두부 코드, 최적 코드
- 문제의 빈도 또는 확률 정보를 이용한 통계적 압축 방법
-
-
-
-
- a: 0, b: 100, c: 110, d: 111, r: 101
- 01101010110011101001010: 23비트
- 디코딩 과정
- 압축된 스트링을 처음부터 차례대로 읽으면서 주어진 접두부 코드와 일치하는 코드가 나오면 해당 문자로 변환
- 성능 분석
- O(nlogn) + O(m)
- n: 문자 집합의 크기
- 길이 m인 텍스트의 실제 인코딩 시간
- O(nlogn + m)
- O(nlogn) + O(m)
- 특징
- 각 문자의 빈도수를 모르는 경우 -> 주어진 텍스트를 2번 읽음
- 각 문자의 빈도수를 계산할 때
- 텍스트를 읽으면서 실제 인코딩 할 때
- 이 경우 속도가 상당히 느려 실용성이 없음
- 압축된 데이터를 디코딩하려면
- 각 문자의 빈도수, 허프만 트리에 대한 정보, 문자 집합 정보가 필요
- 압축된 데이터의 헤더로써 필요한 정보를 제공 -> 실제 압축률 저하를 초래
- 각 문자의 빈도수, 허프만 트리에 대한 정보, 문자 집합 정보가 필요
- 각 문자의 빈도수를 모르는 경우 -> 주어진 텍스트를 2번 읽음
-
-
-
- 최단 경로
- 단일 출발점 최단 경로 -> "다익스트라 알고리즘"
- 성능: 인접행렬 O(|V|^2), 인접리스트 O((|V| + |E|)log|V|)
- 음의 가중치를 갖는 간선이 없는 경우에 적용 가능
- 작업 스케줄링 문제
- 가장 적은 개수의 기계를 사용해서 충돌 없이 모든 작업을 할당하는 문제
- 성능: O(nlogn) (n: 작업의 개수)
- 가장 적은 개수의 기계를 사용해서 충돌 없이 모든 작업을 할당하는 문제
- 작업 선택 문제
- 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 할당하는 문제
- 성능: O(nlogn) (n: 작업의 개수)
- 허프만 코딩
- 접두부 코드, 최적 코드, 허프만 트리(그리디 알고리즘 방법, 전 이진트리)
- 성능: O(nlogn+m) (n: 문자 집합의 크기, m: 텍스트의 길이)
- 각 문자의 빈도수를 모르는 경우 텍스트를 두 번 읽음
- 접두부 코드, 최적 코드, 허프만 트리(그리디 알고리즘 방법, 전 이진트리)
- 단일 출발점 최단 경로 -> "다익스트라 알고리즘"
'algorithm' 카테고리의 다른 글
[algorithm] 합병정렬, 퀵정렬, 힙정렬, 계수, 기수 정렬 (0) | 2021.04.30 |
---|---|
[algorithm] 정렬 알고리즘 (0) | 2021.04.27 |
[algorithm] 그리디 알고리즘 (0) | 2021.04.17 |
[algorithm] 1952 달팽이 java (0) | 2021.04.14 |
[algorithm] 달팽이 java (0) | 2021.04.13 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- server side rendering
- 구조체
- 이진탐색
- 퀵정렬
- javascript
- client side rendering
- 클래스
- C
- 최단경로
- BFS
- 입출력장치
- 알고리즘
- 스텍
- 동적프로그래밍
- 운영체제
- Stack
- 인접행렬
- 소프트웨어
- 배열
- 재귀함수
- 인접리스트
- 병행프로세스
- C++
- Java
- stackframe
- 세마포어
- 교착상태
- 자료구조
- dfs
- react
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함