열혈 C프로그래밍-도전 프로그래밍1

 윤성우의 열혈 C 프로그래밍

248쪽에 위치한 '도전! 프로그래밍1'의 해설입니다.

 

 

 

 

도전1

 

 

10진수 정수를 입력받아서 16진수로 출력하는 프로그램을 작성해 보자. 이는 서식 문자의 활용에 대한 문제이므로 쉽게 해결할 수 있을 것이다.

 

 

16진수는 0~9까지의 숫자 그리고 A~F까지의 문자 총 16개를 이용하여 수를 표현하는 방법인데 이 문제에서는 배경지식이 없어도 서식 문자를 활용하면 바로 문제를 해결할 수 있다. 물론 서식문자를 이용하지 않고도 문제를 풀 수 있지만 조금 더 복잡해진다.

 

10진수 서식문자 = %d

16진수 서식 문자 = %x

이 두 개를 활용하면 된다.

 

 

코드

#include<stdio.h>
int main(void)
{
	int n;
	scanf("%d", &n);
	printf("%X", n);
}

 

 

10진수(%d)로 입력받은 뒤 16진수(%x)로 출력하면 끝이다.

참고로 %x → %X 로 바꾸면 대문자가 나오게 된다.

 

 

도전2

 

프로그램 사용자로부터 두 개의 정수를 입력받아서 구구단을 출력하는 프로그램을 작성해 보자. 예를 들어서 프로그램 사용자가 3과 5를 입력하면 3단, 4단, 5단이 출력되어야 하고, 2와 4를 입력하면 2단, 3단, 4단이 출력되어야 한다.
단 한 가지 조건이 있다. 사용자는 두 개의 숫자를 입력할 때에 입력 순서에 자유로워야 한다. 즉 3과 5를 입력하건 5와 3을 입력하건 프로그램은 같은 결과를 출력해야 한다.

 

 

반복문 중첩을 이용한 문제이다. 이 문제에서 특이사항은 입력 순서가 자유로워야 한다는 것이다.

 

 

코드

#include<stdio.h>
int main(void)
{
	int n1,n2,n3;
	scanf("%d %d", &n1, &n2);
	if(n1>n2)
	{
		n3=n1;
		n1=n2;
		n2=n3;
	}
	for(int i=n1; i<=n2; i++)
	{
		for(int z=1; z<=9; z++)
		{
			printf("%d X %d = %d\n", i,z,i*z);
		}
		printf("\n");
	}
}

 

 

n1, n2을 입력받고 n1단에서 n2단까지 구구단을 출력하는데 입력 순서에 자유를 줘야 하기 때문에 n1이 n2보다 더 큰 숫자일 경우 n1과 n2를 바꾸는 코드가 6~11행에 있다. 그리고 그 아래는 구구단을 출력하는 코드이다.

 

728x90

도전3

 

 

두 개의 정수를 입력받아서 최대 공약수(GCD)를 구하는 프로그램을 작성해 보자.

 

 

여러 가지 방법이 있는데 일반적인 방법과 책에 나온 유클리드 호제법 이 두 가지 코드를 작성해보았다.

참고로 정수는 작은 것부터 입력받았다고 가정했다.

 

 

코드

#include<stdio.h>
int main(void)
{
	int n1,n2;
	scanf("%d %d", &n1, &n2);  
	for(int i=n1; i>=1; i--)
	{
		if(n1%i==0 && n2%i==0)
		{
			printf("%d", i);
			break;
		}
	}
	return 0;
}

 

 

 

위 코드는 일반적인 방법이고 두 숫자를 각각 두 숫자 중 작은 수인 n1으로 나눈 나머지를 구하는데 둘 다 0이 나올 때까지 나누는 수를 1씩 줄여나간다. 이렇게 해서 구해진 '나누는 수'가 바로 두 수의 최대공약수이다. 이 방법은 최대 공약수로 n1, n2를 나누면 나머지가 0이 되는 성질을 이용한 것이다. 매우 간단한 방법이다.

 

 

코드

#include<stdio.h>
int main(void)
{
	int n1,n2,n3;
	scanf("%d %d", &n1, &n2);
	while(n2%n1!=0)
	{
		n2%=n1;
		n3=n1;
		n1=n2;
		n2=n3;
	}
	printf("%d", n1);
	return 0;
}

 

 

위 코드는 유클리드 호제법을 이용한 코드이다. 유클리드 호제법은 유클리드가 집필한 '원론'에 수록된 내용으로 

어떤 두수 A, B(A> B)가 있을 때 A와 B의 최대공약수는 B와A%B(A를B로나눈 나머지)의 최대공약수와 같다는 내용이다.

이해하기 쉽게 예시를 들어보자면

ex) 51,18

51%18->15

18%15->3

15%3->0

위 성질을 반복하여 최대공약수를 구했다.

즉 3이 51과 18의 최대공약수가 된다.

 위 코드는 이 내용을 그대로 옮긴 것이다.

 

 

도전4

 

 

필자가 좋아하는 것 중 하나가 금요일 저녁 퇴근길에 DVD나 만화책을 잔뜩 빌리고, 동네 슈퍼에 들러서 군것질거리를 사 가지고 집에 들어가는 것이다. 오늘은 금요일이다. 현재 필자의 주머니에는 5천 원이 있다. DVD 한 편을 빌리면 3,500원이 남는다. 슈퍼에 들려서 크림빵(500원), 새우깡(700원), 콜라(400원)를 사려한다. 잔돈을 하나도 남기지 않고 이 세 가지 물건을 하나 이상 반드시 구매하려면 어떻게 구매를 진행해야 하겠는가? 물론 여기에는 여러 가지 경우의 수가 있을 것이다. 필자가 어떠한 선택을 할 수 있는지 여러분이 제시해 주기 바란다.

 

 

이 문제가 어려워 보일 수도 있는데 이 문제는 브루트 포스 알고리즘을 이용하면된다. 

브루트포스 알고리즘은 모든 경우의 수를 고려하는 것으로 일명 노가다이다.

 

 

코드

#include<stdio.h>
int main(void)
{
	for(int i=1; i<=5 ;i++)
	{
		for(int z=1; z<=7; z++)
		{
			for(int x=1; x<=8; x++)
			{
				if(i*700+z*500+x*400==3500)
				{
					printf("크림빵 %d개, 새우깡 %d개, 콜 라 %d개\n", z,i,x);
				}
			}
		}
	}
	return 0;
}

 

 

i=새우깡(700원), z=크림빵(500원), x=콜라(400원)이다. 

문제에서 각각 최소한 하나 이상 구매하라고 하였으니 i, z, x는 각각 1부터 시작해야 하며

한 가지 종류만 구매한다 하였을 때 새우깡은 5개, 크림빵은 7개 콜라는 8개까지 구매할 수 있으므로 

for문에서도 여기까지만 구하도록 한다.

그렇게 모든 경우의 수를 구해가며 총물건의 합이 3500원일 때 각각 얼마나 구매하는지 출력하면 된다.

 

 

 

도전5

 

 

10개의 소수(Prime Number)를 출력하는 프로그램을 작성해 보자. 참고로 정수 num이 1과 num으로 밖에 나눠지지 않는다면 이는 소수에 해당한다. 따라서 3은 소수이다. 그러나 4는 소수가 아니다. 1, 2, 4로 나눠지기 때문이다.

 

 

소수를 구하는 방법에는 여러 가지 방법이 있다.

에라토스테네스의 체와 같은 방법도 있지만 

가장 간단하다고 생각되는 방법을 소개하겠다.

 

 

코드

#include<stdio.h>
int main(void)
{
	int n=0;
	for(int i=0; i<10; i++)
	{
		n++;
		while(1)
		{
			int count=0;
			for(int z=1; z<=n; z++)
			{
				if(n%z==0)
					count++;
			}
			if(count==2)
			{
				printf("%d ", n);
				break;
			}
			else
				n++;
		}
	}
}

 

 

이 방법은 소수가 10개 나올 때까지 어떤 수 n을 1이라 정하고 이 n을 1~n로 나눈 나머지를 각각 구해 나머지가 0이었던 적이 2번이면 소수라 정하고 아니면 n을 1씩 더해나가는 방법이다. 

즉 숫자 하나하나마다 소수인지 아닌지 체크하는 방법이 다.

이 방법이 가장 시간 복잡도가 간단하다고는 말할 수 없지만 직관적으로 보기에 이해하기 쉬운 방법이다.

 

 

 

도전6

 

 

프로그램 사용자로부터 초(second)를 입력받은 후에, 이를 [시, 분, 초]의 형태로 출력하는 프로그램을 작성해 보자.

 

 

코드

#include<stdio.h>
int main(void)
{
	int cho,hour,minute,second;
	printf("초를 입력하세요.");
	scanf("%d", &cho);
	second=cho%60;
	hour=cho/3600;
	minute=(cho-3600*hour)/60;
	printf("%d시간 %d분 %d초입니다.", hour, minute, second);
	return 0;
}

 

 

'초'는 입력받은 시간을 60으로 나눈 나머지이다. 60초마다 1분으로 바뀌기 때문이다. 

1시간은 3600초이니 입력받은 시간을 3600으로 나누고 나온 몫이 '시간'이다.

'분'은 입력받은 시간에서 '시간'*3600을 빼주어 후에 60으로 나눴을 때 분은 최대 59분까진데 60 이상의 값이 나오는 것을 막아준 다음 60으로 나누면 값이 나온다.

 

 

도전7

 

 

프로그램 사용자로부터 숫자 n을 입력받는다. 그러고 나서 다음 공식이 성립하는 k의 최댓값을 계산해서 출력하는 프로그램을 작성해 보자.

 

 

코드

#include<stdio.h>
int main(void)
{
	int n,k=0,g=1;
	printf("정수입력");
	scanf("%d", &n);
	while(1)
	{
		g *=2;
		if(g>n)
			break;
		k++;
	}
	printf("%d", k);
}

 

 

n을 입력받고 g는 1부터 시작해 2를 곱하고 곱할 때마다 k값에 1을 더해준다.

g가 n보다 커질 때까지 곱한 다음 k값을 출력해주면 된다.

간단한 문제이지만 g> n인지 g>=n인지 잘 생각해주어야 된다.

만약 g>=n이라 작성하였을 경우 2,4,8에서 k값이 1,2,3이 아닌 0,1,2로 

잘못된 값이 나온다.

 

도전8

 

 

2의 n승을 구하는 함수를 재귀적으로 구현해 보자. 그리고 그에 따른 적절한 main함수도 구현해 보자. 참고로 재귀 함수의 구현이 처음에는 어려운 편이기 때문에 여기서는 쉬운 문제를 제시하였다(본문에 소개한 예제보다도 쉬운 문제다).

 

 

코드

#include<stdio.h>
int jecob(int x)
{
	static int y=1;
	if(x==0)
		return y;
	y*=2;
	jecob(x-1);
}
int main(void)
{
	int n;
	scanf("%d", &n);
	printf("%d", jecob(n));
	return 0;
 }

 

 

재귀 함수를 이용하여 구하여야 한다.

함수에서 y값에 2를 곱해주는 데

2의 n승이라면 n번 곱해야 하므로

jecob(x-1) 이렇게 호출해주면 n, n-1, n-2...1까지 총 n번 호출되고 2가 n번곱해진다

그리고 함수에 0이 들어가게 되면 y값을 리턴해준다. 

주의해야 할 점은 만약 2의 0승은 값이 1이 나와야 하므로 

처음 y값을 설정할 때 1로 설정해야 한다.

그리고 변수 y값을 선언할 때 static선언을 해주었는데 이렇게 안 해주면 함수가 호출될 때마다 y값이 1로 초기화되어 

올바른 값이 나오지 않는다.