자료구조와 알고리즘 #5 의사 코드의 표현과 성능 분석

2020/09/08 - [Learn/자료구조와 알고리즘] - 자료구조와 알고리즘 학습 #4 추상 자료와 알고리즘

자료구조와 알고리즘 학습 #4 추상 자료와 알고리즘

---

알고리즘

의사 코드(Pseudo-code)

추상화 방법

 - 의사 코드, 즉 알고리즘 기술 언어(ADL, Algorithm Description Language)를 사용하여 프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘을 표현

 - 특정 프로그래밍 언어가 아니므로 직접 실행은 불가능한 대신 일반적인 프로그래밍 언어의 형태이므로 원하는 특정 프로그래밍 언어로의 변환 용이

 

기본요소

 - 기호 : 변수, 자료형 이름, 프로그램 이름, 레코드 필드 명, 문장의 레이블 등을 나타내며 문자나 숫자의 좆합으로 첫 문자는 반드시 영문자를 사용한다.

 - 자료형 : 정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자료형을 의미

 - 연산자 : 산술 연산자, 관계 연산자, 논리 연산자와 같은 연산자들을 의미

 

지정문

 변수에 값을 지정하는 방법이다.

 

문법 : 변수 <- 값

지정 연산자 (<-)의 오른쪽에 있는 값(또는 식의 계산 결과 값이나 변수의 값)을 지정 연산자(<-)의 왼쪽에 있는 변수에 저장하라는 의미다. 지정문에 사용할 수 있는 식은 산술식, 부울식, 문잦식 등 모든 연산식을 사용할 수 있다.

 

마침(;)

 명령문의 끝은 세미콜론(;)을 이용하여 표시한다.

 

조건문

 조건에 따라 실행할 명령문이 결정되는 선택적 제어구조를 만든다.

 

1) if문

 하나 이상의 명령문을 중괄호({})로 묶으면 하나의 명령문으로 취급한다.

 

문법 : if-then-else 

 if(조건식) then 명령문 1; else 명령문 2;

i <- 0;
if(i == 0) then /* 'Hello World' 출력*/ ;
else /* 'Bye World' 출력*/ ;

//i가 0이면
//0이 아니면

if(조건식1) then 명령문 1;

else if(조건식 2) then 명령문 2;

else 명령문 3;

i <- 5;

if( i < 5) then /*"5보다 작음" 출력*/;
else if(i > 5) then /* "5보다 큼" 출력*/;
else /*"5와 같음" 출력*/;

// 5보다 작으면
// 5보다 크면
// 모두 아니면

 

2) case 문

 - 여러 조건식 중에서 해당하는 조건식을 찾아서 그에 대해 정해진 명령을 수행하는 조건문으로 하나의 case문은 중첩 if문과 같은 의미를 나타낸다.

 

문법 : case { 조건식 1: 명령문 1; 조건식 2: 명령문 2;  else : 명령문 3;}

 

i = 0;
case {
	case i = 0: /*"Hello" 출력*/;
    case i = 1: /*"World" 출력*/;
    else : /* "Bye" 출력*/;
}

//i가 0이면
//i가 1이면
// 모두 아니면

반복문

 - 일정한 명령을 반복 수행하는 루프(loop) 형태의 제어구조

 

1) for문

 문법 : for (초기값; 조건식; 중감값) do { 명령문; }

초기값 : 반복문을 시작하는 값

조건식 : 반복 수행 여부를 검사하는 조건식

증감값 : 반복 회수를 계산하기 위해서 반복문을 한번 수행할 때마다 증가 또는 감소 시키는 값

명령문은 하나 또는 여러개일 수도 있다.

 

for(i<-0; i<10; i+=1)
do{
/* i 출력 */;
}

//i가 0부터 9까지 1씩 증가하며 i를 출력한다.

2) while-do문

- 조건식만 검사하여 조건식이 참인 동안 명령문을 반복 수행한다.

문법 : while(조건식) do{명령문;}

 

i <- 0;
while(i < 10)
do{ i+=1; }

//i는 0
//i가 10보다 작으면
//i를 1 증가

3) do-while 문

 - 먼저 명령문을 수행하고 그 다음에 조건이 맞으면 반복수행을 한다.

문법 : do{명령문;} while(조건식);

i <- 0;
do{
i += 1;
}while(i < 10);

//i는 0이다.
// i를 1 증가시킨다.
// i가 10보다 작으면
// 다시 1을 증가시킨다.

 

함수문

 - 어떤 문제를 처리하는 프로그램을 만들 때, 한 개의 프로그램으로 구선하는 것 보다 처리할 작업 별로 모듈화하여 작은 단위 프로그램(함수) 여러개로 나누어 구성하는 것이 효율적이다.

 

장점 : 

 - 같은 일을 하나의 단위 프로그램에서 독립적으로 수행하게 되어 프로그램의 크기가 줄어든다.

 - 수정과 관리, 재사용이 용이하다.

 - 함수 호출을 통해 독립적으로 실행되며, 매개 변수를 사용하여 다른 함수 및 프로그램과 서로 연결된다.

 

문법 : 

함수 이름(매개변수)

 명령문;

 return 결과값;

end

 

function(i)
 i = i+5;
 return i;
end;

//function 함수는 i를 받고 i에 5를 더한 후 i를 돌려주고 종료한다.

 

성능분석

기준

-문제에 대한 해결방법은 하나 이상일 수 있다. 따라서 그 중 가장 효율적인 알고리즘을 결정해야 한다.

 

판단 기준

 - 정확성 : 올바른 입력에 대하여 유한 시간 내에 올바른 결과를 출력하는지를 판단

 - 명확성 : 알고리즘의 표현이 얼마나 이해하기 쉽고 명확하게 작성되엇는지를 판단

 - 수행량 : 일반적인 연산을 제외하고 알고리즘의 특성을 나타내는 중요 연산들을 분석

 - 메모리 사용량 : 사용하는 명령어, 변수, 정보를 젖아하기 위한 메모리를 얼마나 사용하는지를 판단

 - 최적성 : 알고리즘을 적용할 시스템의 사용 환경에 따라 수행량과 메모리 사용량이 달라지기 때문에 이들간의 최적화를 판단

 

분석 방법

 1) 공간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양

  - 공간 복잡도 = 고정 공간 + 가변 공간

 = 고정 공간 : 프로그램의 크기나 입출력 횟수에 상관없이 고정적으로 필요한 저장 공간으로 프로그램의 저장곤간, 변수 및 상수들을 저장하기 위한 공간

 = 가변 공간 : 실행 과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장하는 공간

 

 2) 시간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료하기 까지의 총 소요시간

 - 시간 복잡도 = 컴파일 시간 + 실행 시간

 =컴파일 시간 : 프로그램 마다 거의 고정적인 시간 소요

 = 실행 시간 : 컴퓨터의 성능에 따라 달라질 수 있으므로, 실제 실행시간 보다는 명령문의 실행 빈도수에 따른 계산

 

- 실행빈도수의 계산

 지정문, 조건문 ,반복문 내의 제어문과 반환문은 실행 시간 차이가 거의 없으므로, 하나의 단위 시간을 갖는 기본 명령문으로 취급하여 실행빈도수를 계산

 

 

 - 시간 복잡도 표기법

 빅 오(Big Oh) 표기법을 사용한다.

 

 = 빅 오 표기법의 순서

  가) 실행 빈도수를 구하여 실행시간 함수를 찾는다.

  나) 실행시간 함수의 값에 가장 큰 영향을 주는 n에 대한 항을 선택한다.

  다) 계수는 생략하고 O(Big Oh)의 오른쪽 괄호 안에 표시 한다.

 

예시 ) 피보나치 수열의 시간 복잡도 = O(n)

 실행시간 함수 : 4n+2

 N에 대한 항을 선택 : 4n

 계수 4는 생략하고 O의 오른쪽 괄호 안에 표시 O(n)