1장) 알고리즘과 문제해결

목차 

◆ 알고리즘이란

◆ ADL

▶ 지정문

▶ 조건문

▶ 반복문

▶ 함수문

▶ 입출력문

◆ 순환

◆ 점근식 표기법

◆ 순환 알고리즘과 점화식

-------------------------------------------------------------------------------------------------------------------------

◆ 알고리즘(algorithm)

     ▶ 특정문제를 해결하기 위해 기술한 일련의 명령문

◆ 프로그램(program)

     ▶ 알고리즘을 컴퓨터가 이해하고 실행할 수 있는 특정 프로그래밍 언어로 표현한 것

◆ 알고리즘의 요건

     ▶ 완전성과 명확성

 ＊ 수행결과와 순서가 완전하고 명확하게 명세되어야 함

 ＊ 순수하게 알고리즘이 지시하는대로 실행하기만 하면 의도한 결과가 얻어져야 함

     ▶ 입력과 출력

 ＊ 입력 : 알고리즘이 처리대야 할 대상으로 제공되는 데이타

 ＊ 출력 : 입력 데이터를 처리하여 얻은 결과

     ▶ 유한성

 ＊ 유한한  단계 뒤에는 반드시 종료

◆ ADL (Algorithm Description Language)

    ▶ 알고리즘 기술을 위해 정의한 언어

    ▶ 사람이 이해하기 쉽고, 프로그래밍 언어로의 변환이 용이 ( 여러가지 방식으로 기술할 수 있는거 있다 )

    ▶ 의사 코드 (pseudo-code) : ADL과 약간의 자연어로 기술한 것

    ▶ ADL 알고리즘에서 프로그램으로의 변환

   ▶ ADL 데이터 : 숫자, 부울(Boolean) 값 , 문자

   ▶ ADL의 명령문 :

＊ 종류 : 지정문 , 조건문 , 반복문 , 함수문 , 입력문 , 출력문

＊ 명령문 끝에는 세미콜론(;)을 사용

(알고리즘이란 끝)

-------------------------------------------------------------------------------------------------------------------------

◆ 지정문

▶ 형식 : 변수 ← 식;

▶ 식 ( expression )

＊산술식

＊부울식

- 결과 : 참 ( true ) 또는 거짓 ( false )

- 표현

》 논리 연산자 (and , or , not)

》 관계 연산자 (< , ≤ , ＝ , ≠ , ≥ , ＞)

＊ 문자식

▶ 제어 구조 : 순차적

◆ 조건문

▶ 제어 구조 : 선택적

▶ 종류 : if문과 case문

◆ if문

▶ if (cond) then S1

   else S2 

◆ case문

▶ case {

cond1 : S1

cond2: S2

· · ·

condn : Sn

else : Sn+1

}

◆ 반복문

▶ 제어 구조 : 일정한 명령문 그룹을 반복해서 수행하는 루프(loop) 형태

▶ 종류 : while문 , for문 , do-while문

◆ while문

 ▶형식

＊ while (cond) do {

S1

}

 ▶무한 루프

＊ while (true) do {

S1

}

◆  for문

▶ 형식

＊ for (initialization; cond; increment) do

S

▶ 동등한 while문

＊ initialization

    while (cond) do {

S

increment;

}

▶ 무한 루프

＊ for ( ; ; ) do

S

( cond의 기정값이 true이므로)

◆ do - while문

▶ 형식

＊ do {

S

 }while( cond );

▶ while문 과의 차이점은 최소한 한 번은 실행 된다는 것이다.

◆ 루프 명령문

▶ goto 명령문 : 루프에서 바로 빠져나갈 때 사용 (의도치 않는 오류가 발생할 확률이 높아 거의 안쓴다고 알고있음)

▶ exit문 : 자신을 둘러싸고 있는 가장 가까운 루프 밖의 명령문으로 제어를 이동시킴 (c언어의 break; 역할)

◆ 함수문

▶ 형식

＊ function-name(parameter_list) 

S

end funcion_name()

▶ 호출 함수로의 복귀

＊ return expr;

＊ 여기서 expr은 함수의 실행 결과

▶ 함수 호출

＊ function-name(argument_list)

＊ 인자 리스트(argument_list)는 타입과 수에 있어서 함수의 형식 매개 변수와 대응되어야 함

▶ 인자와 매개변수와의 연관

＊ 값 호출 (call by value) 규칙

＊ 각 인자의 실제 값이 호출된 함수로 전달

＊ 인자의 값이 주소(참조)가 되면 매개 변수에 주소 값이 전달되어 값은 데이터 지시

◆  입력 함수

▶  read (argument_list);

◆ 출력 함수

▶ print (argument_list);

◆ 인자

▶ 변수나 인용 부호가 있는 문자열

◆ 기타 명령문

▶ stop : 현재 진행 중인 함수의 실행을 정지

▶ 코멘트 : //는 그 행 끝까지 , /* 과 */은 코멘트의 시작과 끝 표시

▶ 다차원 배열 : a[n1,n2, ˙˙˙, nn]

◆ ADL 기술 규칙

▶ 함수의 입·출력 변수를 명확히 명세

▶ 변수의 의미를 알 수 있게 정의

▶ 알고리즘의 제어 흐름은 되도록 순차적

▶ 시각적 구분을 위해 들여쓰기 이용

▶ 코멘트는 짧으면서 의미는 명확히

▶ 함수를 적절히 사용

(ADL 끝)

-------------------------------------------------------------------------------------------------------------------------

◆ 알고리즘의 평가 기준

▶ 원하는 결과의 생성 여부

▶ 시스템 명세에 따른 올바른 실행 여부

▶ 프로그램의 성능

▶ 사용법과 작동법에 대한 설명 여부

▶ 유지 보수의 용이성

▶ 프로그램의 판독 용이

◆ 알고리즘의 성능 평가

▶ 성능 분석 (performance analysis)

＊  프로그램을 실행하는데 필요한 시간과 공간의 추정

▶ 성능 측정 (performance measurement)

＊ 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정

◆ 공간 복잡도 (space complexity)

▶ 알고리즘을 실행시켜 완료하는데 필요한 총 저장 공간

▶ Sa =Sc + Se

＊ Sc : 고정 공간

- 명령어 공간, 단순 변수 , 복합 데이타 구조와 변수 , 상수

＊ Se : 가변 공간

- 크기가 변하는 데이터 구조와 변수들이 필요로 하는 저장 공간

- 런타임 스택 (runtime stack)을 위한 저장 공간

◆ 시간 복잡도 (time complexity)

▶ 알고리즘을 실행시켜 완료하는데 걸리는 시간

▶ Ta =Tc + Te

＊ Tc  : 컴파일 시간

＊ Te  : 실행 시간

- 단위 명령문 하나를 실행하는데 걸리는 시간

- 실행 빈도수 (frequency count)     (c , c++ 기준 for문 1억번 실행시 1초 , Java는 for문 5천만번 실행시 1초)

◆ 점근식 표기법 (Asymptotic notation)

▶ Big-Oh (O)

▶ Big-Omega (Ω)

▶ Big-Theta (Θ)