오일석, C와 ALPS, 2008. 2 장. 문제 해결 © 오일석, 전북대학교 컴퓨터공학.

Presentation on theme: "오일석, C와 ALPS, 2008. 2 장. 문제 해결 © 오일석, 전북대학교 컴퓨터공학."— Presentation transcript:

1 오일석, C와 ALPS, 2008. 2 장. 문제 해결 © 오일석, 전북대학교 컴퓨터공학

2 2장 문제 해결 차례 © 오일석, 전북대학교 컴퓨터공학

3 2장 문제 해결 프로그래밍 도전 이면의 철저한 준비와 체계적인 노력 필요 매우 도전적인 작업
자신의 아이디어와 스타일을 구사할 공간이 무척 넓은 매력적인 분야 도전 이면의 철저한 준비와 체계적인 노력 필요 “정리되지 않은 생각을 가지고 키보드를 두드리는” 초보 물 붓고 라면 넣은 다음 끓이는 행위에 비유할 수 있다. 문제의 이해  알고리즘 설계  C 코딩 수순의 중요성 © 오일석, 전북대학교 컴퓨터공학

4 2.1 문제 해결 과정 지능적인 컴퓨터, 미래에 탄생할 수 있을까? © 오일석, 전북대학교 컴퓨터공학

5 2.1 문제 해결 과정 아래 과정에 충실하자. 전문가의조언 © 오일석, 전북대학교 컴퓨터공학

6 2.2 예제 문제 1: 마방진 마방진magic square 고대 중국과 유럽에서 유래 2019-08-05
© 오일석, 전북대학교 컴퓨터공학

7 2.2 예제 문제 1: 마방진 어떻게 풀까? 손이 먼저 작동 연필들고 이것 저것 해본다. 머리가 먼저 작동
규칙을 찾기 위해 생각에 빠진다. 5*5 마방진 문제 ? © 오일석, 전북대학교 컴퓨터공학

8 2.2.1 우직한 생각 모든 가능성을 나열하고 다 해 본다. 컴퓨터가 빠르니 생각해 봄직 낱낱 알고리즘
n2!개의 후보 해 (n=3이면 9!=362880) © 오일석, 전북대학교 컴퓨터공학

9 2.2.1 우직한 생각 알고리즘으로 기술 거친 버전 라인 3의 ‘새로운 순열을 생성하고’는 기본 연산이 아님
© 오일석, 전북대학교 컴퓨터공학

10 2.2.1 우직한 생각 알고리즘 [2.1]의 효율 논리는 맞는데 현실성이 없다.
크기가 n*n의 마방진을 푸는데 n2!개의 후보 해를 검사 n=5이면 25! 후보 해 하나를 검사하는데 1마이크로 초가 걸린다면 2*1011년 필요 논리는 맞는데 현실성이 없다. © 오일석, 전북대학교 컴퓨터공학

11 2.2.2 Coxeter의 생각 매우 재미있고 단순한 규칙 © 오일석, 전북대학교 컴퓨터공학

12 2.2.2 Coxeter의 생각 Coxeter 알고리즘 (거친 버전) © 오일석, 전북대학교 컴퓨터공학

13 2.2.2 Coxeter의 생각 Coxeter 알고리즘 (상세 버전) 손 시뮬레이션 2019-08-05
© 오일석, 전북대학교 컴퓨터공학

14 2.3 예제 문제 2: 최대 공약수 최대 공약수greatest common divisor
두 정수가 공통으로 갖는 약수 중에 가장 큰 것 © 오일석, 전북대학교 컴퓨터공학

15 2.3.1 우직한 생각 중학교에서 배운 규칙 © 오일석, 전북대학교 컴퓨터공학

16 2.3.1 우직한 생각 또 다른 규칙 © 오일석, 전북대학교 컴퓨터공학

17 2.3.1 우직한 생각 규칙 2에 의한 알고리즘 알고리즘 [2.5]에 의한 C 코딩 2019-08-05
© 오일석, 전북대학교 컴퓨터공학

18 실습 © 오일석, 전북대학교 컴퓨터공학

19 2.3.2 유클리드의 생각 놀랍게도 쉬운 유클리드의 규칙 놀랍게도 기원전 300년 경에 발견됨
규칙 2와 루프 회수를 비교하면? © 오일석, 전북대학교 컴퓨터공학

20 2.3.2 유클리드의 생각 유클리드 호제법 © 오일석, 전북대학교 컴퓨터공학

21 2.4 언어 둘 다 중요하다. 둘 다 잘하자. 논리적인 생각을 통한 규칙 도출 생각의 결과를 ‘언어’를 이용하여 표현
© 오일석, 전북대학교 컴퓨터공학

22 2.4.1 기본 명령어, 의사 코드, 그리고 C 코드 C의 기본 명령어 집합은 의외로 단순하다. 2019-08-05
© 오일석, 전북대학교 컴퓨터공학

23 2.4.1 기본 명령어, 의사 코드, 그리고 C 코드 © 오일석, 전북대학교 컴퓨터공학

24 2.4.2 정렬 정렬 문제로 의사 코드, C 코드 작성을 연습 해 보자. © 오일석, 전북대학교 컴퓨터공학

25 2.4.2 정렬 상식에서 구한 정렬 규칙 © 오일석, 전북대학교 컴퓨터공학

26 2.4.2 정렬 알고리즘으로 쓰면 (스케치 (거친) 버전) © 오일석, 전북대학교 컴퓨터공학

27 2.4.2 정렬 상세 버전의 알고리즘으로 쓰면 처리한 요소는 INT_MAX로 표시 중첩 루프 2019-08-05
© 오일석, 전북대학교 컴퓨터공학

28 2.4.2 정렬 C 코딩하면 배열 크기는 미리 지정해야 함 © 오일석, 전북대학교 컴퓨터공학

29 2.4.2 정렬 코드 이해력 비교 © 오일석, 전북대학교 컴퓨터공학

30 실습 © 오일석, 전북대학교 컴퓨터공학

31 2.4.3 배열 C에서 배열의 첨자는 0~(n-1) 배열 사용 예 © 오일석, 전북대학교 컴퓨터공학

32 실습 © 오일석, 전북대학교 컴퓨터공학

33 2.4.2 for 문 반복을 위한 또 다른 문 for for와 while은 서로 바꾸어 쓸 수 있다. 어느 것이 더 좋을까?
© 오일석, 전북대학교 컴퓨터공학

34 2.4.2 for 문 프로그램 [2.3]을 for로 다시 쓰면 © 오일석, 전북대학교 컴퓨터공학

35 실습 © 오일석, 전북대학교 컴퓨터공학