본문 바로가기

Introduction to Algorithms

 (14)
[Introduction to Algorithms] 최소 신장 트리 1) 최소 신장 트리란?- 전자 회로를 설계할 때, 요소 몇 개의 핀을 전선으로 연결하여 전기적으로 등가가 되도록   만들어야 하는 경우가 있다.  n개의 핀을 서로 연결하기 위해 n-1개의 전선을 사용할 수 있는데,  여기서 전선 하나가 핀 2개를 연결한다.  일반적으로 전선을 배치하는 모든 방법 중에서 전선을 가장 적게 사용하는 방법이 가장 바람직하다. - 전선을 연결하는 문제를 연결 무방향 그래프 G = (V, E)로 모델링할 수 있다.  이 때, V를 핀의 집합, E를 연결 가능한 핀 쌍들의 집합, w(u, v)를 각 간선(u,v)   u와 v를 연결하는 비용(필요한 전선의 양)을 나타내는 가중치로 둔다.  - 그런 다음 모든 정점을 연결하고 전체 가중치의 합인 다음을 최소화하는   비순환 부분 ..
[Introduction to Algorithms] 그리디 알고리즘 1) 그리디 알고리즘이란?- 최적화 문제를 위한 알고리즘들은 통상적으로 일련의 단계를 거치는데,  각 단계마다 여러 가지 경우 중에서 선택을 해야 한다.  최적화 문제에서 동적 프로그래밍을 사용하면 가장 좋은 선택을 결정하기 위해  지나치게 많은 일을 하게 된다.  오히려 더 간단하고 효율적인 알고리즘만으로도 충분한 경우가 많다. - 그리디 알고리즘(Greedy Algorithm)은 항상 각 단계에 있어서   가장 좋을 거라 생각되는 선택을 한다.  다시 말해 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고  부분적으로 최적인 선택을 한다.  - 그리디 알고리즘은 언제나 최적의 해답을 구하지는 못하지만   많은 문제에 대한 해를 구해줄 수 있다.   우선, 활동 선택 문제(activity..
[Introduction to Algorithms] 행렬-체인 곱셈 1) 행렬-체인 곱셈이란?-다음에 소개할 동적 프로그래밍은 행렬 곱셈 문제를 해결하는 알고리즘이다. 행렬 곱셈을 위한 다음과 같은 n개의 행렬 체인(순서) 이 주어지고, 행렬의 곱을 계산하려고 한다.  A1A2... An - 먼저 n개의 행렬을 어떻게 곱할지 애매함(ambiguity)을 없애기 위해서   괄호로 묶고나면, 두 개의 행렬을 곱하는 표준 알고리즘을 서브 루틴으로 이용해  위의 식의 결과를 계산할 수 있다.  - 행렬의 곱은 결합 법칙이 성립하므로, 괄호를 어떤 방법으로 묶더라도 결과는 같다.  어떤 행렬들의 곱이 하나의 행렬 또는 완전히 괄호로 묶인 두 행렬의 곱일 때  완전하게 괄호로 묶였다고 한다.  - 예를 들어, 행렬 의 곱 A1A2A3A4를 계산한다면,  다음과 같이 5가지 방법으로..
[Introduction to Algorithms] 이진 검색 트리 1) 이진 검색 트리란? - 검색 트리 자료구조는 SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE를  비롯해 많은 동적 집합 연산을 지원한다.  따라서 검색 트리를 사전(dictionary) 및 우선순위 큐(priority queue)로 사용할 수 있다. - 이진 검색 트리에 대한 기본 연산은 트리의 높이에 비례하는 시간에 수행된다.  n개의 노드로 이루어진 완전 이진 검색 트리(complete binary search tree)에 대해  이런 연산들은 최악의 경우, O(lgn) 시간에 실행된다.  그러나 트리가 n개의 노드가 선형으로 연결된 모양일 경우 평균 O(n) 시간에 수행된다. - 앞으로 만들어진 이진 검색 트리의 높이의 기댓값..
[Introduction to Algorithms] 해시 테이블 - 체이닝에 의한 충돌 해결 1) 체이닝이란?  - 체이닝에서는 위 그림과 같이 같은 위치에 해시되는 모든 원소를 같은 연결 리스트에 넣는다.  위치 j는 위치 j에 해시된 모든 원소로 이루어진 리스트의 처음을 가리키는 포인터를 가지고 있다.  이런 원소가 존재하지 않는다면 위치 j는 NIL 값을 가진다.  - 체이닝에 의해 충돌이 해결될 때 해시 테이블 T의 사전적 작업을 구현하기가 매우 쉽다.  CHAINED-HASH-INSERT(T, x)리스트 T[h(x.key)]의 맨 앞에 x 삽입CHAINED-HASH-SEARCH(T, k)리스트 T[h(k)]에서 키 k를 가지는 원소를 검색CHAINED-HASH-DELETE(T, x)리스트 T[h(x.key)]에서 x를 삭제 - 삽입 프로시저는 최악의 경우 수행시간이 O(1)이다.   삽..
[Introduction to Algorithms] 해시 테이블 1) 직접 주소화 방법의 단점과 해시 테이블  - 직접 주소화 방법의 단점은 명백하다. 전체 집합 U가 크다면 일반적인 컴퓨터의 메모리 공간에서는  크기 |U|가 가지는 테이블 T를 저장하는 것은 비실용적이거나 불가능하다.  게다가 실제 저장되는 키들의 집합 K는 U에 비해 상대적으로 작아서  T를 위해 할당된 대부분의 공간은 낭비된다. - 사전에 저장된 키들의 집합 K가 모든 가능한 키들의 전체 집합 U에 비해 훨씬 작을 때,  해시 테이블은 직접 주소 테이블보다 훨씬 작은 공간을 필요로 한다. -  특히, 원소의 검색에 소요되는 시간이 단지 O(1)인 이점을 유지하면서 사용 저장 공간을 O(|K|)로 줄일 수 있다.  다만, 직접 주소화 방법에서는 이 수행시간이 최악의 경우 수행시간에 해당되지만  해..
[Introduction to Algorithms] 동적 프로그래밍 1) 동적 프로그래밍이란?- 동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결한다  분할정복 알고리즘은 문제를 서로 겹치지 않는(disjoint) 부분 문제로 분할하고,  해당 부분 문제를 재귀적으로 해결한 후,  해결 결과를 결합하여 원래의 문제를 해결한다.  - 반면, 동적 프로그래밍은 부분 문제가 서로 중복될 때, 즉, 부분 문제가 다시 자신의 부분 문제를 공유할 때 적용할 수 있다.  이 경우, 분할정복 알고리즘은 공유되는 부분 문제를 반복적으로 해결하여 일을 필요 이상으로 더 많이 하게 된다.  동적 프로그래밍 알고리즘을 이용하면 모든 부분 문제를 한 번만 풀어   그 해를 테이블에 저장함으로써 그 해를 테이블에 저장함으로써   각 부분 문제를 풀 때마다 다시 계산하는..
[Introduction to Algorithms] 랜덤화된 퀵 정렬 1) 개요- 퀵 정렬의 평균적인 경우를 살펴볼 때 모든 입력이 똑같은 확률로 발생한다고 가정했다.  그러나 실제로는 이 가정이 언제나 들어맞지는 않는다.  이 때, 알고리즘에 랜덤화 기법을 적용함으로써 모든 입력에 대해 성능의 기댓값을 높일 수 있다.  때문에 입력이 충분히 큰 경우에는 정렬 알고리즘으로 랜덤화된 퀵 정렬을 많이 사용한다. - 입력을 명시적으로 뒤섞음으로써 임의화를 할 수 있는데,  이 같은 방법을 퀵 정렬에서도 적용할 수 있지만,   무작위 추출이라는 다른 랜덤화 기법을 사용하면 분석을 좀 더 간단히 할 수 있다.  - 매번 A[r]을 기준으로 선택하는 대신 부분 배열 A[p...r]에서 임의의 원소를 선택하고  이 원소와 A[r]을 교환한다.  이렇게 기준 원소를 p, ... ,r 범..
[Introduction to Algorithms] 퀵 정렬 - 퀵 정렬의 성능 1) 개요- 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한지 그렇지 않은지에 따라 달라지고,  분할의 균형도는 분할할 때마다 어떤 기준 원소를 사용하는지에 달려 있다.  분할이 균등하게 되면 퀵 정렬은 (점근적으로) 병합 정렬처럼 빠르게 동작한다.   그러나 균등하지 않다면 삽입 정렬처럼 느리게 동작한다.  이 글에서는 분할이 균등하게 또는 불균등하게 이루어질 때 퀵 정렬의 성능이 어떻게 되는지를   약식으로 조사한다.  2) 분할을 가장 나쁘게 하는 경우 - 퀵 정렬에서 최악의 경우는 분할과정에서 원래의 문제를 n-1개 짜리와 0개 짜리 부분 문제로 나누는 때다.  재귀 호출을 할 때마다 이런 불균등 분할이 발생한다고 가정해보자.  분할 과정에 소요되는 시간은 O(n)이다.   크기가 0인 ..
[Introduction to Algorithms] 힙 만들기 1) 힙 만들기 과정  - 배열 A[1...n]을 최대 힙으로 바꿀 경우, MAX-HEAPIFY 프로시저를 바닥에서부터 위로 올라가는 식으로 이용한다.  (여기서 n = A.length).   BUILD-MAX-HEAP 프로시저에서 트리의 나머지 노드에 대해 MAX-HEAPFIY를 수행한다. BUILD-MAX-HEAP(A)A.heap-size = A.lengthfor i = [A.length/2] downto 1 MAX-HEAPIFY(A, i)   - 위 그림은 BUILD-MAX-HEAP 동작의 예를 보여준다.   BUILD-MAX-HEAP이 정확하게 동작함을 보이기 위해 다음과 같은 루프 불변성을 이용한다.   - 2-3행에 있는 for 루프에서 반복을 시작할 때마다 노드 i+1, i+2, ... ..

티스토리툴바