CHAP 2:순환 2017. 3. 14 순천향대학교 컴퓨터공학과.

Slides:



Advertisements
Similar presentations
폭력. 폭력이란 무엇인가 우상의 눈물 물리적인 폭력 ( 최기표 ) VS 지능적인 폭력 ( 임형우, 담임선생님 )
Advertisements

1 박 2 일 !!! 인천마장초등학교 유수아. 1 박 2 일 멤버 인기순 위 1 위 이승기 2 위 엄태웅 3 위 은지원 4 위 김종민, 이수근 ※인터넷에서 본것이기 때문에 사람에따라 서 다를 수 있다. ※
광고론 제 2장: 광고의 경제적 효과 및 규제.
2. 세계 여러 지역의 자연과 문화 2) 육지가 넓고 인구가 많은 북반구.
석관중앙교회 5남전도회 석 관 중 앙 교 회 회원 소식 통권 05-04호 발행일 : 2005년 04월 회 장 : 장진호 집사
지역사회복지론 1조. 요양보호시설에 대해서 황성국 임재형 이동영
2-4.세계속의 우리 경제.
업무 프로세스 및 체크리스트
Recursion SANGJI University KO Kwangman
Activation Records & Recursion
슬라이드 1~21까지는 각자 복습! 슬라이드 22부터는 수업시간에 복습
Power C++ 제6장 포인터와 문자열.
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express.
C++ Espresso 제2장 제어문과 함수.
14주차 1교시 강화계획 [학습목표] 1. 강화계획의 정의를 안다 [학습내용] 1. 단순한 강화계획 2. 간헐적 강화 3. 복합 계획 4. 선택과 대응법칙 [사전학습] 강화계획이 일어날 수 있는 사례를 생각해본다.
연장근로와 야간·휴일근로 김영호 노무사 나눔 노사관계연구소 소장 연세대 일반대학원 박사 수료 고려사이버대 법학과 외래교수
I 문학의 개념과 역할 1. 문학의 개념 (1) 언어 예술로서의 문학 (2) 소통 활동으로서의 문학
총장후보자추천규정에 관한 검토 국립한밭대학교 교수평의회.
4. 목적론적 윤리와 의무론적 윤리 01. 경험주의와 이성주의 01. 경험주의와 이성주의 02. 결과론적 윤리와 공리주의
쉽게 풀어쓴 C언어 Express 제8장 함수 C Express.
쉽게 풀어쓴 C언어 Express 제8장 함수 C Express.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
변화 하는 세계 무역 환경 (p.144~147) 5303김민영.
2007 1학기 10 함수 활용.
쉽게 풀어쓴 C언어 Express 제9장 함수와 변수 C Express.
CHAP 2:순환 순천향대학교 컴퓨터공학과.
증명 수학적 귀납법 직접 증명법 간접 증명법 재귀법 프로그램 검증.
Internet Computing KUT Youn-Hee Han
Data structures 02.3:programming recursive functions
7장 배열 배열의 정의 배열의 초기화 1차원 배열 2차원 및 다차원 배열 문자 배열 배열과 구조.
CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
8장 함수 함수의 필요성 라이브러리 함수와 사용자 정의 함수 함수의 정의, 원형, 호출 배열을 함수 인자로 전달 재귀호출.
쉽게 풀어쓴 C언어 Express 제9장 함수와 변수 C Express.
9장. 동적 프로그래밍Dynamic Programming (DP)
배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.
개항기 조선과 동아시아 박 범 한국역사입문Ⅱ.
제 6장 함수 Hello!! C 언어 강성호 김학배 최우영.
CHAP 2:순환.
다음 주 과제 3장 읽어오기 숙제 해서 제출하기. 자료구조와 알고리즘, 순환 E304호,
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
함수와 변수 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
Power Point 2007년 정보화교육 원미구청 총무과 통신전산팀.
CHAP 2:순환.
CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 Slide 1 (of 19).
제 1 강.
프로그래밍 기초와 실습 Chapter 11 Recursion.
Hanoi Tower.
대구의 부도심 대구의 주요축 동대구 부도심 4조 강민석 / 박성균 / 최은지/ 황재현/김예지.
2 배열과 구조.
CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
기업회생 절차.
2. 윤리학의 원리와 적용 가. 상대주의와 절대주의.
CHAP 2:순환 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 12 : 탐색.
CHAP 1:자료구조와 알고리즘.
강의 프레젠테이션 현대 사회와 미디어 12강. 미디어 문화.
기술 진화와 진보.
사도행전 13장 22절 말씀 –아멘 다 윗 을 왕 으 로 세 우 시 고 증 언 하 여 이 르 시 되 내 가 이 새 의 아 들
“생각을 바꾸면 수학도 재밌다!!” 중앙대학교 사범대학 부속 고등학교 이 금 수.
7주차: Functions and Arrays
CHAP 2:순환.
쉽게 풀어쓴 C언어 Express 제6장 조건문 C Express.
경찰행정과 세미나 결과를 공개해야한다. VS 비공개로 해야한다. 경찰의 근무성적평정 제도.
컴퓨터 프로그래밍 기초 - 11th : 파일 입출력 및 구조체 -
Report #4 (1) (due 4/4) 문제 #1 3개의 막대 A, B, C와 원판 n개를 전달받아 Hanoi 탑 문제를 해결하는데 필요한 원판의 이동 회수를 구하여 반환하는 hanoi_tower(n, A, B, C)를 작성하라. 여기서 원판 n은 막대 A에 쌓여 있고.
영상으로 읽는 한국사 02 삼국은 서로를 한 ‘민족’으로 생각했나? - 삼국통일의 의미-.
삶을 풍요롭게 만드는 의사소통.
강의 #3. 순환(Recursion).
Presentation transcript:

CHAP 2:순환 2017. 3. 14 순천향대학교 컴퓨터공학과

순환(recursion)이란? 순환은 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 문제나 자료구조가 순환적으로 정의되는 경우, 알고리즘을 순환적으로 표현하는 것이 적합 예제: 정수의 팩토리얼 정의 Factorial 알고리듬 재귀적 정의

순환 알고리즘의 구조 순환 알고리즘은 다음과 같은 부분들을 포함한다. 만약 순환 호출을 멈추는 부분이 없다면?. 순환 호출을 하는 부분 else return n * factorial(n-1); int factorial(int n) { 순환을 멈추는 부분 순환호출을 하는 부분 } if( n <= 1 ) return 1 만약 순환 호출을 멈추는 부분이 없다면?.

순환 vs. 반복 대부분의 순환은 반복 버전으로 표현할 수 있고, 모든 반복은 순환 버전으로 표현할 수 있다. 순환 반복 순환적인 문제에서는 매우 자연스러운 방법 비효율적 반복 수행속도가 빠르다. 순환적인 문제에 대해서는 프로그램 작성이 아주 어려울 수도 있다.

순환 vs. 반복 팩토리얼 함수를 정의하라. 팩토리얼 함수 fact(n)을 알고리즘으로 작성하라. n! = 1 if n = 0 n*(n-1)*(n-2)*….*1 if n>0 팩토리얼 함수 fact(n)을 알고리즘으로 작성하라. Factorial 순환 버전 Factorial 반복 버전

Quiz 다음 함수에 대해서 답하시오. int sub(int n) { if ( n < 0) return 0; return n + sub(n-3); }

예제: 거듭제곱  

예제: 거듭제곱  

예제: 거듭제곱 power(), power2()의 알고리즘 복잡도 비교 구분 Power1 Power2 알고리즘 시간복잡도

예제: 피보나치 수열 피보나치 수열 정의 0,1,1,2,3,5,8,13,21,… fib(n)의 알고리즘을 작성하라.

예제: 피보나치 수열 피보나치 순환 알고리즘은 어떻게 동작하는가? 이 알고리즘은 효율적인가? n= 6인 경우를 고려 fib(6) fib(4) fib(5) fib(2) fib(3) fib(3) fib(4) fib(1) fib(0) fib(1) fib(2) fib(1) fib(2) fib(2) fib(3)

예제: 피보나치 수열 fib(7)이 호출될 경우에, fib(4)는 몇 번이나 중복 계산되는가? fib()의 반복적 버전은?

예제: 피보나치 수열 알고리즘 반복 버전?

예제: Hanoi 탑 문제 기원 1883년 프랑스 수학자 Edouard Lucas에 의해서 소개 옛날에 인도의 Kashi Vihswanath에 있는 브라만교 대사원에 하노이 탑이 있었고, 이 탑에는 3개의 다이어몬드 기둥과 그 한 기둥에 순금 원판 64개가 쌓아 있었다고 한다. 신이 브라만 승려들에게 다음 원칙으로 원판을 옮기라고 하였고, 원판은 한번에 한 개씩만 옮긴다 작은 원판 위에 큰 원판을 올려놓을 수 없다 64개의 원판이 다른 원판에 모두 옮겨졌을 때, 세상의 종말이 온다고 하였고, 승려들은 아직까지도 옮기고 있다고 함 http://en.wikipedia.org/wiki/Tower_of_Hanoi 웹 사이트: http://vornlocher.de/tower.html 스마트폰 어플: Tower of Hanoi

예제: Hanoi 탑 문제 https://www.mathsisfun.com/games/towerofhanoi.html

예제: Hanoi 탑 문제 A B C 문제 가정 문제 각 원판의 크기는 다르다. 한번에 하나의 원판만 이동 가능 크기가 작은 원판 위에 큰 원판을 쌓는 것 불가 위의 조건을 충족하면서 막대 A상의 모든 원판을 막대 C로 이동하는 알고리듬을 작성하라. A B C 가정 문제

예제: Hanoi 탑 문제 원판의 개수가 3인 경우 A B C

예제: Hanoi 탑 문제 원판의 개수가 n인 경우 A B C n-1개의 원판 1개의 원판

예제: Hanoi 탑 문제 알고리즘 생각 A B C Goal: A 상의 원판 n개를 막대 B를 이용하여 C로 이동하라. hanoi_tower(n, A, B, C) 문제를 순환적으로 생각 A 상의 원판 n-1개를 B로 이동 (C를 이용) A의 하나 남은 원판을 A에서 C로 이동: move(A, C) B상의 원판 n-1개를 C로 이동 (A를 이용) A B C

예제: Hanoi 탑 문제 알고리즘 A B C A 상의 원판 n-1개를 B로 이동 (C를 이용) A의 하나 남은 원판을 C로 이동 B상의 원판 n-1개를 C로 이동 (A를 이용) A B C hanoi_tower(int n, char from, char tmp, char to) // from상의 n개 원판을 tmp를 이용하여 to로 이동 { }

예제: Hanoi 탑 문제