[자료구조] 알고리즘의 의미와 특성

 

 

 알고리즘(Algorithm) 

 

https://cdn.inflearn.com/wp-content/uploads/algorith.png

 

넓은 의미

자료구조와 함께 컴퓨터 프로그램을 구성하는 요소

컴퓨터 프로그래밍 = 자료 + 명령(연산)

 

좁은의미

어떠한 문제를 해결하기 위한 절차

 

ex. 1부터 100까지 합을 구하는 문제

문제를 해결하는 절차를 의사코드, Pseudo Code라고 한다.

 

 

---

 알고리즘의 필수 5가지 특성 

1. 입력(input)

외부에서 제공되는 자료가 0개 이상 있어야 한다

(입력할 수 없는 경우도 있다.)

 

2. 출력(output)

적어도 1개 이상의 결과를 만들어야 한다

 

3. 명백성(definiteness)

각 명령어는 의미가 모호하지 않고 명확해야 한다

 

4. 유한성(finiteness)

한정된 수의 단계 뒤에는 반드시 종료된다.

무한히 동작해서는 안된다

 

5. 유효성(effectiveness)

모든 명령은 실행가능한 연산이어야한다.

예를 들어 0으로 숫자를 나누는 연산과 같이

실행 할 수 없는 연산을 포함해서는 안된다.

 

---

 알고리즘과 자료구조와의 관계 

알고리즘의 성능은 자료구조에 의해 결정된다

여기서 성능이란 , 얼마만큼 빨리 수행되느냐이다.

 

같은 자료라고 하더라도 어떻게 표현되고 저장되느냐에 따라

사용가능한 알고리즘이 달라지기 때문이다

 

자료구조의 기본적인 연산을 구현하기 위해서 알고리즘을 사용한다. 

 

 

---

 

알고리즘의 표현

 

자연어 (Natural Language) 

사람이 사용하는 일반적인 언어로 표현

알고리즘 표현으로 부적절하며 기술하는 사람에 따라 일관성과 명확성이 달라진다

 

프로그래밍언어(Programming Language)

C와 같은 프로그래밍 언어로 표현

알고리즘을 구현소스를 통해 나태기 때문에

추가 구현단계가 필요 없다는 장점이 있다

하지만 너무 엄격하게 기술하면 비효율적인 경우가 생길 수 있다.

 

이를 표현하기 위한 대표적인 종류로

순서도와 의사코드가 있다.

 

순서도(Flow Chart)

: 알고리즘을 그림으로 도식화 하여 표현한 것

알고리즘 각 단계를 직관적으로 표현한다는 장점이 있지만

복잡한 알고리즘을 나타내기에는 비효율적이다.

 

 

기호	내용
타원	시작 혹은 종료
사각형	처리. 특정 연산을 실행
마름모	판단. 주어진 조건을 비교하여 해당 조건에 따라 흐름을 결정
평행사변형	자료. 데이터의 입력 혹은 출력을 나타낸다
화살표	흐름선, 실행 순서를 표시한다

 

의사코드(Pseudo Code)

특정 프로그래밍 언어가 아닌 가상의 유사한언어로 표현

프로그래밍 언어보다는 덜 엄격한 문법을 사용하고

자연어보다는 체계적으로 기술할 수 있으며

자료구조/알고리즘 책마다 약간 구문의 차이는 있다.

책에따라 가상코드 ,유사코드, 슈도 코드라고도 불린다.

 

 

1_지정문 : 변수에 특정 값을 대입하는 명령

변수 <- 값

 

2_ 조건문 : 조건식을 만족하는 지에 따라 흐름이 결정되는 명령

if (조건) then{
	명령;
} else if (조건) then{
	명령;
}

 

 

3_ 반복문 : 특정 명령을 여러번 반복적으로 수행하는 구조.

for 또는 while

for(초기값 ; 조건식 ; 증감값){
	명령문;
 }

---

알고리즘의 성능 분석

 

주어진 문제를 해결하기 위해 여러개의 다양한 알고리즘이 존재한다.

어떤 알고리즘을 사용해야하는가?

 

어떤 것이 효율적일지 알고리즘의 성능 분석이 필요

 

예를들어 , 1~100까지의 합을 구하는 문제가 있다고 할 때,

 (a) 100번의 연산(덧셈 100번)

1+2+3+4+5+6+7+...+99+100 

 

(b) 3번의 연산(덧셈 1번, 곱셈 1번 , 나눗셈 1번)

100*(1+100)/2

 

 

알고리즘 분석기준

 

- 공간 복잡도(Space Cmplexity)

메모리(저장공간)이 적게드는 것

 

- 시간 복잡도(Time Complexity)

1. 실제 걸리는 시간을 측정. 

하지만 그럴경우 CPU에 따라 달라질수 있으므로

아래 방법을 더 많이 사용함.

 

2. 실행되는 명령문의 개수를 계산

시간복잡도 함수 : 입력값에 따른 실행 연산의 빈도수. 

 

 

시간복잡도 비교시 빅-오(O) 표기법을 사용한다.

 

빅오표기법 (big-oh notation)

시간 복잡도 함수 중에서 가장 큰 영향력을 주는  n에 대한 항 만을 표시

 

계수는 생략하여 표시. 

상수일 경우 O(1) 로 표기하고 그 외 for문 반복하는경우 O(n)

 

시간복잡도에서 많이 사용되는 최고 차항들

위에서 부터 순서대로 복잡도가 높아진다