컴퓨터프로그래밍 개요 충북대학교 컴퓨터공학과 서 영 훈.

Presentation on theme: "컴퓨터프로그래밍 개요 충북대학교 컴퓨터공학과 서 영 훈."— Presentation transcript:

1 컴퓨터프로그래밍 개요 충북대학교 컴퓨터공학과 서 영 훈

2 프로그램의 기본 요건 주어진 문제가 요구하는 모든 사항을 만족하면서, 수행되어야 한다. 오류(error)가 없어야 한다.
이해하기 쉽도록 작성되어야 한다. 효율이 좋아야 한다. … 기초컴퓨터프로그래밍

3 프로그램의 개발 절차 요구 분석 (Requirement Analysis) 설 계 (Design) 코 딩 (Coding)
테스트 및 디버깅 (Test & Debugging) 기초컴퓨터프로그래밍

4 요구 분석 요구 사항을 정확하게 분석 기능 (Functional Requirements)
성능 (Performance Requirements) 시스템 (System Requirements) 사용자 (Person Requirements) 기타 요구 사항 기초컴퓨터프로그래밍

5 설 계 (1) 구조 설계 (Architectural Design) 상세 설계 (Detailed Design)
프로그램의 구조 설계 주어진 문제를 작고, 다루기 쉬운 모듈들로 세분화 각 모듈간의 인터페이스 정의 주요 개념 : 모듈화 프로그래밍, 하향식 설계, 추상화 등 상세 설계 (Detailed Design) 자료구조 및 알고리즘 설계 구현하는 언어에 영향을 받을 수 있으나, 구현과 동일하지는 않음 주요 고려 사항 : 효율, 신뢰도 기초컴퓨터프로그래밍

6 설 계 (2) 구조 설계 결과의 예 (Structure Chart) 전체 프로그램의 구조 각 모듈의 기능 설명
각 모듈의 인자(input data) 및 결과(output data) A B C D E 1 2 3 4 5 각 모듈의 기능 1 Input Data Output 2 In Out 4 5 3 A … B … C … D … E … 기초컴퓨터프로그래밍

7 코 딩 코딩 (Coding) 이해하기 쉽도록 작성 설계 결과를 바탕으로 프로그램 작성
구현(implementation)이라고도 함 이해하기 쉽도록 작성 구조화 프로그래밍(structured programming) 적용 프로그램 내부에 설명문(comments) 삽입 적절한 외부 설명 자료 (documents) 빈 줄 삽입, 인덴테이션 등의 적절한 사용 등 사용자 정의 식별자(상수, 변수, 함수 명칭 등)를 사용 의도가 반영된 명칭 사용 기초컴퓨터프로그래밍

8 테스트 및 디버깅 테스트 및 디버깅 테스트 디버깅 프로그램 오류 수정
모든 요구 사항을 만족하도록 프로그램 튜닝 (기능, 성능 등) 테스트 많은 데이터를 이용하여 오류 검사 요구 사항의 만족 여부 검사 Test shows the presence, not the absence, of bugs. – E. W. Dijkstra 디버깅 테스트에 의해 발견된 오류 수정 기초컴퓨터프로그래밍

9 Software Lifecycle 단계 세부 단계 Typical Effort (Cost) Software 개발 요구분석 40
설계 코딩 20 테스트와 디버깅 Software 유지 보수 Enhancement 60 Correction Adaptation 기초컴퓨터프로그래밍

10 알고리즘 설계 (1) 알고리즘 설계 방법 프로그램 예제1 [소수구하기] 예제1에 대한 지식을 정리
문제에 대한 지식을 정리 (알고 있는 지식 또는 참고 문헌) 컴퓨터에 의해 수행될 수 있도록 구체적인 절차를 기술 추상적인 절차로부터 점점 구체화 (stepwise refinement) 프로그램 예제1 [소수구하기] N을 입력으로 하여, 2부터 N까지의 모든 소수(prime number)를 구하는 프로그램을 작성하라. 예제1에 대한 지식을 정리 소수(prime number)는 1과 자기 자신으로만 나누어지는 수이다. 어떤 수 n이 m으로 나누어진다는 것은 n을 m으로 나누었을 때 나머지가 없다(0)는 것이다. 기초컴퓨터프로그래밍

11 알고리즘 설계 (2) 수행 절차 구상 (전체적인 흐름부터 추상적으로) 위 절차를 pseudo code로 기술 N을 입력한다.
2가 소수인지 아닌지 확인하고, 소수이면 출력 3이 소수인지 아닌지 확인하고, 소수이면 출력 … N이 소수인지 아닌지 확인하고, 소수이면 출력 위 절차를 pseudo code로 기술 read(N) for i := 2 to N do i가 소수인지 아닌지 확인하고, i가 소수이면 출력 endfor PC-1 기초컴퓨터프로그래밍

12 알고리즘 설계 (3) [Refinement 1] : i가 소수인지 아닌지 확인하는 방법 PC-1과 PC-2의 결합
i를 1부터 i까지의 정수들로 나누면서, 나누어진 회수를 센다. 만일 1과 자기자신(i)로만, 즉 2번만 나누어졌으면 소수이다. PC-1과 PC-2의 결합 read(N) for i := 2 to N do i가 소수이면 출력 endfor PC-2 PC-3 기초컴퓨터프로그래밍

13 알고리즘 설계 (4) [Refinement 2] : i를 1부터 i까지로 나누어 본다.
for j := 1 to i do i가 j로 나누어지는지 확인한다. endfor [Refinement 3] : i가 j로 나누어지는지 확인한다. if (i mod j = 0) … // if (i % j == 0) … [Refinement 4] : i가 j로 나누어지는 회수를 센다. count := 0 if (i mod j = 0) count := count + 1 기초컴퓨터프로그래밍

14 알고리즘 설계 (5) Refinement-4의 내용을 PC-3에 반영 (전체 알고리즘) read(N)
for i := 2 to N do count := 0 for j := 1 to i do if (i mod j = 0) count := count + 1 endfor if (count = 2) print(i) Algorithm-1 기초컴퓨터프로그래밍

15 코딩 (1) 알고리즘(Algorithm-1)을 C 언어의 구문에 맞게 코딩 Algorithm-1 C 프로그램 read(N);
for i := 2 to N do count := 0 for j := 1 to i do if (i mod j = 0) count := count + 1 endfor if (count = 2) print(i) #include <stdio.h> int main() { int i, j, count, num; scanf(“%d”, &num); for(i=2; i<=num; i++) { count = 0; for(j=1; j<=i; j++) if (i%j==0) count++; if (count==2) printf(“%d ”, i); } return 0; 기초컴퓨터프로그래밍

16 코딩 (2) 알고리즘(Algorithm-1)을 Pascal 언어의 구문에 맞게 코딩 Algorithm-1 Pascal 프로그램
read(N); for i := 2 to N do count := 0 for j := 1 to i do if (i mod j = 0) count := count + 1 endfor if (count = 2) print(i) program primeNumber(input, output); var i, j, count, num: integer; begin read(num); for i := 2 to num do begin count := 0; for j :=1 to i do if (i mod j = 0) then count := count + 1; if (count=2) then write(i, ‘ ’); end end. 기초컴퓨터프로그래밍

17 알고리즘 분석 Algorithm-1의 분석 각 문장 실행 회수 read(N) // 1회 for i := 2 to N do
count := // (N-1)회 for j := 1 to i do if (i mod j = 0) count := count // (2+3+4+…+N)회 endfor if (count = 2) print(i) // (N-1)회 가장 실행 회수가 많은 연산 : mod 연산 mod 연산의 실행 회수 : N*(N+1)/2 – 1 따라서, 효율을 개선하려면 mod 연산의 실행 회수를 줄여야 함 기초컴퓨터프로그래밍

18 알고리즘 개선 (1) 소수구하기 알고리즘 개선-1 (Algorithm-2-1) Algorithm-2-1의 장점
i가 소수인지 알기 위해 1부터 i까지의 모든 정수로 나누어 볼 필요 없음. 즉, 2부터 i-1까지의 정수로 나누어서 한번도 나누어지지 않으면 소수임 Algorithm-2-1의 장점 매번 안쪽 반복문에서 반복회수가 2회 줄어듬 바깥 반복문이 2~N까지 (N-1)회 반복되므로, 전체적으로 2*(N-1)회 반복 계산 회수가 줄어듬 따라서 실행 시간 단축 효과 기초컴퓨터프로그래밍

19 알고리즘 개선 (2) Algorithm-2-1 read(N)
if (N >= 2) print(2) // 2는 2로 나누어지므로 별도 출력 for i := 3 to N do count := 0 for j := 2 to i-1 do if (i mod j = 0) count := count + 1 endfor if (count = 0) print(i) 기초컴퓨터프로그래밍

20 알고리즘 개선 (3) Algorithm-2-1의 추가 개선 (Algorithm-2)
read(N) if (N >= 2) print(2) for i := 3 to N do flag := true j := 2 while ((flag = true) and (j < i)) do if (i mod j = 0) flag := false j := j + 1 endwhile if (flag = true) print(i) endfor Algorithm-2 기초컴퓨터프로그래밍

21 알고리즘 개선 (4) 소수 구하기 알고리즘 개선-2 (Algorithm-3)
2를 제외한 모든 짝수는 소수가 아니므로 대상에서 제외시킴 (약 2배의 효율 향상) 또한 홀수는 짝수로 나눠지지 않기 때문에, 나뉘어지는 수도 짝수 제외 (약 2배 효율 향상) 소수 구하기 알고리즘 개선-3 (Algorithm-4) 어떤 수 i가 소수인지 확인하기 위해 2부터 (i-1)까지의 정수로 나누어 볼 필요 없음 2부터 sqrt(i)까지로만 나누어 보면 됨 (e.g.) 48의 약수 (e.g.) 64의 약수 1 2 3 4 6 8 12 16 24 48 1 2 4 8 16 32 64 기초컴퓨터프로그래밍

22 알고리즘 개선 (5) 소수구하기 알고리즘 요약 알고리즘 바깥 반복의 대상 안쪽 반복의 대상 및 반복 조건 Algorithm-1
2부터 N까지의 모든 수 1부터 i까지의 모든 수 무조건 반복 Algorithm-2 2부터 i-1까지의 모든 수 한번이라도 나눠지면 반복 중단 Algorithm-3 모든 홀수 2부터 i-1까지의 모든 홀수 Algorithm-4 2부터 sqrt(i)까지의 모든 홀수 Algorithm-5 2부터 sqrt(i)까지의 모든 소수 기초컴퓨터프로그래밍

23 알고리즘 개선 (6) 알고리즘의 성능 비교 알고리즘 N=100 나머지(mod) 연산 수행 회수 N=1,000 N=10,000
5,049 500,499 50,004,999 Algorithm-1 (A1) 1,133 78,022 5,775,223 Algorithm-2 (A2) 530 38,678 2,884,498 Algorithm-3 (A3) 87 2,351 55,958 Algorithm-4 (A4) 84 1,804 33,756 Algorithm-5 (A5) 60.1 277.4 1,481.4 A1 / A5 기초컴퓨터프로그래밍

24 최대 공약수 구하기 (1) 프로그램 예제2 : 최대 공약수 구하기 문제 해결 방법 구상 (아는 지식 정리) GCD1 알고리즘
두 자연수 a, b (a >= b)의 최대 공약수를 구하라. 문제 해결 방법 구상 (아는 지식 정리) 최대 공약수는 두 수 a, b의 약수 중에서 제일 큰 수 (GCD1) 어떤 수 n의 약수는 그 수를 1부터 n까지로 나누었을 때, 나머지가 없는 수이다. 최대 공약수는 두 수를 소인수 분해하여 찾을 수 있다. 두 수가 공통적으로 나누어지는 소인수들을 전부 곱하면 최대 공약수이다. GCD1 알고리즘 a의 약수를 구한다. b의 약수를 구한다. a, b의 약수에 공통으로 들어있는 가장 큰 수를 구한다. 기초컴퓨터프로그래밍

25 최대 공약수 구하기 (2) a, b의 약수를 구하여 배열 ad[], bd[]에 저장하는 알고리즘
idx1 := 1; idx2 := 1; for i := 1 to a do for i := 1 to b do if (a mod i = 0) then if (b mod i = 0) then ad[idx1] := i; bd[idx2] := i; idx1 := idx1 + 1; idx2 := idx2 + 1; endif endif endfor endfor 두 약수 배열에 공통으로 들어 있는 가장 큰 수를 찾는 방법 큰 수부터 비교 (예: 36과 16의 최대 공약수) 1 2 3 4 6 9 12 18 36 // 36의 약수 // 16의 약수 1 2 4 8 16 기초컴퓨터프로그래밍

26 최대 공약수 구하기 (3) 약수 배열에서 공통의 가장 큰 수를 찾는 알고리즘
i := idx1 – // i를 ad 배열의 최대 첨자 값으로 초기화 j := idx2 – // j를 bd 배열의 최대 첨자 값으로 초기화 flag := false // flag는 수를 찾았을 때 true 값을 가지는 변수 while ((flag = flase) and (i >= 1) and (j >= 1)) do if (ad[i] > bd[j]) then i := i – 1 else if (ad[i] < bd[j]) then j := j – 1 else flag = true endwhile return (ad[i]) 기초컴퓨터프로그래밍

27 최대 공약수 구하기 (4) GCD1의 효율 개선 방법 소인수 분해를 이용하는 알고리즘 (GCD2)
두 수중 작은 수보다 큰 약수는 구할 필요 없음 약수를 구하기 위해 제곱근까지의 수로만 나누고, 나누어지는 수의 몫과 제수를 약수로 취함 기타 소수(prime number)를 구할 때 적용한 방법 등 이용 소인수 분해를 이용하는 알고리즘 (GCD2) 두 수중 작은 수의 약수를 구하고 그중 소수를 배열에 저장 : pn[] gcd := 1 for i := 1 to maximum_index_of_pn while ((a mod pn[i]) = 0) and (b mod pn[i] = 0) do gcd = gcd*pn[i]; a = a/pn[i]; b = b/pn[i]; endwhile endfor 기초컴퓨터프로그래밍

28 최대 공약수 구하기 (5) Euclid Algorithm : GCD3 Euclid Algorithm 적용 예
최대공약수를 구하는 효율적인 방법 a if b = 0 GCD(a, b) = GCD(b, a mod b) otherwise function GCD3(a, b) if (b = 0) then a else GCD3(b, a mod b) end Euclid Algorithm 적용 예 72와 20의 최대공약수 GCD3(72, 20) = GCD3(20, 12) = GCD3(12, 8) = GCD3(8, 4) = GCD3(4, 0) = 4 int gcd3(int a, int b) { if (b==0) return(a); else return(gcd3(b, a%b)); } 기초컴퓨터프로그래밍

29 최대 공약수 구하기 (6) 알고리즘 비교 72와 20을 입력으로 했을 경우의 mod 연산 및 기타 연산 알고리즘 GCD1
(약수 구하여 비교) GCD2 (소인수 분해 이용) GCD3 (Euclid Algorithm) mod 연산 회수 기타 연산 92 12 (비교 연산) 22 없음 4 기초컴퓨터프로그래밍

30 Searching (1) 탐색 (searching) Blind Search 임의의 자료 집합에서 어떤 자료를 찾는 문제
Some examples 영어사전 또는 국어사전에서 어떤 단어를 찾는 문제 어떤 숫자 집합에서 원하는 숫자가 있는지 조사하는 문제 대학교에서 어떤 학생에 대한 정보를 찾는 문제 인터넷에서의 정보 검색 Blind Search 첫번째 자료부터 순차적으로 하나씩 비교 만일 N을 전체 자료의 수라고 할 때, 최악의 경우 N번 비교 평균 탐색 시간 : N/2 for i = 1 to N if X = L[i] then return(i) endfor return (0) 기초컴퓨터프로그래밍

31 Searching (2) 이진 탐색 (Binary Search) 자료가 정렬(sorting)되어 있을 때 사용 가능한 방법
탐색 대상 자료 집합의 중간 값과 비교 찾고자 하는 자료가 중간 값보다 크면, 중간 값보다 큰 부분의 자료에서만 탐색하고, 반대의 경우이면 작은 부분의 자료에서만 탐색 즉, 한번 비교할 때마다 탐색 대상 자료의 수가 ½로 줄어듬 i = 1; j = N; while (i <= j) do k = (i+j)/ // 단, 는 소수점 이하 절사(truncation) 기호 if X = L[k] then return(k) else if X < L[k] then j = k – 1 else i = k + 1 endwhile return (0) 기초컴퓨터프로그래밍

32 Searching (3) 이진 탐색의 복잡도(Complexity) : O(log2N) 1 when N = 1 W(N) =
1 + W( N/2 ) when N > 1 W(N) = 1 + W( N/2 ) = W( N/4 ) = 2 + W( N/22 ) = k + W( N/2k ) = k when 1  N/2k < 2  log2N + 1 1  N/2k < 2 2k  N < 2k+1 // 2k를 각 항에 곱함 k  log2N < k+1 // 각 항에 log2를 적용 즉, log2N – 1 < k  log2N 기초컴퓨터프로그래밍