정말 애를 많이 먹었다. 자료구조를 안해둬서.. 선수과목을 꼭 이행하고 올리는것을 추천한다.
알고리즘을 공부하기 위해 자료구조만 2주 넘게 한거같다..
1.
알고리즘 설계기법 원리 및 특징
1.1.
분할정복 방법
분할
정복 방법의 원리는 문제를 더 이상 나눌 수 없을 때 까지 반복해서 나눠서 각각 문제를 해결 한 후 결합하여 원래 문제를 해결하는 방식입니다.
분할
정복 방법의 특징은 나눠진 작은 문제는 원래 문제와 동일, 입력크기의
감소, 하향식 접근방법, 분할된 문제는 순환적 분할과 결과 결합이 가능합니다.
1.2.
동적 프로그래밍 방법
동적
프로그래밍의 원리는 입력크기가 작다면 쉽게 해를 구할 수 있는 것을 이용하는 것입니다.
동적
프로그래밍의 특징은 입력의 크기만 작고 원래의 문제와 같음, 상향식
접근방법, 작은 문제들이 서로 독립적, 최적화 문제 해결에 주로 사용, 최적성의 원리가 적용됩니다.
1.3.
욕심쟁이 방법
욕심쟁이
방법의 원리는 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선인 최적 해를 선택하여 구하는 방법입니다.
욕심쟁이
방법의 특징은 최적화 문제 해결에 주로 사용, 최적성의 원리가
적용, 오직 하나의 최적화만 고려합니다. 그러하여 해를 구할 수 도 없습니다.
2.
알고리즘 종류와 특징/성능
2.1.
분할정복 방법
2.1.1.
이진 탐색
이진탐색
알고리즘은 문제를 절반으로 분할하여 한쪽을 사용하지 않고 나눠지지 않을 때까지 분할해나가면서 분할할 때마다 한쪽을 쓰지 않는 것을 의미합니다.
이진탐색의
특징은 결합단계가 없음, 데이터가 오름차순으로 정렬, 빈번한 데이터의 변경이 있는 데이터에 대해서는 부적함, 순환 형태, 혹은 반복 형태로 구성됩니다.
이진
탐색의 성능은 최대 비교 횟수 = 최대 분할 횟수 – 1 입니다.
이진탐색의
성능은 T(n) = 맨 바깥 수준에서의 비교 횟수 + 순환 호출에서의 비교 횟수
이진탐색의 성능은 점화식으로 표현하면 T(n) = T(
) +
1 ( n > 1), T(1) = 1입니다.
점화식을
풀어서 표현하면 이진 탐색의 시간 복잡도는 T(n) = log n + 1 = O(log n)가 됩니다.
2.1.2.
합병 정렬
합병
정렬이란 분할한 동일한 크기의 부분배열을 가진 두 개의 배열을 각각 순환적으로 정렬한 후, 정렬된 부분배열을 합병하여 하나의 정렬된 배열로 만듭니다.
분할
정복의 특징은 알고리즘의 성능은 데이터와 선형적 비례관계, 제자리
정렬 알고리즘이 아님 , 부각되는 알고리즘으로 비교를 할 2개가 나올 때까지 분할, 합병하면서 비교하여 정렬합니다.
최악의 경우의 비교 횟수는
+
- 1
= n-1이며 합병에 걸리는 시간은
(n)
이게 됩니다.
강의에
나온 2.3 알고리즘의 성능은 아래와 같습니다.
점화식은 T(n)
= T(
) + T(
) +
(n) ( n > 1)입니다. 시간복잡도는 2T(
) +
(n)
입니다.
2.1.3.
퀵 정렬
퀵
정렬 알고리즘의 특징은 최악의 경우 선택 정렬과 삽입 정렬 같은 다른 정렬 알고리즘보다 빠르지 않음,
피벗을 임의로 잘 선정한다면 평균 성능 이상을 보일 가능성이 매우 높음, 결합단계가 없음, 피벗이 존재합니다.
퀵
정렬의 성능은 최악, 최선, 평균을 구분하여 이용하여 표현하겠습니다.
최악의
점화식은 T(n) = T(0) + T(n-1) +
(n), n > 0 = T(n-1)+
(n)입니다. 최악의 시간복잡도는 O(
) 입니다.최선의 점화식은 T(n) = T(
) + T(
) +
(n) = 2T(
) +
(n),
n > 1입니다. 최선의 시간복잡도는 O(n log n) 입니다.
평균의
점화식은 T(n) =
(
T(i - 1) + T(n – i)) +
(n),
n > 2입니다. 평균의 시간복잡도는 O(n log n)입니다.
2.1.4.
선택 문제
선택
문제 알고리즘이란 n개의 원소가 임의의 순서로 저장된 배열[0..n-1]에서 I번째로 작은 원소를 찾는 문제입니다. 데이터를
오름차순으로 정렬한 후 I번째 원소를 찾는 직관적인 방법이
있습니다.
I
번째로 작은 원소를 찾을 때에 빗대어 특징과 성능을 설염 하도록 하겠습니다.
특징은
선택한 원소를 찾는 알고리즘, 결합 과정이 없습니다.
성능은 최악과 평균으로 나누겠습니다. 퀵 정렬의
경우 최악은 O(
),
평균은 O(n)입니다. 항상 일정한 비율로 분할한다면 최악은 O(n), 평균은 O(n)입니다.
2.2.
동적 프로그래밍 방법
2.2.1.
피보나치수열 문제
피보나치수열이란
어떤 수열의 항이, 앞의 두 항의 합과 같은 수열을 말합니다.
피보나치수열의
특징으로는 소문제가 독립이 아니어서 분할정복 방법을 적용할 수 없습니다.
피보나치수열의
성능인 시간 복잡도는 O(n)입니다.
2.2.2.
연쇄 행렬 곱셈 문제
특징은
결합법칙 성립, 원리최적의 곱셈순서 도출하므로 최적성의 원리가
성립되고 동적 프로그래밍 방법 해결이 가능해집니다.
성능을 알고리즘 3.2를 예제로
시간복잡도는 O(
)입니다.
2.2.3.
스트링 편집거리
스트링
편집거리의 특징으로는 방향성을 통한 거리 계산 가능, 최적성의
원리를 만족해야하고, 두 문자열 사이의 편집거리를 구할 수
있습니다.
성능은
첫 열, 첫 행은 O(n+m)
시간에 수행됩니다. E[i][j] 계산을 위한 이중 for루프에서의 복잡도는 O(nm)입니다.
2.2.4.
플로이드 알고리즘(모든 정점 간의 최단 경로)
특징으로는
가중치의 합이 음수가 없고, 최소 비용 경로, 최단 경로를 구할 수 있습니다.
성능은 교재의 알고리즘 3.4의 시간
복잡도를 계산하였을 때 O(|V
)입니다.
2.2.5.
저울 문제
특징으로는
추의 최대 공약수를 이용한 무게를 확인, 최적성의 원리 만족, 물체의 무게가
보다
크면 모든 경우를 따져 보는 직관적인 방법보다 비효율적입니다.
성능은
교재에 알고리즘 3.6의 초기화에는 O(M) 이 필요하고 S[i][k] 계산을 위한 이중루프 이용 시 시간 복잡도 O(nM)입니다.
2.3.
욕심쟁이 방법
2.3.1.
동전 거스름돈 문제
특징은
거스름돈을 계산, 임의로 값이 정해지는 일반적인 경우는 사용이
불가능하기도 합니다.
성능은
시간 복잡도는 동전의 수만큼 걸리는 O(n)입니다.
2.3.2.
배낭 문제
특징은
물체를 쪼갤 수 없는 0/1 배낭 문제는 해결 불가, 물체를 쪼갤 수 있다고 가정, 단위당 이익을 계산하여 가장 좋은 것을 우선으로 넣습니다.
성능인
시간 복잡도는 O(n) 이고 정렬까지 포함하면 O(n log n)입니다.
2.3.3.
최소 신장 트리
특징은
가중치가 합이 가장 적은 최소 신장 트리를 구합니다.
2.3.3.1.
크루스칼 알고리즘
특징은
간선이 없는 상태에서 사이클을 만들지 않으면 추가, 최종적으로
하나의 연결 선분을 만듭니다.
성능은
초기화하는데 O(1) 시간이 걸리고, 반복하면 O(I V I)가 되고 정렬을 하게 되면 O(| E | log | E |)입니다.
2.3.3.2.
프림 알고리즘
특징은
임의의 한 정점에서 시작, 부수된 가중치가 최소인 간선을
추가합니다.
성능은
인접 행렬로 구현시 O( | V
)
이고 힙 사용 시 O(( |V| + |E|)log|V|)입니다.
2.3.4.
최단 경로(데이스트라 알고리즘)
특징은
음의 가중치를 갖는 간선이 없다고 가정, 단일 출발점 최단
경로를 구합니다.
성능은
인접 행렬로 구현시 O(| V
)이며
힙을 사용 시 O ((|V| + |E|) log |V| ) 가 됩니다.
2.3.5.
작업 스케줄링 문제
특징은
시작 시간이 빠른 것을 우선 처리, 가장 적은 개수의 기계를
사용하여 기계간 충돌이 발생하지 않고 모든 작업을 기계에 할당합니다.
성능인
시간 복잡도는 O(n log n)입니다.
2.3.6.
작업 선택 문제
특징은
완료시간이 빠른 작업을 우선 처리, 하나의 기계만을 사용해서
충돌 없이 최대 개수의 작업을 할당하는 문제입니다.
성능인
시간 복잡도는 O(n log n)입니다.
2.3.7
허프만 코딩
특징은
접두부 코드면서 최적 코드, 디코딩과 인코딩의 과정을 거침, 빈도수를 모를 경우 두 번 읽음, 출현하는 빈도수에 따라 각각 길이의 부호를 부여, 문자의 빈도나 확률정보를 사용하여 통계적 압축 방법입니다.
성능은
시간 복잡도는 최악, 최선, 평균 수행 모두 O(n log n+
m)입니다.
출처
: 방송통신대학교재,
알고리즘
댓글 없음:
댓글 쓰기