공룡호가 사는 세상 이야기

strcmp() 구현

프로그래밍2006. 1. 25. 15:06
int ustrcmp(char *a, char *b)
{
while (*a == *b && *a != 0)
{
a++;
b++;
}
return *a - *b;
}

풀어야 할 문제가 어떤 것인가?
그 문제를 어떻게 해결해야 할 것인가?
에 대한 대답을 구하고 난 다음에 곧바로 코딩에 들어가곤 한다.

메인함수를 제외한 함수의 개수가 일정이상을 초과하면,
메인함수로 부터 처음 호출당한 함수가 또다른 함수를 호출하게 되고,
호출받은 함수는 또 다른 함수를 호출하게 된다.
이런 순환이 반복되다가 일정규모를 넘어서게 되면 프로그램의 제어를 대체 어디서 담당하고 있는지 알 수 없게 된다.
결국, 소스는 엉키게 되고 무분별한 변수와 반복문으로 도배가 되기 시작한다.

함수는 각각의 독립적인 일만 수행하게 작성하되,
그 함수들의 제어는 메인함수에서 담당하게 작성할것.


오늘도 하루종일 개삽질... 결국 또 수정. ㅠㅠ

'프로그래밍' 카테고리의 다른 글

함수 호출시 2차원 배열을 파라메터로 사용할 수 없다???  (2) 2006.01.26
strcmp() 구현  (0) 2006.01.25
strchr()의 사용법  (0) 2006.01.23
DP(Dynamic Programming)  (0) 2006.01.20
fseek() 함수  (1) 2006.01.19

원형 : void *strchr(char *str,char ch)

*str문자열, ch문자, str에서 처음찾은 ch의 주소를 반환한다.
일치하는 결과가 없을 경우 리턴값은 '0'이다.

str이 i am a boy이고 ch가 a라면
p = strchr(str,ch)라고 한다면 p에 i am의 a의 주소가 반환된다.

int *p
while( p = strchr(str, ' ') )
*p = '_'; //str에 포함된 공백문자를 '_'로 치환

'프로그래밍' 카테고리의 다른 글

strcmp() 구현  (0) 2006.01.25
프로그램을 작성할 때  (0) 2006.01.24
DP(Dynamic Programming)  (0) 2006.01.20
fseek() 함수  (1) 2006.01.19
문자형 숫자('1', '2')를 숫자로 바꾸려면?  (0) 2006.01.19

정보올림피아드 알고리즘 자료집 No.13
난이도 ★★★☆☆

1 , 5 , 10 , 40 , 50 (원) 의 동전이 들어있는 자판기가 있다.
투입금액과, 물건금액을 입력하면, 위의 동전을 사용하여(모두 사용할 필요는 없다) 잔돈을 거슬러주는 프로그램을 작성하라.
구매자의 호주머니를 가볍게 해 주기 위하여 거슬러 주는 동전의 개수가 최소가 되어야 한다.

프로그램의 이름은 “coin"으로 한다.

입력 형식
입력 파일 이름은 “Input.txt"로 한다.
한 줄에 자동판매기에 넣은 지폐의 금액 W(0≤W≤100000)과 물건의 가격이 주어진다.

출력 형식
출력 파일 이름은 "Output.txt"로 한다.
각 줄에 각 동전별(50 40 10 5 1) 순서대로 사용한 동전의 개수를 출력한다.

입력의 예(1) - (Input.txt)
1000 863

출력의 예(1) - (Output.txt)
1
2
0
1
2

입력의 예(2) - (Input.txt)
100000 753

출력의 예(2) - (Output.txt)
1984
1
0
1
2

문제의 배경 및 관련 알고리즘

1. 그리드 알고리즘(Greedy, 욕심쟁이)
- 현재 상황에서 가장 좋아 보이는 것을 택하는 것이다. 그 이유는 현재 상황에서 가장 좋은 것을 선택했을 때 전체적인 상황이 가장 좋게 되도록 하기 위함이다.
상당부분 그리드 알고리즘으로 최적 해를 구할 수 있다. 그러나 모든 경우에 그리드 방법이 통하는 것은 아니다. 또한 대부분의 휴리스틱의 문제의 경우 그리드 알고리즘을 사용하면 최적 해에 근접한 결과를 얻을 수 있다. 그리드 알고리즘을 사용하는 문제의 유형으로 동전교환문제, 냅색문제 등이 있다.

2. 다이나믹(Dynamic)
- 모든 해를 다 찾아보되 한번 찾아본 해는 다시 찾지 않고 찾아진 결과를 가져다 보는 것. 소스가 간결한 편이며 그리드 알고리즘과 함께 가장 많이 쓰이는 풀이법 중 하나임.

3. 백트래킹(Backtracking, 퇴각검색)
- 주어진 조건을 만족하는 최적해 또는 해들의 집합을 찾는 문제에 주로 사용하는 방법으로 주어진 상태공간을 트리로 구성해서 깊이우선 탐색(DFS) 등을 이용하여 상태공간을 체계적으로 탐색하는 방법이다.
이는 그리드 알고리즘 등으로는 효율적으로 해결할 수 없는 문제에 적용하여 최적해에 접근할 수 있으나 지수 시간의 복잡도를 갖는 단점이 있다. 이를 극복하기 위해 트리의 각 노드에서 더 이상 탐색이 필요 없는 부분을 제외시킴으로서 탐색할 범위를 줄이는 방법이 있다.

문제의 접근

일반적으로 우리 일상에서 사용하고 있는 동전을 이용한 동전교환 문제는 그리드(Greedy) 알고리즘을 이용하여 최소 동전의 개수를 바꿀 수 있다. 만약 동전이 아래와 같이 1원, 5원, 10원, 50원의 동전을 사용하고 있을 때,

1 5 10 50

137원의 동전을 거슬러 줘야 한다면 사용하고 있는 1원, 5원, 10원, 50원의 동전 중 금액이 제일 큰 50원을 거슬러 줄 수 없을 때까지 거슬러 준 다음 10원짜리 동전을 같은 방법으로 거슬러 주고 다음은 5원짜리 1원짜리 동전 순으로 거슬러 주면 된다.
137원에서 50원짜리는 최대 2개를 거슬러 줄 수 있고 이때 37원이 남는다. 50 50 37원에서 10원짜리는 최대 3개를 거슬러 줄 수 있고 이때 7원이 남는다.
10 10 10 7원에서 5원짜리는 최대 1개를 거슬러 줄 수 있고 이때 2원이 남는다.
5 2원에서 1원짜리로 2개를 거슬러 주면 잔액은 0원이 된다.
1 1 따라서137원을 최소동전의 개수로 거슬러 주기위한 동전의 개수는 50원 2개, 10원 3개, 5원 1개, 1원 2개로 총 8개가 된다.
그리드 알고리즘을 사용하기 위해서는 큰 액수의 동전은 작은 액수의 동전의 “배수” 관계일 때에만 가능하다. 5원짜리가 2개 있다면 합이 10원으로 5원짜리 2개보다 10원짜리 한개가 더 최소한의 동전 교환 개수가 되기 때문에 서로 배수 범위보다 큰 동전의 개수를 갖지는 못한다.
즉, 어느 동전을 가지고 있을 때 그 합이 한 단계 위의 동전만큼 된다면 그것은 최소한의 동전 개수라고 할 수 없다.
그러나 주어진 문제처럼 40원짜리 동전을 새로 만들어 냈다면 새로 만든 40원1원, 5원,10원과의 배수관계는 성립하지만 50원과의 배수관계는 성립하지 않기 때문그리드 방법으로 해를 구하면 항상 최적해가 나오는 것은 아니다.
만약 137원을 동전으로 바꿀 때 그리드 알고리즘을 이용하면 50원짜리 2개, 40원짜리 0개, 10원짜리 3개, 5원짜리 1개, 1원짜리 2개로 총 8개의 동전이 필요하다. 그러나 달리 생각을 하면 50원짜리 1개, 40원짜리 2개, 10원짜리 0개, 5원짜리 1개, 1원짜리 2개로 총 6개가 필요함을 볼 수 있다.
이제 동전을 최소 개수로 거슬러줄 때 항상 최적 해를 구하기 위해 다이나믹(Dynamic)방법을 생각해 보자. 장황하다.....;
다이나믹 방법은 동전을 거슬러줄 모든 금액을 다 살펴보아야 하지만 한번 살펴본 같은 금액을 찾기 위해 다시 반복해서 계산할 필요가 없는 특징이 있다.
예를 들어 1원짜리 동전과 5원짜리 동전이 있다고 할 때 11원을 만들려고 한다면 11원은 “6원”에 5원짜리 동전 1개를 추가해서 만들거나 아니면 “6원”에 1원짜리 동전 5개를 추가 해서 만들 수 있다. 그렇다면 6원을 만들기 위해서는 최소한의 동전이 몇 개 필요한지 알아보자. 6원은 1원짜리 동전 6개나 1원짜리 동전 1개와 5원짜리 동전 1개로 만들 수 있는데 “1원+5원”으로 6원을 만드는 것이 최적이라는 것을 알 수 있다.
최적해인 6원(1원+5원)을 이용해 11원의 최소 동전 개수를 구할 때 다시 사용할 수 있다는 것이다.
각각 a, b, c, d원 짜리 동전이 여러 개 있다고 가정하자. 위 문제와 같은 방식으로 한다면 p원을 만들기 위해 a+(p-a)원이나, b+(p-b)원 등을 만들 수 있다.
즉, a+(p-a), b+(p-b), c+(p-c), d+(p-d) 등으로 나누어 생각할 수 있다. 반복되는 계산을 막기 위해 1원부터 p원까지 위의 방법으로 차례대로 만들어 나간다.
m원을 만들기 위해, m-a, m-b, m-c, m-d원을 만들기 위해 필요한 최소 개수의 동전을 찾은 뒤 그 값에 +1(그 값에 a, b, c, d원을 추가시켰으므로)을 해주기만 하면 m원을 만드는데 필요한 최소 동전의 개수를 알 수 있는 것이다.

따라서,
1원 1개 1원×1
...
4원 4개 1원×4
5원 1개 5원×1


4(5-1)원, 0(5-5)원을 만들기 위한 최소 동전의 개수가 각각 4원이 4개, 0원이 0개 이므로 여기에 +1을 해주면 5개와 1개가 나온다. 1개가 최소 동전의 개수이므로 5원을 만들 수 있는 최소 동전의 개수는 1개이다.

6원 2개 1원×1, 5원×1
7원 3개 1원×2, 5원×1
...
10원 1개 10원×1


9(10-1)원, 5(10-5)원, 0(10-10)원을 만들기 위
한 최소 동전의 개수가 각각 9원이 5개, 5원이 1
개, 0원이 0개 이므로 여기에 +1을 해주면 6개,
2개, 1개가 나온다. 1개가 최소 동전의 개수이므
로 10원을 만들 수 있는 최소 동전의 개수는 1
개이다.

80원 2개 40원×2

79(80-1)원, 75(80-5)원, 70(80-10)원, 40(8
-40)원, 30(80-50)원을 만들기 위한 최소 동전
의 개수가 각각 8개, 4개, 3개, 1개, 3개이므로
여기에 +1을 해서 가장 적은 동전의 개수는 2개
이다.

이러한 방식으로 최적 해에 점차 접근하는 방법을 DP라 한다.

반드시 DP로 풀어야 하는 것은 아니다.
( 백트래킹 + 그리드 ) 알고리즘 방식으로도 가능할 것 같다. 알고리즘은 아래와 같다.

퇴각검색은 모든 가능한 경우를 검색하는 방법으로 퇴각검색의 효율을 높이기 위해서는 먼저 그리드 알고리즘으로 동전의 개수의 상한을 설정하고 그 이후에 발견된 해 중 가장 좋은 해를 결정해야한다.
만약 동전의 종류가 1원, 5원, 10원, 40원, 50원이 있을 때 137원을 최소 동전의 개수로 바꾼다면 먼저 137원에서 동전 1원, 5원, 10원, 40원, 50원을 하나씩 바꿀 때의 5가지 경우로 나누어 생각해 본다. 그런 다음 다시 136원, 132원, 127원, 97원, 87원 중에서 다시 1원, 5원, 10원, 40원, 50원을 하나씩 바꿀 때의 각각 5가지 경우를 금액이 0원이 될 때까지 고려하는 방법이다.

퇴각검색은 모든 가능한 경우를 다 살펴보는 경우이기 때문에 시간이 다른 알고리즘에 비해 많이 소요된다. 때문에 시간을 단축하려면 간단한 그리드 알고리즘을 이용해 해를 구한 다음 이 해를 기준점으로 해서 현재 검색하고 있는 방향의 퇴각검색의 해가 그리드 알고리즘의 결과 해보다 클 때에는 더 이상 그 방향을 탐색하지 않는 pruning 기법을 이용하여 다른 방향을 검색해야 한다(N-Queen에서 불가능하면 더이상 가지 않았던 방식과 동일)

[# Dynamic Programming #]

#include <stdio.h>
#include <memory.h> //memset() / memcpy
#define MAX 100000 //잔돈 액수 제한(10만원)
#define INPUTFILE "input.txt" //이것도 define이 되는걸 처음 알게됨(06.01.19)
#define OUTPUTFILE "output.txt"

int g_Send_money, g_TValue, g_Change; //앞에서부터 준돈, 물건값, 잔돈
int Result[MAX+1][5]; //결과값 배열

//입력(from file)
void input(void)
{
FILE *pIF=fopen(INPUTFILE, "rt");
fscanf(pIF, "%d %d", &g_Send_money, &g_TValue);
g_Change = g_Send_money - g_TValue;
fclose(pIF);
}

//프로세스
void DP(void)
{
int Times[MAX+1]; //동전의 빈도수를 임시로 가지고 있을 배열(if문 비교위해)
int Money[5]={50, 40, 10, 5, 1};
int i, j;

memset(Times, 127, sizeof(Times));
Times[0]=0;

memset(Result[0], 0, sizeof(int)*5);

for (i=1; i<=g_Change; i++) //i의 범위(1 <= i <= 잔돈)
for (j=0; j<5; j++) //j는 동전배열을 돌린다(순서 : 50 -> 1)
//동전의 최소금액 <= 잔돈 && 최소 동전 개수를 체크
if (Money[j]<=i && Times[i-Money[j]]+1<Times[i])
{
//i금액을 만들어 내는 최소동전 개수 Times[i]에 저장(값 = 동전 개수)
Times[i]=Times[i-Money[j]]+1;

// printf("잔돈 = %d, Times[i] = %d\n", i, Times[i]); //중간값 임시출력(주석)

//i금액을 만드는 j동전의 종류별로 개수를 모두 누적(=Result[i])=총 동전개수
memcpy(Result[i], Result[i-Money[j]], sizeof(int)*5);

//마지막 값을 기록(각 동전별로 사용된 회수)
Result[i][j]++;
}
}

//출력(to file)
void output(void)
{
FILE *pOF=fopen(OUTPUTFILE, "wt");
fprintf(pOF, "%d\n%d\n%d\n%d\n%d\n",
Result[g_Change][0], Result[g_Change][1],
Result[g_Change][2], Result[g_Change][3],
Result[g_Change][4]);
fclose(pOF);
}

//메인
void main(void)
{
input();
DP();
output();
}


[# Backtracking + Greedy #]

이건... 내일.. 하든지... ㅠㅠ....

'프로그래밍' 카테고리의 다른 글

프로그램을 작성할 때  (0) 2006.01.24
strchr()의 사용법  (0) 2006.01.23
fseek() 함수  (1) 2006.01.19
문자형 숫자('1', '2')를 숫자로 바꾸려면?  (0) 2006.01.19
strcmp() 함수  (0) 2006.01.19

fseek() 함수

프로그래밍2006. 1. 19. 14:13
fseek() : 파일 포인터를 특정 위치로 이동시킨다.

int fseek(FILE *fp, long offset, int origin);

*fp : 파일과 연결된 FILE 포인터
offset : 위치 표시자가 이동하는 거리(바이트 단위)
orgin : SEEK_SET 0 파일의 시작 부분으로부터 표시자를 offset 바이트 이동
orgin : SEEK_CUR 1 파일의 현재 위치로부터 표시자를 offset 바이트 이동
orgin : SEEK_END 2 파일의 끝에서부터 표시자를 offset 바이트 이동

'프로그래밍' 카테고리의 다른 글

strchr()의 사용법  (0) 2006.01.23
DP(Dynamic Programming)  (0) 2006.01.20
문자형 숫자('1', '2')를 숫자로 바꾸려면?  (0) 2006.01.19
strcmp() 함수  (0) 2006.01.19
칼로리 계산(Back Tracking)  (2) 2006.01.18

ASCII 코드 '0'이 48인 것을 생각하면,
문자형 - '0'을 하면 간단하게 처리된다.

Ex) '2' -> '2'(50) - '0'(48) = 2
Ex) '10' -> '10'(58) - '0'(48) = 10

조금만 생각하면 유용하게 쓸 수 있다.
scanf로 문자를 받는데, 숫자가 들어갔다고 가정하자.
그러면 문자 숫자가 될 터인데, 이것을 숫자로 바꿀 때에는 다음과 같다.

while ( (ch = getchar()) != "\n" )
{
num = num * 10 + (ch - '0');
}

: 또하나의 포인트
-> num * 10숫자문자가 1개 이상일때 끝까지 읽으면서 이전에 읽었던 숫자들을 한자리씩 올려주는 역할을 한다. 즉, 다시 말하면 10진수로 바꾸기 위해 쓰였다는 것을 알 수 있다.
num * 8로 하면 8진수로, num * 16으로 하면 16진수로 바뀌어 진다.

'프로그래밍' 카테고리의 다른 글

DP(Dynamic Programming)  (0) 2006.01.20
fseek() 함수  (1) 2006.01.19
strcmp() 함수  (0) 2006.01.19
칼로리 계산(Back Tracking)  (2) 2006.01.18
ACM 10018 Reverse And Add  (0) 2006.01.16

strcmp() 함수

프로그래밍2006. 1. 19. 13:33
strcmp() : 두개의 문자열을 한 문장씩 비교, string.h에 정의

int strcmp(char *str1, char *str2);

// 함수 원형을 보면 int형을 반환값으로 갖고 있음.


Return value ?

When, str1이 str2보다 작으면 < 0 값 반환
When, str1이 str2와 같으면 0 값 반환
When, str1이 str2보다 크면 >0 값 반환

'프로그래밍' 카테고리의 다른 글

fseek() 함수  (1) 2006.01.19
문자형 숫자('1', '2')를 숫자로 바꾸려면?  (0) 2006.01.19
칼로리 계산(Back Tracking)  (2) 2006.01.18
ACM 10018 Reverse And Add  (0) 2006.01.16
ACM 10127 ONES  (0) 2006.01.16

계곡의 돌다리는 5*5개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 모두 다르며 높이에 따라 건널 때마다 칼로리가 소비된다. 첫번째 지점에서 우리가 갈려고 하는 목표 위치의 돌까지 건널 때 가장 빠르게 도망가야 한다. 가장 빠르게 건널 수 있는 방법을 미리 알아두기 위해서 건너는 순서를 알아보자.

칼로리가 정해진 5*5 돌다리

3 7 2 1 9
5 8 3 9 2
5 3 1 2 3
5 4 3 2 1
1 7 5 2 4

출발 지점은 (0,0)이고 도착지는 (4,4)이다. 5*5배열로 표시한 값들은 돌다리를 건너는데 서로 다른 높이로 인하여 오르내리는데 필요한 칼로리를 표시한 것이다. 대각선의 돌다리는 사이가 멀기 때문에 바로 아래 돌다리나 오른쪽 돌다리로만 이동할 수 있다.

Explanation :

역시나 백트래킹 문제이다. 대각선과 좌측으로 이동할 수 없으므로, 최종 도착지에 이르는 동안 방문하는 돌다리는 모두 8개.
최종 도착지에 도착하되, 가능한 방법들을 모두 조사하여 각 방법마다 소모한 칼로리 수를 누적한다. 그리고 한번의 방법마다 누적된 칼로리 수를 기초로 하여 최소값의 칼로리를 구한다음 출력하면 된다.

재귀적으로 생각할 필요가 있다. 문제를 좁혀서 생각 해 보면, 처음 출발지의 칼로리는 '3'이다. 가능한 자리는 우측 돌다리인 '7'과 아래쪽 돌다리인 '5' 2개가 있다. 그중에 우측(7)을 선택한다고 치자.
그렇다 해도 문제는 달라지지 않는다. 또다시 이동가능한 돌다리는 우측과 아래쪽 두가지 뿐이다. 처음에 아래쪽인 '5'를 선택했어도 마찬가지 이다. 그러므로 우측을 방문하는 것은 x값을 증가시켜 재귀호출, 아래쪽을 방문하는 것은 y값을 증가시켜 재귀호출 하면 되는 것.

recursion(int x, int y)
{
recursion(x+1, y);
recursion(x, y+1);
}

이 되게 되는데 무한루프를 방지하기 위하여 조건을 달아준다.
5 by 5 배열이라 했으므로, 조건을 추가하면 아래와 같다.

if (x < 4)
recursion();
if (y < 4)
recursion();

하지만 이것으로 끝나지 않는다. 방문하면서 소모한 칼로리를 누적해야 하기 때문이다. 함수의 파라메터가 하나 더 추가된다. sum이라고 해 두자. 이동할 때마다 해당 칼로리 값을 누적해야 한다.

recursion(x+1, y, sum + 우측 칼로리 값)
recursion(x, y+1, sum + 아래쪽 칼로리 값)

그래서 x와 y값이 최종적으로 4값에 도달했을 경우 (x==4 && y==4)
최소값을 갱신한다.

if (x == 4 && y == 4)
if (sum < min) // 최소값 갱신
min = sum;

이것으로 충분할 것 같지 그렇지 않다.
만약, 돌다리들을 방문하는 도중에 너무 많은 칼로리들을 소모하는 방법을 선택하는 경우라고 가정하자. 그리하여 최종 도착지점에 도착하기도 전에 누적된 칼로리 값이 현재 구해놓은 다른 방법의 최소 칼로리 값보다 커지는 경우라면 그 다음은 방문해 볼 필요가 없다.
물론 5 by 5 배열에서는 큰 속도의 성능향상이 없을수도 있다. 오히려 비교하는 시간이 더 많이 걸릴수도 있지만, 배열이 많이 커지는 경우에는 유용하다. N-Queen문제에서 이미 구현한 바 있다.

if (x < 4 && sum + 우측칼로리값 < min)
recursion();
if (y < 4 && sum + 아래쪽 칼로리값 < min)
recursion();

완성된 소스는 아래와 같다.


#include <stdio.h>
#include <limits.h> //use INT_MAX

int calorie[5][5] = {{3,7,2,1,9},{5,8,3,9,2},{5,3,1,2,3},{5,4,3,2,1},{1,7,5,2,4}};
int g_min_calorie = INT_MAX; //임의의 큰 값으로 초기화

void find(int y, int x, int sum)
{
// printf("%d ", calorie[y][x]); 중간확인을 위해 찍어봄(주석처리)

if (x == 4 && y == 4)
{
//한번의 순회후 누적된 칼로리들의 최소값을 구한다
if (sum < g_min_calorie)
g_min_calorie = sum;
}

else
{
//우측으로 이동가능 하고, 현재까지의 누적 칼로리보다 작으면 이동
if (x < 4 && g_min_calorie > sum + calorie[y][x+1])
find(y, x+1, sum + calorie[y][x+1]);

//하단으로 이동가능 하고, 현재까지의 누적 칼로리보다 작으면 이동
if (y < 4 && g_min_calorie > sum + calorie[y+1][x])
find(y+1, x, sum + calorie[y+1][x]);
}
}

void print(void)
{
printf("\nMin Calories = %d \n", g_min_calorie);
}

void main(void)
{
//0,0부터 시작, sum값은 시작값으로 초기화
find(0,0,calorie[0][0]);

//인쇄
print();
}

'프로그래밍' 카테고리의 다른 글

문자형 숫자('1', '2')를 숫자로 바꾸려면?  (0) 2006.01.19
strcmp() 함수  (0) 2006.01.19
ACM 10018 Reverse And Add  (0) 2006.01.16
ACM 10127 ONES  (0) 2006.01.16
GetTickCount() Function  (1) 2006.01.16

UVA - 10018
programming-challenges - 110502


Reverse And Add는 어떤수를 입력 받았을 때 이것을 뒤집어서 원래의 수에 더하는 과정이다.
이 과정을 반복하다가 결과가 Palindrome(앞뒤 어느쪽으로 보아도 같은 말이 되는 어구 ex : eye ,madam)이 될 때까지 반복한다.

이 Palindrome을 찾기까지의 Reverse and Add 횟수와 찾아진 Palindrome을 출력하는 프로그램을 만들어 보자.

195 + 591 = 786
786 + 687 = 1473
1473 + 3743 = 5214
5214 + 4125 = 9339

입력
그 아래부터 테스트 하려는 정수 N

출력
주어진 N에 대한 Reverse and Add횟수와 찾아진 Palindrome을 공백을 두고 출력한다.

입력 예제
195
265
750

출력 예제
4 9339
5 45254
3 6666

Explanation :
숫자를 뒤집어서 비교하면서 더해주기만 하면 되는 문제이다.
숫자를 뒤집는 방법은 여러가지가 있다. string으로 변환하여 뒤집어서 비교하는 방법, 수학적 연산으로 수를 뒤집는 방법 등이 있다.
2가지 방법으로 해결한 소스는 아래에 첨부.

1st - 숫자뒤집기

#include <stdio.h>

int process(int n)
{
int result = 0;

while(n) //입력수가 0이 아닌동안
{
result = (result * 10) + (n % 10); //결과를 10배하고 단위값 추가
n /= 10; //입력수 단위를 밀어낸다
}

return result;
}

void main(void)
{
int n, rev;
int cnt = 0;
scanf("%d", &n);

while(1)
{
rev = process(n); //뒤집기

if (n == rev) //팰린드롬 유/무 판단
{
printf("%d ", cnt);
printf("%d\n", n);
break;
}
n = n + rev; //뒤집은 값 더하기
cnt++; //reverse and add 횟수 증가
}
}


2st - 뒤집지 않고 검사 (By Won.suck)

#include <windows.h>
#include <stdio.h>
#include <sys/timeb.h>

bool isCondition( char *pNum, int length )
{
for( int i=0; i<length/2; ++i )
if( pNum[i] != pNum[length-i-1] )
return FALSE;
return TRUE;
}

void func( int input )
{
printf( "func %d\n", input );

char temp[32];
int length;
itoa( input, temp, 10 );
length = strlen( temp );

if( isCondition( temp, length ) )
printf( "Result : %s\n", temp );
else
{
int newNum = 0;
for( int i=0; i<length; ++i )
newNum = newNum*10 + (temp[i]-'0' + temp[length-i-1]-'0');
func( newNum );
}
}

void main()
{
func(195);
}

'프로그래밍' 카테고리의 다른 글

strcmp() 함수  (0) 2006.01.19
칼로리 계산(Back Tracking)  (2) 2006.01.18
ACM 10127 ONES  (0) 2006.01.16
GetTickCount() Function  (1) 2006.01.16
chaos in FOR loop  (0) 2006.01.13

ACM 10127 ONES

프로그래밍2006. 1. 16. 14:53
2나 5로 나눌 수 없는 0이상 10,000 이하의 정수 n이 주어졌는데, n의 배수 중에는 10진수로 표기할시 모든 자리 숫자가 1인 것이 있다. 그러한 n의 배수 중에서 가장 작은 것은 몇자리 수인가?

입력
한줄에 하나의 정수가 입력된다.

출력
(자세한 설명은 생략한다?) n이 1로만 이루어진 숫자의 약수일 경우 1로만 이루어진 숫자의 자릿수를 출력한다? 중복일때는 최소값을 출력한다?

입력 예제
3
7

출력 예제
3
6

입력받은 숫자와 모든 자리가 '1'인 숫자와 계속 비교

#include <stdio.h>

int process(unsigned int n)
{
unsigned long cnt = 11;
int count = 2;

if (n == 1)
return 1;

while(1)
{
if (cnt % n == 0)
return count;

cnt = cnt * 10 + 1; //모든 자리의 값이 '1'
count++; //자릿수
}
return 0;
}

void main(void)
{
unsigned int n;
scanf("%d", &n);

printf("%d\n", process(n));
}

'프로그래밍' 카테고리의 다른 글

칼로리 계산(Back Tracking)  (2) 2006.01.18
ACM 10018 Reverse And Add  (0) 2006.01.16
GetTickCount() Function  (1) 2006.01.16
chaos in FOR loop  (0) 2006.01.13
ACM 10110 Light, More Light  (0) 2006.01.13