# 피보나치 수열 문제 Fibonacci 수열은 다음과 같이 정의된다.$f_0 = 0, f_1 = 1 그리고 f_i = f_{i - 1} + f_{i - 2}(i > 1 일 때)$ $f_i$를 계산하는 C함수로 순환 함수와 반복 함수를 모두 작성하라. # 구현 // 반복버전에서 반복계수가 2부터 시작해서 n까지 간다는 것만 주의하면 된다. 반복계수가 2인 까닭은 2개의 초기값을 설정해줬기 때문에 0과 1을 지나쳐 2부터 시작되는 것이다. /************************************************* **Fibonacci iterative & recursive ver *************************************************/ #include in..
# 팩토리얼 문제 문제) 팩토리얼 (=계승) 함수 n!은 $n\le1$일 때 n * (n - 1)! 의 값을 가진다. n!을 계산하는 C프로그램을 순환과 반복버전으로 구현하라. # 구현 // 순환함수는 다들 쉽게 작성하시리라 믿고, 반복버전 코드를 배워가시면 좋을 것 같습니다. /************************************************* ** Factorial recursive ver & iterative ver *************************************************/ #include int recur_fac(int n); int iter_fac(int n); void main() { int n; int output1, output2; wh..
# 비둘기집 원칙 문제 문제) 비둘기집 원칙이란 함수 f가 n개의 상이한 입력에 대해 n개보다 작은 상이한 출력이 나온다면 $a\neq$ $b$ 이고 $f(a) = f(b)$인 두 개의 입력 a, b가 존재한다는 것이다. 이와 같이 입력값이 상이하면서 함수값이 같은 a,b를 찾는 C프로그램을 작성하라. # 풀이 이 문제는 한 가지 함수를 미리 정해두고 프로그램을 작성한다. 그 후 함수 내에 같은 y값이 나오는 x값들이 있는지 확인하는 프로그램을 작성하면 된다. /************************************************* ** 비둘기집 원칙 프로그램 *************************************************/ #include #include //..
# Horner의 법칙 문제 //horner의 법칙 관련 개념 설명은 맨 밑에 있습니다. 문제) Horner의 법칙은 주어진 점 $x0$ 에서 최소의 곱으로 다항식 $A(x) = a_nx^n+a_{n-1}x^{n-1}+\ldots+a^1x+a_0$ 를 계산하는 것으로 이 법칙은$A(x_0) = ( ... ((a_nx_0 + a_{n-1})x_0 + ... + a_1)x_0 + a_0)$ 이다. Horner의 법칙을 사용하여 다항식을 계산하는 C프로그램을 작성하라. # 풀이 Horner의 법칙 문제를 풀 때는 직접 손으로 먼저 계산하며 그 과정을 이해해야 한다. 곱셈으로 도출된 값이 다음 덧셈에 이용되고 또 그렇게 도출된 나머지가 곱셈되어 다음 덧셈에 이용되는 그 과정을 이해해야 한다. /*********..
퀴즈에 등장하는 개념 요약 // 해당 도서를 읽지 않으시는 분들도 생각하고 풀어보실 수 있습니다.# 전진 이동법 전진 이동법(Move to front method)은 어느 항목이 한 번 탐색되고 나면, 그 항목을 데이터 집합의 가장 앞(링크드 리스트에서는 헤드)에 위치시키는 방법이다. 이렇게 하면 한 번 찾은 항목을 연이어 또 찾는 경우 단번에 탐색을 완료할 수 있다. MS 워드의 '최근 문서'기능과 같은 원리로 동작한다고 생각하면 이해가 쉽다. 전진이동법의 한계는 한 번 탐색된 항목이 곧 이어 또다시 검색될 가능성이 높은 데이터 집합에서만 사용해야한다 점이다. # 전위법 전위법(Transpose method)은 탐색된 항목을 바로 이전 항목과 교환한다는 것 말고는 기본적으로 전진 이동법과 같은 전략을 ..
이것만은 알고 갑시다. 문제) 더블 링크드 리스트는 탐색이 느린 대신, 데이터 요소의 삽입 / 삭제가 빠른 자료구조다. 배열을 위해 구현되었던 Insertion_Sort( )함수가 더블 링크드 리스트를 정렬할 수 있게 구현하라. 풀이 한 가지 확실한 건 이 문제는 머릿 속으로만 해결할 수 없는 문제다. 반드시 일어날 수 있는 상황을 상정하고 직접 손으로 그림을 그려가며 풀어야 한다. 논리가 그렇게 간단하지 않다. 아래 적혀 있는 풀이 소스는 가독성을 위해 이중연결리스트(더블링크드리스트) 구조체와 삽입정렬 알고리즘만이 적혀 있다. 이미 완성되어 있는 이중연결리스트의 첫 번째 노드의 주소, 즉 헤드가 매개변수로 전달되었다 생각하고 밑의 코드를 살펴보도록 하자. 전체 소스는 최하단에 첨부해 두었으니 잘 작동하..
# 삽입 정렬 삽입 정렬(Insertion Sort)은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다. 마치 뒤섞여 있는 트럼프 카드를 순서대로 정리하는 모습과 같다. 카드를 한 장씩 뽑아 카드의 값에 따라 적절한 곳에 끼워 넣는 것을 반복하다 보면 결국 모든 카드가 순서대로 정리된다. 마찬가지로 데이터 집합에서 요소를 하나씩 뽑아 적절한 곳에 끼워 넣는 것을 반복하다 보면 정렬된 데이터 집합을 얻을 수 있다. 삽입 정렬은 구현이 간단해서 버블 정렬과 함께 프로그래머들에게 애용되는 알고리즘 중 하나다. 성능 또한 버블 정렬과 비슷하다. 이 알고리즘은 아래의 과정을 통해 정렬을 수행한다. 오름차순으로 정렬할 때를 가정한다. 데이터 집합에서 정렬 대상이..
Vitamin Quiz 문제) 버블 정렬은 이미 정렬이 되어 있어도 모든 루프를 돌며 비교를 수행하는 미련한 알고리즘이다. 정렬되어 있는 경우에는 루프를 취소하고 빠져나올 수 있도록 알고리즘을 개선하라. 풀이 플래그(flag) 변수를 하나 사용함으로써 문제를 해결했다. 첫 검사에서 비교를 했는데 바꿀 것이 없었다면 플래그 값은 변함이 없을 것이다. 첫 검사로부터 데이터가 정렬이 되어 있는지를 플래그를 통해 확인한다. /************************************************* ** BubbleSort Vitamin Quiz *************************************************/ #include void BubbleSort(int dataS..
Vitamin Quiz 문제) 아래 예제 프로그램에서 특정 레벨의 모든 노드를 출력하는 함수 LCRS_PrintNodesAtLevel(LCRSNode *Root, int Level)를 작성하라. 함수의 원형은 다음과 같다. void LCRS_PrintNodesAtLevel(LCRSNode *Root, int Level); 풀이 // 이 글은 드래그 및 복붙이 안되므롤 아래 첨부한 파일을 다운받아 보시기 바랍니다. 첫 번째는 교재의 소스코드, 두 번째는 데브맷의 풀이 소스입니다. 이 문제의 핵심은 원하는 레벨의 모든 노드를 출력하기 위해서는 부모노드의 정보를 기억할 필요가 있다는 겁니다. /************************************************* ** LCRSTree Vit..
Vitamin Quiz 문제) 위 예제의 AS_IsFULL(ArrayStack *Stack) 함수를 추가하라. 스택을 생성할 때 정한 용량이 가득 차 있는지 체크하는 기능이다. 함수의 원형은 다음과 같다.int AS_IsFULL(ArrayStack *Stack); 풀이 // 이 글은 드래그 및 복붙이 안되므로 아래 첨부한 파일을 다운받아 보시기 바랍니다. 첫 번째는 교재의 소스코드 및 헤더파일, 두 번째는 데브맷의 풀이입니다. 문제가 굉장히 쉽다. 왜냐하면, 애초에 ArrayStack 구조체를 정의할 때, Capacity라는 변수도 추가해줬기 때문이다. 따라서 스택이 가득 차 있는지 확이하려면 현재 배열에 들어온 원소의 갯수를 나타내는 Top 변수와 Capacity가 같은지 여부만 체크해주면 된다. /*..
- Total
- Today
- Yesterday