제 1 장 1. 소프트웨어와 알고리즘

1.1 소프트웨어 소프트웨어란? 작은 의미로는 프로그램을 의미하며, 큰 의미로는 프로그램과 프로그램을 개발하기 위하여 작성한 관련 문서. 소프트웨어의 분류 1)시스템 소프트웨어(system software) 하드웨어와 밀접하게 연결되는 소프트웨어로서, 운영 체제(operating system), 컴파일러(compiler), 데이터 베이스(database) 등. 2)응용 소프트웨어(application software) 건축과 기계의 설계, 공정의 자동 제어 등을 위한 산업용 소프트웨어, 궤도 계산, 항공 역학, 지진 관측 등을 위한 과학용과 공학용 소프트웨어, 그리고 재고 관리, 인사 관리, 경영 관리 등을 위한 사무용 소프트웨어. 소프트웨어 공학(software engineering)은 소프트웨어를 효율적으로 개발하고 유지보수 하는 기술, 소프트웨어의 품질을 향상시키기 위한 기술과 소프트웨어를 개발하는 데 필요한 지원 기술 등을 포함한다.

1.2 소프트웨어 개발 프로세스 소프트웨어 개발 프로세스 분석, 설계, 구현, 시험, 유지보수의 과정을 순차적으로 접근하는 소프트웨어 개발 과정 <그림 1.1>은 고전적인 waterfall 개발 모델을 나타내며, 다음과 같은 단계를 거친다. <그림 1.1> 소프트웨어 개발 프로세스

1.2 소프트웨어 개발 프로세스(계속) 소프트웨어 요구 사항 분석 설계 코드생성(구현) 개발할 프로그램을 파악하기 위해서 소프트웨어 엔지니어는 반드시 요구 기능, 행위, 성능, 인터페이스 등은 물론이고 소프트웨어가 쓰이는 정보 도메인을 이해해야 한다. 시스템과 소프트웨어에 대한 요구 사항은 문서화되고 고객에 의해 검토된다. 설계 소프트웨어 설계는 프로그램의 자료구조, 소프트웨어 구조, 인터페이스, 표현 알고리즘 등의 네 가지 성질에 초점을 가진다. 설계 과정은 요구사항을 코딩이 가능한 상태로 소프트웨어를 표현하는 것이다. 설계는 요구사항과 마찬가지로 문서화되고 소프트웨어의 형상의 부분이 된다. 코드생성(구현) 설계의 결과는 기계가 이해할 수 있는 형태로 변환되어야 한다. 코드 생성 단계에서 이러한 작업을 수행한다. 만약 설계 작업이 보다 자세하게 진행된다면 코드 생성 단계는 자동적으로 수행될 수도 있다.

1.2 소프트웨어 개발 프로세스(계속) 시험 유지보수 코드가 생성되면, 프로그램 시험이 시작되며, 시험과정은 모든 문장을 시험하는 소프트웨어의 내부적 논리성에 초점을 두기도 하고, 기능 외적인 에러나 정해진 입력에 대해 올바른 작동을 하는가에 대해 초점을 두기도 한다. 유지보수 소프트웨어는 그 산출물이 고객에게 전달된 후에도 어쩔 수 없이 변화하는 경우가 생기거나, 외부환경의 변화(새로운 운영체계나 주변 기기의 추가)에 의한 에러가 발생하기도 한다. 또는 기능의 추가나 성능의 향상을 소비자가 요구하기 때문에 변화가 필요한 경우도 있다. 소프트웨어 지원과 유지는 프로그램을 새로운 것으로 바꾸는 것이 아니라 이전의 단계들을 재 적용시키는 것.

1.3 알고리즘(Algorithm) 알고리즘(Algorithm)이란? 특정한 일을 수행하는 명령어들의 유한집합이다. 모든 알고리즘은 다음과 같은 조건들을 만족해야 한다. ․ 입력 : 외부에서 제공되는 데이터가 0개 이상 있다. ․ 출력 : 적어도 한 가지의 결과를 생성한다. ․ 명확성 : 각 명령들은 명확하고 모호하지 않아야 한다. ․ 유한성 : 알고리즘의 명령대로 수행하면 어떤 경우에도 유한개의 단계 뒤에는 반드시 종료한다. ․ 유효성 : 원칙적으로 모든 명령들은 종이와 연필만으로 수행될 수 있어야 한다.

1.3 알고리즘(Algorithm) (1) 알고리즘 분석 알고리즘이 시작된 후 종료될 때까지의 시간이 사용자의 기대에 맞지 않게 너무 길어서는 안 된다. 알고리즘을 생각할 때 상식적으로 너무 복잡도가 큰 것은 생각하지 않으며, 될 수 있으면 능률적인 알고리즘을 생각한다. 예) 장기 또는 바둑과 같은 게임에 대한 알고리즘을 설계할 때, 시작 상태에서부터 가능한 모든 경우들을 열거하여 조사하는 방법으로 알고리즘을 꾸밀 수도 있다. 그러나 이렇게 가능한 모든 경우들을 고려하여 꾸민 알고리즘을 수행하려면, 현대의 가장 강력한 슈퍼컴퓨터로도 수십조 년 이상의 수행시간이 소요된다.

1.3 알고리즘(Algorithm) (2) 성능분석 알고리즘의 능률성을 평가하는 측정수단 1) 시간 복잡도(time complexity) : 알고리즘이 시작하여 답을 얻어 끝날 때까지의 시간 : 구체적인 하드웨어 기종이나 프로그래밍 언어 등을 고려하지 않은 알고리즘의 추상적인 수행시간. 2) 공간 복잡도(space complexity) : 알고리즘을 수행시키기 위해서는 기억장치를 얼마나 많이 사용하는지를 말한다. 알고리즘의 복잡도는 시간 복잡도를 의미. 시간 복잡도 알고리즘을 구성하는 명령어들의 수행 횟수에 각 명령어의 수행시간을 곱한 합계로 구한다. 이 방법은 하드웨어 종류 혹은 프로그래밍 언어 종류 등에 영향을 받는다. 알고리즘의 시간 복잡도를 측정할 때는 어느 특정한 하드웨어 기종, 혹은 프로그래밍 언어에 대한 고려는 무시. 알고리즘을 이루는 명령어들의 수행횟수를 계산하여 알고리즘의 시간 복잡도를 구하는 일을 성능 분석이라고 한다.

1.3 알고리즘(Algorithm) (3)알고리즘의 표현 방법 자연어 순서도 (flow chart) 한글이나 영어 사용 알고리즘 기술의 용이성 자연어의 모호성에 의하여 명확성 유지의 어려움 순서도 (flow chart) 좋은 알고리즘의 표현 방법임 규모가 큰 문제에 대해서 코딩의 어려움 의사코드 (pseudo code) 프로그래밍 언어에 가까우며 특정 언어의 구조에 제약을 받지 않음 실행을 위해서는 새로이 코딩하여야 함

1.3 알고리즘(Algorithm) (3) 알고리즘의 분석 기준 정확성 (Correctness) 수행량 (Amount of work done) 기억장소 사용량 (Amount of space used) 단순성/명확성 (Simplicity, Clarity) 최적성 (Optimality)

1.3 알고리즘(Algorithm) 정확성(correctness) 수행량(amount of work done) 올바른 입력에 대해서 유한 시간 내에 옳은 답을 내는 것을 의미함. 수행량(amount of work done) 알고리즘을 수행하는데 걸리는 수행 횟수를 나타내는데, 최선의 경우, 최악의 경우 및 평균의 경우로 나타낼 수 있음. 기억 장소 사용량(amount of space used) 알고리즘의 수행 시 필요한 컴퓨터의 기억 공간의 사용량을 의미함.

1.3 알고리즘(Algorithm) 단순성/명확성(simplicity/clarity) 최적성(optimality) 알고리즘의 작성이 쉽고 간결하여 해독성이 높아야 한다는 것을 말함. 최적성(optimality) “어떤 알고리즘이 최적이다” 라고 하는 것은 그 알고리즘보다 더 적은 중요 연산을 수행하는 알고리즘이 없다는 것을 의미함.

O(f) = {gcR+, n0N, nn0 , g(n)cf(n)} 1.3 알고리즘(Algorithm) (4) 증가율에 따른 함수의 구분 알고리즘의 수행량 비교를 위해 알고리즘의 차수 개념을 도입 알고리즘의 차수 비교 가정 f와 g를 자연수 집합 N에서 실수 집합 R로의 함수, 즉 f, g: N  R R+는 양의 실수 집합 O (big oh) f보다 차수가 작거나 같은 함수 전체의 집합 O(f) = {gcR+, n0N, nn0 , g(n)cf(n)}

1.3 알고리즘(Algorithm) 알고리즘의 차수 비교(계속)  (big theta) Ω (big omega) f와 같은 차수를 갖는 함수들의 집합 Ω (big omega) f보다 차수가 크거나 같은 함수 전체의 집합 (f) = {gg O(f), fO(g)} (f) = {gcR+, n0N, nn0 , g(n) cf(n)}

(f): 적어도 f보다 빠르게 증가하는 함수들 O(f): f보다 작은 비율로 증가하는 함수들 1.3 알고리즘(Algorithm) O, ,  의 관계 (f): 적어도 f보다 빠르게 증가하는 함수들 (f): f와 같은 비율로 증가하는 함수들 즉, (f) = (f)  O(f) f O(f): f보다 작은 비율로 증가하는 함수들

1.3 알고리즘(Algorithm) (5)차수의 중요성 같은 문제를 해결하는 두 알고리즘의 연산시간의 비교 O(n) O(n2) 450 300 30 312 1/2 250 25 200 20 112 1/2 150 15 50 100 10 12 1/2 5 1/2 1 n2/2 10n n

1.3 알고리즘(Algorithm) 자주 나타나는 수행량의 비교 f(n)=2n f(n)=n3 f(n)=n2 1 2 4 8 16 32 64 128 256 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 f(n)=2n f(n)=n3 f(n)=n2 f(n)=nlog2n f(n)=n f(n)=log2n n f(n)

연습문제 1. 알고리즘이란 무엇이며, 만족해야 하는 조건 5가지를 쓰시오. 2. 시간 복잡도에 대해 간단히 설명하시오. 3. 다음을 "big-oh" 표현으로 나타내시오.   a) 5n4 + 6n +3                b) 8   c) 7n3 + O(n)                    d) n log n + 2n2 + 7   e) 3n7 + O(2n) + n log n 4. 다음 알고리즘의 시간 복잡도를 구하시오.   for(i = 1; i <= n; i++)     for(j = 1; j <= n; j++){       sum = i + j;     }   }