실습 과제: C 언어 함수와 재귀 알고리즘
본 실습에서는 C 언어의 함수 정의, 재귀 호출, 그리고 기본적인 알고리즘 구현을 학습한다. 여러 가지 대표적인 프로그래밍 문제들을 통해 함수 작성법과 논리적 사고력을 키우는 것이 목표이다.
과제 1: 점수 등급 변환 프로그램
입력된 점수를 등급으로 변환하는 프로그램을 작성한다. 90점 이상은 A, 80점 이상은 B, 70점 이상은 C, 60점 이상은 D, 그 미만은 E 등급을 출력한다.
#include <stdio.h>
char convert_score(int point);
int main() {
int point;
char grade;
while (scanf("%d", &point) != EOF) {
grade = convert_score(point);
printf("점수: %d, 등급: %c\n\n", point, grade);
}
return 0;
}
char convert_score(int point) {
char result;
switch (point / 10) {
case 10:
case 9: result = 'A'; break;
case 8: result = 'B'; break;
case 7: result = 'C'; break;
case 6: result = 'D'; break;
default: result = 'E';
}
return result;
}분석:
- 기능: 정수형 점수를 등급 문자로 변환하는 역할을 수행
- 매개변수: int형 점수 값을 전달받음
- 반환값: char형 등급 문자 반환
- switch 문을 사용하여 10으로 나눈 몫을 기준으로 등급 판정
과제 2: 자릿수 합 계산
입력된 정수의 각 자릿수의 합을 구하는 프로그램을 작성한다.
#include <stdio.h>
int calculate_digit_sum(int value);
int main() {
int value;
int result;
while (printf("값 입력: "), scanf("%d", &value) != EOF) {
result = calculate_digit_sum(value);
printf("값: %d, 결과: %d\n\n", value, result);
}
return 0;
}
int calculate_digit_sum(int value) {
int sum = 0;
while (value != 0) {
sum += value % 10;
value /= 10;
}
return sum;
}분석:
- 기능: 입력된 숫자의 모든 자리수를 더한 값을 반환
- 원리: 10으로 나눈 나머지를 통해 마지막 자리수를 추출하고, 10으로 나누어 자리수를 제거하는 과정을 반복
- 반복문과 재귀 두 가지 방식으로 구현 가능
과제 3: 거듭제곱 계산
입력된 base와 exponent를 사용하여 x의 n제곱을 계산하는 프로그램을 작성한다. 재귀적인 방법을 활용한다.
#include <stdio.h>
int power_function(int base, int exp);
int main() {
int base, exp;
int result;
while (printf("base와 exp 입력: "), scanf("%d%d", &base, &exp) != EOF) {
result = power_function(base, exp);
printf("exp = %d, 결과 = %d\n\n", exp, result);
}
return 0;
}
int power_function(int base, int exp) {
int temp;
if (exp == 0)
return 1;
else if (exp % 2)
return base * power_function(base, exp - 1);
else {
temp = power_function(base, exp / 2);
return temp * temp;
}
}분석:
- 기능: 지정된 지수만큼 base의 거듭제곱을 계산
- 원리: 분할 정복(Divide and Conquer) 기법 활용 - 지수가 짝수일 때는 반으로 나눠서 계산하고, 홀수일 때는 하나를 뺀 후 곱함
- 시간 복잡도: O(log n)
과제 4: 쌍둥이 소수 찾기
100 이하의 쌍둥이 소수(Twin Prime)를 찾는 프로그램을 작성한다. 쌍둥이 소수란 차이가 2인 두 소수의 쌍을 의미한다.
#include <stdio.h>
#include <math.h>
int check_prime(int num) {
int i;
if (num <= 1) {
return 0;
}
for (i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return 0;
}
}
return 1;
}
int main() {
int count = 0;
int i;
printf("100 이하의 쌍둥이 소수:\n");
for (i = 1; i <= 100; i++) {
if (check_prime(i) && check_prime(i + 2)) {
printf("%d %d\n", i, i + 2);
count++;
}
}
printf("100 이하의 쌍둥이 소수 개수: %d개", count);
return 0;
}실행 결과:
3 5 5 7 11 13 17 19 29 31 41 43 59 61 71 73 100 이하의 쌍둥이 소수 개수: 8개
과제 5: 하노이 타워
전형적인 하노이 타워 문제를 재귀적으로 해결하는 프로그램을 작성한다. 원반을|source柱子에서 목표 기둥으로 이동하는 최소 이동 횟수를 구한다.
#include <stdio.h>
int hanoi_tower(int disc, char source, char target, char auxiliary)
{
if (disc == 1)
{
printf("1: %c -> %c\n", source, target);
return 1;
}
int moves = hanoi_tower(disc - 1, source, auxiliary, target) + 1;
printf("%d: %c -> %c\n", disc, source, target);
moves += hanoi_tower(disc - 1, auxiliary, target, source);
return moves;
}
int main()
{
int disc;
char source, target, auxiliary;
while (scanf("%d", &disc) != EOF)
{
getchar();
scanf("%c %c %c", &source, &auxiliary, &target);
int moves = hanoi_tower(disc, source, target, auxiliary);
printf("총 이동 횟수: %d\n\n", moves);
}
return 0;
}분석:
- 원리: n개의 원반을 이동하기 위해 n-1개의 원반을 보조 기둥으로 옮기고, 가장 큰 원반을 목표 기둥으로 이동시킨 후, 다시 n-1개를 목표 기둥으로 옮김
- 이동 횟수: 2^n - 1
- 전형적인 재귀 호출의 예시
과제 6: 조합 계산 (nCm)
주어진 n과 m에 대해 조합 nCm을 계산하는 프로그램을 작성한다. 반복적 방법과 재귀적 방법 두 가지로 구현한다.
반복적 구현
#include <stdio.h>
int combination_iterative(int n, int m)
{
int result = 1;
for (int i = 0; i < m; i++)
{
result *= n--;
}
for (int i = 1; i <= m; i++)
{
result /= i;
}
return result;
}
int main()
{
int n, m;
int result;
while(scanf("%d%d", &n, &m) != EOF){
if (n < m)
{
printf("n = %d, m = %d, 결과 = 0\n\n", n, m);
continue;
}
result = combination_iterative(n, m);
printf("n = %d, m = %d, 결과 = %d\n\n", n, m, result);
}
return 0;
}재귀적 구현
#include <stdio.h>
int combination_recursive(int n, int m)
{
if (m == n || m == 0)
return 1;
else
return combination_recursive(n - 1, m) + combination_recursive(n - 1, m - 1);
}
int main()
{
int n, m;
int result;
while(scanf("%d%d", &n, &m) != EOF){
if (n < m)
{
printf("n = %d, m = %d, 결과 = 0\n\n", n, m);
continue;
}
result = combination_recursive(n, m);
printf("n = %d, m = %d, 결과 = %d\n\n", n, m, result);
}
return 0;
}분석:
- 반복적 방법: n! / (m! × (n-m)!) 공식을 직접 계산
- 재귀적 방법: 파스칼의 삼각형 원리 활용 - C(n,m) = C(n-1,m) + C(n-1,m-1)
- 재귀적 방법은 중복 계산이 발생하여 비효율적일 수 있으나, 알고리즘 이해에 도움됨
과제 7: 아스키 아트 출력
입력된 숫자에 따라 크기가 변하는 스틱맨 아트 패턴을 출력하는 프로그램을 작성한다.
#include <stdio.h>
#include <stdlib.h>
void draw_pattern(int height);
int main() {
int height;
printf("높이 입력: ");
scanf("%d", &height);
draw_pattern(height);
return 0;
}
void draw_pattern(int height)
{
int offset = 0;
for (int i = height; i >= 1; i--)
{
for (int j = 0; j < offset; j++)
printf("\t");
for (int j = 0; j < 2 * i - 1; j++)
printf(" o\t");
printf("\n");
for (int j = 0; j < offset; j++)
printf("\t");
for (int j = 0; j < 2 * i - 1; j++)
printf("<H>\t");
printf("\n");
for (int j = 0; j < offset; j++)
printf("\t");
for (int j = 0; j < 2 * i - 1; j++)
printf("I I\t");
printf("\n");
offset++;
}
}분석:
- 입력값에 따라 삼각형 형태로 스틱맨 패턴이 출력
- 중첩 반복문을 사용하여 행과 열 제어
- 오프셋 값을 이용해 점층적으로 들여쓰기 증가
결론
본 실습을 통해 C 언어의 함수 정의 및 호출, 반복문과 재귀 호출, 기본적인 수학 알고리즘(소수 판정, 조합, 하노이 타워) 등을 학습하였다. 이러한 기본 알고리즘들은 추후 더 복잡한 프로그램을 개발할 때 필수적인 기반 역량이 된다.