학습출처 : [KOCW 건국대학교 김강일 교수님 알고리즘 강의]
1. 학습목표
- 알고리즘 구현에서의 문제점
- 알고리즘의 표현 방법
- 알고리즘 분석 방법
1-1 알고리즘? :
주어진 문제를 해결하기 위한 일련의 Actions 전체를 의미함
1-2 Actions? :
컴퓨터 연산 (Read, Write, Add, Move..)
1-3 문제? :
입력과 출력의 관계 표현
- 랜덤하게 분산된 숫자카드가 있다.
- 컴퓨터 연산을 이용해 작성된 정렬 알고리즘을 Run
- 입력된 X에 대한 출력 값 Y를 도출한다.
이것들을 잘 적용해서 문제를 해결하는 것이 알고리즘의 목표
이러한 알고리즘의 특징들은 다음과 같다.
Correctness (정확성)
- 주어진 X에 대해 알고리즘이 정확한 Y를 도출해야한다.
Runnability (실행성)
- 컴퓨터가 작성된 알고리즘을 주어진 시간안에 실행할 수 있어야 한다.
Finiteness (유한성)
- 작성된 알고리즘이 유한한 시간 이내에 종료되어야 한다.
Efficiency (효율성)
- 효율적인 알고리즘이 시공간적인 관점에서 더 좋다.
2. 최초의 알고리즘
- 유클리드 알고리즘 (기원전 300년)
( GCD = 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법 )
만약 100과 125라는 수가 있을때 GCD를 구하려면 어떻게 해야할까?
-
check every number
- 둘중 작은 수를 선택하여 1부터 해당수까지 iteration 하며 100과 125로 나누어 지는 수를 구한다. (비효율적)
-
유클리드 알고리즘
- N과 N이 주어진다.
N = arg1, M = arg2- N과 M이 같다면 N을 리턴.
if (N == M) then return N- N, M이 1인경우
Else if ( N = 1 or M = 1 ) then return 1- 아닌 경우 (최대 숫자를 줄여 최종적으로 M과 N 중 하나가 최대공약수가 됨)
if (N > M) then N = N - M Else M = M - N- 결과
Euclid(a, b) Integer a,b; <- a >= b >= 0 //input GCD of a and b // output 1. if (b = 0) return a 2. return Euclid(b, a minus b)
3. 알고리즘을 표현하는 방법
-
알고리즘을 표현하는 방법에는 여러가지가 있음
- sudo, 자연어, 플로차트, 프로그래밍 언어, 수식 등
-
꼭 실행되는 코드를 모두 구체적으로 작성할 필요는 없음
-
아이디어와 프로세스가 얼마나 명확한지가 가장 중요하다.
EX) 자연어로 작성된 알고리즘 표현 방법 (가장 큰 숫자 카드 찾기)
1. 첫번째로 뽑은 숫자카드 기억하기
2. 다음 숫자카드와 기억한 숫자카드 비교하기
3. 비교된 두 수중, 더 큰 수를 기억한다
4. 더 열어볼 카드가 없을때까지 2번과정 반복
5. 카드가 다 떨어지면 마지막으로 기억하고 있는 숫자 return
4. 알고리즘의 카테고리
4-1 문제 해결 전략에 따른 카테고리
- Divide and Conquer (분할정복 알고리즘)
- Greedy (탐욕법)
- Dynamic Programming
- Approximation
- Search
- Backtracking
- Branch-and-Bound
4-2 문제 종류에 따른 카테고리
- Sorting Problem (정렬 문제)
- Graph Problem (그래프 문제)
- Geometric Problem (기하학 문제)
4-3 컴퓨터 환경에 따른 카테고리
- Parallel (분산 처리)
- Distributed
- Quantum (연산 방식이 다름)
4-4 심화 알고리즘에 따른 카테고리
- Genetic Algorithm
- Random Algorithm
- Intelligence Algorithm
5. 알고리즘의 효율성
5-1 computation time (Time complexity):
컴퓨터가 특정 작업을 수행하는 데 걸리는 시간
5-2 space (Space complexity):
사용되는 메모리 공간
5-3 Time complexity (시간복잡도) ?
- 알고리즘의 실행 시간을 평가하는 방법
- 코드를 실행하는데 걸리는 시간을 확인하거나 디버깅 및 성능 향상을 위해 실행 시간과 관련된 정보를 출력
- 허나, 이러한 소요시간은 컴퓨팅 환경에 의존하기 때문에 환경마다 상이 할 수 있다는 단점이 있음
time complexity를 유클리드 알고리즘으로 나타내보면 아래와 같다.
Pseudo Code
max = A[0] // write 1
for i = 1 to 9 // write 9
if (A[i] > max) max = A[i] // comparison 9, whrite 9, Read 9
return max // write 1
- 메모리에 write를 한다. (1번)
- i (1 to 9) iteration 하며 write 한다 (9번)
- A[i]와 max 값을 비교하며 max값을 재할당한다.
(비교연산 9번, write 9번, read 9번)
5-3-1 Memory cost
read/write cost : m
comparison cost : n
> M * 29 + N * 95-4 계산 한계
- 코드가 복잡해지게 되면 이러한 계산 작업은 소모적인 일이 된다.
- 이러한 한계를 극복하기 위해 모든 frequency를 계산하지 않는 방법을 찾게됨
5-5 time complexity를 표현하는 방법
- worst case analysis
- Average case analysis
- Best case analysis
- 표현하는 방법이 세 개나 존재하는 이유는 이름처럼 최고, 최악의 상황의 배열이 입력으로 들어올 수 있기 때문이다.
- 예를 들어, 정렬 알고리즘을 사용해야하는 문제가 있다고 가정했을때,
정렬된 배열을 입력 받는다면 수행할 작업이 없으니, Best case라고 할 수 있다.
5-6 가장 중요한 analysis는?
- 가능하다면, 모두 사용하는 것이 좋음
- 그러나, 복잡한 알고리즘을 분석할때 복잡해진다. (라임..)
(However, analysis is so complex for complex algorithms) - 그렇기 때문에, 목적에 맞게 분석 방법을 선택하는 것이 좋다.
- 보통은 worst case를 주로 사용
5-7 점근 표기법
Big-O (O)
- 상한을 의미하며, 알고리즘의 최악의 실행 시간을 나타냄.
- 입력 크기 N이 증가함에 따라 알고리즘의 실행 시간이 얼마나 빨리 증가하는지를 나타낸다.
- 예를 들어, O(N)은 선형 시간 복잡도를 가지는 알고리즘을 의미.
Big-Omega (Ω)
- 하한을 의미하며, 알고리즘의 최선의 실행 시간을 나타냄.
- 입력 크기 N이 증가함에 따라 알고리즘의 실행 시간이 얼마나 빨리 감소하는지를 나타낸다.
- 예를 들어, Ω(1)은 상수 시간 복잡도를 가지는 알고리즘을 의미.
Big-Theta (Θ)
- 상한과 하한이 동시에 적용되는 경우로, 알고리즘의 실행 시간이 입력 크기에 대해 일정한 범위 내에서 변하지 않음을 나타냄.
- 입력 크기 N이 증가함에 따라 알고리즘의 실행 시간이 일정하게 유지되는 경우에 해당.
- 예를 들어, Θ(N)은 선형 시간 복잡도가 일정한 범위 내에서 유지되는 알고리즘을 의미.
O(1) : Constant time (상수 시간)
O(logn) : Logarithmic time (로그 시간)
O(n) : Linear time (선형 시간)
O(nlogn) : Log-linear time (선형 로그 시간)
O(n^2) : Quadratic time (2차 시간)
O(n^3) : Cubic time (3차 시간)
O(2^n) : Exponential (지수 시간)
- 밑으로 갈수록 알고리즘이 느려짐
-끝-
