오일석, C와 ALPS, 2008. 3 장. 논리적으로 생각하기 © 오일석, 전북대학교 컴퓨터공학

3장 논리적으로 생각하기 차례 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3장 논리적으로 생각하기 일상과 공부에서의 논리의 중요성 프로그래밍은 철저한 논리적 작업 해외 배낭 여행 준비에서도 논리적인 사고를 한다. 논리적 사고가 부족하면 모든 과목에서 애를 먹는다. 프로그래밍은 철저한 논리적 작업 알고리즘 구상 알고리즘 표현 (의사 코드와 C 코드) 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.1 강 건너기 강 건너기 문제 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.1 강 건너기 강 건너기 문제 모든 물건이 A에 있는 상태를 어떻게 모든 것이 B에 있는 상태로 변환할 것인가라는 문제 단위 작업 프로그래밍에서는 연산이라 부름 연산은 상태를 변화시킴 상태 S개S닭S쌀S배 (물건 i가 A에 있으면 Si=A, 그렇지 않으면 Si=B) 이제 문제를 상태 AAAA를 어떻게 BBBB로 바꿀 것인가로 볼 수 있음 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.1 강 건너기 강 건너기 문제의 해 찾기 초기 상태 AAAA에서 적용 가능한 연산은? ②만 가능 ②를 적용하면 ABAB 가 됨 ABAB에서 적용 가능한 연산은? 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.2 하노이 탑 하노이 탑 문제 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.2 하노이 탑 연산 원반이 세개 뿐인 문제 Hanoi(3,A,B,C)부터 생각해 보자. 여섯 가지 AB, AC, BA, BC, CA, CB 원반이 세개 뿐인 문제 Hanoi(3,A,B,C)부터 생각해 보자. A B C A B C A B C A B C A B C A B C A B C A B C 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.2 하노이 탑 원반이 네 개인 문제 Hanoi(4,A,B,C) 세 개짜리 문제 두 번과 원 반 이동 한 번으로 해결 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.2 하노이 탑 이러한 순환 원리를 일반화시키면, 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.2 하노이 탑 예제 3.1 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.2 하노이 탑 알고리즘 C 코딩은 순환 함수 배우는 곳에서 다시 살피자. 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.2 하노이 탑 원반 개수 n에 따른 원반 이동 회수 f(n) f(3)=7 f(4)=2*f(3)+1=15 …. 일반화 하면 f(n)=2f(n-1)+1=2n-1 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.3 배열 분할 배열 분할 문제 (quick sort의 핵심 연산) 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.3 배열 분할 어떻게 해결할 것인가? 왼쪽 끝에서 출발하여 오른쪽으로 진행하면, 기준보다 작은 것은 지나치고 큰 것을 만나면 거기서 멈춘다. 오른쪽 끝에서 출발하여 왼쪽으로 진행하면, 기준보다 큰 것은 지나치고 작은 것을 만나면 거기서 멈춘다. 두 개를 교환한다. 이런 과정을 왼쪽과 오른쪽이 교차할 때까지 반복한다. 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.3 배열 분할 스케치 코드 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.3 배열 분할 상세 코드 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.3 배열 분할 C 프로그램 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

실습 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.4.1 직사각형 그리기 직사각형 그리기 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.4.1 직사각형 그리기 C 코드 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.4.1 직사각형 그리기 경계 조건 예외 조건 변수가 가지는 값의 범위에서 경계 부근의 값을 가지는 경우 직사각형 예에서는 height=0, 1, 또는 2 가 경계 조건에 해당 경계 조건에서의 동작 height=0 또는 1일 때 오류 예외 조건 width 또는 height 가 음수 또는 스크린 보다 큰 값일 때 프로그램 [3.2]는 오동작 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.4.1 직사각형 그리기 경계 조건과 예외 조건을 제대로 처리하는 프로그램 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

실습 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.4.2 다이아몬드 그리기 다이아몬드 그리기 규칙을 만들어 보자. 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.4.2 다이아몬드 그리기 다이아몬드 그리기 규칙 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.4.2 다이아몬드 그리기 가상 코드 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

3.4.2 다이아몬드 그리기 C 코드 2018-11-28 © 오일석, 전북대학교 컴퓨터공학

실습 2018-11-28 © 오일석, 전북대학교 컴퓨터공학