01. List 1 - 1차시

해당 알고리즘 게시글은 SW Expert Academy를 공부하고 정리하기 위해 작성한 글입니다. 

 

1. 알고리즘

유한한 단게를 통해 문제를 해결하기 위한 절차나 방법. 주로 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법

 

예) 1 ~ 100까지의 합

1. 1 + 2 + 3 + ... + 100 = 5050

2. {(1+100) + (2 + 99) + ... + (50 + 51)} * 50 = 5050

 

2. 알고리즘 표현법

1. 슈도코드

2. 순서도

 

1. 슈도코드

일반적인 언어로 코드를 흉내내어 알고리즘을 써놓은 코드

특정 언어로 프로그램을 작성하기 전에 알고리즘을 대략적으로 모델링하는데에 쓰인다.

 

2. 순서도

프로그램이나 작업의 진행흐름을 순서에 따라 여러가지 기호나 문자로 나타낸 도표. 흐름도라고도 하며 프로그램의 논리적인 흐름, 데이터의 처리과정을 표현하는데 사용한다. 프로그램의 전체적인 흐름과 과정 파악을 위해 필수적인 작업이다.

 

3. 알고리즘의 성능분석

1. 정확성 : 얼마나 정확하게 동작하는가?

2. 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가?

3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가?

4. 단순성 : 얼마나 단순한가? 알고리즘이 단순할수록 좋은 알고리즘이다.

5. 최적성 : 더 이상 개선할 여지없이 최적화되었는가?

 

알고리즘의 성능분석 기준으로 알고리즘의 작업량을 비교한다.

 

예) 1 ~ 100 까지의 합

1. 1 + 2+ 3 + ... + 100 = 5050 -> 99번의 연산

2. (100 * ( 1+ 100)) / 2 = 5050 -> 3번의 연산

2가 1보다 연산횟수가 훨씬 적은것을 확인할 수 있다. 더하려는 범위가 클수록 연산횟수의 차이가 커진다.

 

1. 시간복잡도

> 실제 걸리는 시간을 측정

> 실행되는 명령문의 개수를 계산 => 이 방법이 더 많이 쓰인다. 

 

알고리즘1

def calcSum(n) :
	sum = 0 # 1번
    for i in range(1, n+1) : # 1번
    	sum = sum + i # 1번
    return sum

시간복잡도 : 1 + n * 2 = 2n + 1

 

알고리즘2

def calcSum(n):
	return n * (n + 1) // 2 # 3번

시간복잡도 : 3

 

# 시간복잡도 표현법 

빅오(O) 표기법

시간복잡도 함수중 가장 큰 영향력을 주는 n에 대한 항만을 표시한다. 계수(Coefficient)는 생략한다.

예)

O(2n + 1) = O(2n) = O(n)

O(2n^2 + 10n + 100) = O(n^2)

O(4) = O(1)

 

요소 수가 증가함에 따라 각기 다른 시간복잡도의 알고리즘은 아래와 같은 연산수를 보인다.

요소 수(n)

0.1초에 1억개의 연산을 처리할 수 있는 기계를 가정했을 때 logN은 0.027마이크로초가 걸리고 N^2은 115.7일이 걸린다.