알고리즘과 자료구조 01 알고리즘 개요

 

 

알고리즘 개요

 

 

1. 알고리즘(algorithm)

 

: 어떤 문제의 해답을 구하기 위한 단계적인 절차를 순서대로 명확하게 나타낸 것

 

ex. 두 변수 a, b의 값을 맞바꾸는 알고리즘

1. 변수 c를 준비한다

2. 변수 a의 값을 변수 a에 저장한다

3. 변수 b의 값을 변수 a에 저장한다

4. 변수 c의 값을 변수 b에 저장한다

 

 

2. 알고리즘 조건(특성)

 

1) 명확성

- 알고리즘을 구성하는 각 명령의 의미는 모호하지 않고 명확해야 함

 

2) 유한성

- 알고리즘은 일정한 시간 내에 종료되어야 함

- 무한루프를 포함하면 안 됨

 

3) 유효성

- 컴퓨터에서 실행 가능해야 함

- 현대의 기술로 해결이 가능해야 함

 

4) 효율성

- 효율적인 알고리즘일수록 가치가 높음

- 빠르고 메모리 사용량이 적어야 함

 

ex. 1-N까지 더하는 알고리즘

1	sum = 0
2	num = 1
3	sum = sum + num
4	num = num +1
5	if (num <= N) then go to step 3
6	otherwise print(sum)

 

알고리즘 효율성 개선

1	sum = (N*(N+1))/2
2	print(sum)

-> 경우에 따라 여러 가지 알고리즘이 존재할 수 있다

 

 

3. 알고리즘의 표현 방법

 

1) 자연어(한글, 영어 등)로 표현

 

2) 흐름도(flowchart)로 표현

- 누구나 이해할 수 있는 장점

- 알고리즘이 복잡해지면 흐름도가 지나치게 비대하고 복잡해질 수 있음

 

3) 의사코드(pseudo-code)로 기술

- 프로그램 코드와 유사한 형태(상세한 detail 생략 가능)

- 논문 등에서 알고리즘을 표현할 때 널리 활용됨

-> 복잡한 알고리즘을 표현할 때 유용

 

4) 프로그램 언어로 기술

- 파이썬으로 프로그래밍

-> java 등 다른 언어에 비해 단순한 표현 가능

- 실행이 간편함

- 의사코드와 유사함

 

 

4. 알고리즘 정확성 검증

 

1) 실험적 분석(test)

- 다양한 입력값을 이용해 예상된 결과가 도출되는지 검증

- 동치(동등) 분할 입력

- 경계값 입력

 

2) 증명적 분석(수학적 방법 활용)

- 수학적 귀납법

 

 

알고리즘 효율성 분석

 

 

1. 시간 효율성

 

1) 시간 효율성

- 알고리즘이 얼마나 빠른 시간 안에 결과를 도출하는가

- 일반적으로 데이터의 입력 크기에 따른 시간 복잡도(time complexity)로 표현

 

2) 시간 복잡도

- 데이터의 입력 크기에 따라 필요한 연산의 수

- 데이터 크기 N이 증가함에 따라 필요한 연산의 수가 얼만큼 증가하는가

 

3) 시간 복잡도 예시(빅오 표기)

O(1)	연산의 수가 데이터 크기 N과 관계없이 일정 -> 가장 효율적인 최상의 알고리즘
O(logN)	연산의 수가 데이터 크기 N이 증가함에 따라 logN에 비례해 증가
O(N)	연산의 수가 데이터 크기 N이 증가함에 따라 N에 비례해 증가
O(NlogN)	...
O(N²)	...
O(2ⁿ)	...

- 효율성 비교: O(1) > O(logN) > O(N) > O(nlogN > O(N²) > O(2ⁿ)

 

4) 시간 복잡도 종류

- 최선(best case) 시간 복잡도

- 평균(average) 시간 복잡도

- 최약(worst case) 시간 복잡도

 

5) 알고리즘 예시

- O(1) 알고리즘 예시

sum = (N*(N+1))/2 print(sum)

 

- O(N) 알고리즘 예시

1	sum = 0
2	num = 1
3	sum = sum + num
4	num = num +1
5	if (num <= N) then go to step 3
6	otherwise print(sum)

 

6) 전체 알고리즘이 여러 알고리즘으로 구성된 경우

- 가장 복잡도가 높은 알고리즘에 의해 전체 복잡도가 결정됨

 

ex.

1단계 알고리즘 시간복잡도: O(1)

1단계 알고리즘 시간복잡도: O(N)

1단계 알고리즘 시간복잡도: O(logN)

-> 전체 알고리즘 시간복잡도: O(N)

 

 

2. 공간 효율성

 

- 알고리즘이 얼마나 많은 메모리를 사용하는가

 

 

알고리즘 설계 기법

 

 

1. 알고리즘 설계 기법

 

1) brute-force(억지) 기법

2) decrease and conquer

3) divide and conquer

4) dynamic programming

5) montecarlo simulation

6) greedy(탐욕) 기법