2. 거듭 제곱 값 계산 반복적인 거듭제곱 계산 프로그램 int slow_power(double x, int n){ double r = 1.0; for(int i=0;i O(n) 순환적인 거듭제곱 계산 power(x,n) if n=0 return 1; else if n이 짝수 then return power(x^2,n/2); else if n이 홀수 then return x * power(x^2,(n-1)/2); (1) n이 짝수인 경우 power(x,n) = power(x^2, n/2) = (x^2)^(n/2) = x^2^(n/2) = x^n (2) n이 홀수인 경우 power(x,n) = x * power(x^2,(n-1)/2) = x*(x^2)^((n-1)/2) = x * x^(n-1) = x^n ..

Reference: C언어로 쉽게 풀어쓴 자료구조 / 생능출판사 / 천인국 1. 순환의 소개 - 순환(recusrion) : 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 순환의 예 순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다 순환적인 팩토리얼 계산 프로그램 int factorial(int n) { if (n 복귀 주소가 시스템 스택 (stack) 에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record) 라 한다 *호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 점프하게 되는 것이다 main()에서..

Reference : 건국대학교 컴퓨터공학과 자료구조 수업 / 김성열 교수님 합병 정렬의 개념 : 하나의 리스트를 2 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다. ==> 합병 정렬은 분할 정복 (divide and conquer) 기법에 바탕을 두고 있다 분할 정복 (divide and conquer) 기법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 ==> 분리된 문제가 아직도 해결하기 어렵다면 (충분히 작지 않다면) 분할 정복 방법을 연속하여 다시 적용 ==> 분할 정복 기법은 대개 순환 호출을 이용하여 구현 분할(Divide) : 입력 배열..

Reference : 건국대학교 컴퓨터공학과 자료구조 수업 / 김성열 교수님 C언어로 쉽게 풀어쓴 자료구조 / 천인국 / 생능출판사 선택 정렬의 원리 선택 정렬은 가장 이해하기 쉬운 정렬 방법이다 숫자들은 1차원 배열에 들어 있다고 가정 왼쪽 리스트 : 정렬이 완료된 숫자들 오른쪽 리스트 : 정렬되지 않은 숫자들 선택 정렬 : 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이 해서 오른쪽 리스트가 공백 상태가 될 때까지 이 과정을 되풀이하는 정렬 기법 위의 방법은 배열로 구현하기로 하였다면, 위의 방법을 구현하기 위해서는 입력 배열과는 별도로 똑같은 크기의 배열이 하나 더 필요하다. ==> 따라서 메모리를 절약하기 위하여 입력 배열 외에 추가적인 공간을 사용하지 않는 선택..