DevMoon's 살아가는 이야기

문제

다른 사람들 보니 다들 그래프로.. 풀었길래 따라하는건 양심에 걸려서 새롭게 풀어보았다.

처음에 짰던 재귀형식으로 고민하다가 너무 오래 걸려서 새로운 전략을 짰다.

새로운 해결전략은 다음과 같다. (brand new!!)

한마디로 distance가 1인 집합에 계속해서 끌어들이는 방법이다.

이에따른 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_WORD_NUM	8192
#define MAX_WORD_LEN	6

int nwords;
int elem[MAX_WORD_NUM];

char dic[MAX_WORD_NUM][MAX_WORD_LEN];

int makedic(char *fname)
{
	FILE *fp = NULL;

	fp = fopen(fname, "r");

	if (!fp) {
		printf("%s open fail.\n", fname);
		return 0;
	}

	int n = 0;

	while(1)
	{
		n = fscanf(fp, "%s", dic[nwords]);
		if (n == EOF) break;
		nwords++;
	}

	fclose(fp);
	return 1;
}

int distance(char *w1, char *w2, int len)
{
	int count = 0;

	for(int i = 0; i < len; i++) {
		if (w1[i] != w2[i]) {
			count++;
		}
	}

	return count;
}

int getpage(char *word)
{
	for(int i = 0; i < nwords; i++) {
		if (!strcmp(word, dic[i])) return i;
	}

	return -1;
}

int find(char *word, char *target, int len)
{
	int src_idx = getpage(word);

	if (src_idx == -1) return 0;

	elem[src_idx] = src_idx+1;

	while(1)
	{
		int find_newelem = 0;

		for(int i = 0; i < nwords; i++) 
		{
			if (elem[i])
			{
				for(int j = 0; j < nwords; j++)
				{
					if (elem[j] == 0 && distance(dic[i], dic[j], len) == 1)
					{
						// add new element.
						elem[j] = i+1;

						if (!strcmp(dic[j], target)) return j;

						find_newelem = 1;
					}
				}
			}
		}

		if (find_newelem == 0) break;
	}

	return 0;
}

int main(int argc, char *argv[])
{
	if (argc != 2) {
		printf("Usage: %s dictionary\n", argv[0]);
		exit(1);
	}

	// make dictionary
	if (makedic(argv[1]) == 0) {
		printf("file open fail.\n");
		exit(1);
	}

	// get input
	char src[MAX_WORD_LEN], target[MAX_WORD_LEN];

	scanf("%s %s", src, target);

	// running...
	int rtn = find(src, target, strlen(src));

	if (rtn == 0) {
		printf("IMPOSSIBLE\n");
	} else {
		// make trace
		int idx = rtn, ntrace = 0;
		int trace[MAX_WORD_NUM];

		while(1)
		{
			trace[ntrace++] = idx;
			if (!strcmp(dic[idx], src)) break;
			idx = elem[idx]-1;
		}

		// print trace
		printf("%s", dic[trace[ntrace-1]]);

		for(int i = ntrace-2; i >= 0; i--) {
			printf(" -> %s", dic[trace[i]]);
		}
		printf("\n");
	}

	return 0;
}

다음은 시험결과

damp like 입력에 대한 답이 예시 답안보다 길어서 맘에 안들긴 하지만 정답이긴 하니 뭐.

이제 심화 문제를 좀 더 고민해봐야지 -_-a

################################################################################################

심화문제 1(가장 적은 단어 사용하기) 해결~! 각 단어마다 distance를 저장해둘 필요가 있다. 

코드는 다음과 같이..

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_WORD_NUM	8192
#define MAX_WORD_LEN	6

int nwords;
int dist[MAX_WORD_NUM];
int from[MAX_WORD_NUM];

char dic[MAX_WORD_NUM][MAX_WORD_LEN];

int makedic(char *fname)
{
	FILE *fp = NULL;

	fp = fopen(fname, "r");

	if (!fp) {
		printf("%s open fail.\n", fname);
		return 0;
	}

	int n = 0;

	while(1)
	{
		n = fscanf(fp, "%s", dic[nwords]);
		if (n == EOF) break;
		nwords++;
	}

	fclose(fp);
	return 1;
}

int distance(char *w1, char *w2, int len)
{
	int count = 0;

	for(int i = 0; i < len; i++) {
		if (w1[i] != w2[i]) {
			count++;
		}
	}

	return count;
}

int getpage(char *word)
{
	for(int i = 0; i < nwords; i++) {
		if (!strcmp(word, dic[i])) return i;
	}

	return -1;
}

int find(char *src, char *target, int len)
{
	int src_idx = getpage(src);

	if (src_idx == -1) return 0;

	dist[src_idx] = 1;

	while(1)
	{
		int updated = 0;

		for(int i = 0; i < nwords; i++)
		{
			if (dist[i])
			{
				for(int j = 0; j < nwords; j++)
				{
					if (distance(dic[i], dic[j], len) == 1) 
					{
						// update distance
						if (dist[j] == 0 || dist[j] > dist[i]+1) 
						{
							dist[j] = dist[i]+1;
							from[j] = i;
							updated = 1;
						}
					}
				}
			}
		}

		if (updated == 0) break;
	}

	int target_idx = getpage(target);
	
	if (dist[target_idx]) {
		return target_idx;
	}

	return 0;
}

int main(int argc, char *argv[])
{
	if (argc != 2) {
		printf("Usage: %s dictionary\n", argv[0]);
		exit(1);
	}

	// make dictionary
	if (makedic(argv[1]) == 0) {
		printf("file open fail.\n");
		exit(1);
	}

	// get input
	char src[MAX_WORD_LEN], target[MAX_WORD_LEN];

	scanf("%s %s", src, target);

	// running...
	int rtn = find(src, target, strlen(src));

	if (rtn == 0) {
		printf("IMPOSSIBLE\n");
	} else {
		// make trace
		int idx = rtn, ntrace = 0;
		int trace[MAX_WORD_NUM];

		while(1)
		{
			trace[ntrace++] = idx;
			if (!strcmp(dic[idx], src)) break;
			idx = from[idx];
		}

		// print trace
		printf("%s", dic[trace[ntrace-1]]);

		for(int i = ntrace-2; i >= 0; i--) {
			printf(" -> %s", dic[trace[i]]);
		}
		printf("\n");
	}

	return 0;
}

다음은 시험결과

역시 결과가 달라졌다 음하핫. 시간은 좀 더 걸리지만..

이번 문제는 정말 꼼수(?)로 푼것같다 -_-; 한마디로 수학적인 검증? 철학? 이런게 없ㅋ엉ㅋ 

일단 나의 답. 다른 사람들과 비교하니 맞는 것같다.

아래 책에서 나온 문제라는 것!!

문제는 아래와 같다. (새창으로보기)

저 어마어마한 숫자들을 다 저장한다는건 문제를 포기하겠다는 것이고 ..

생각해보니 0이 몇개인지를 카운트 해두고 앞에 몇자리 수만 기억해두면 될 것같았다. 

어차피 곱하기 할 때 앞자리 많은 수들은 0을 만들어내는 것과 관계가 없으므로. 

코드는 아래와 같이.. 짧게 @_@;

#include <stdio.h>

int main()
{
	int N = 0, zeros = 0;
	int mult = 1;

	scanf("%d", &N);

	for(int i=1; i<=N; i++) 
	{
		int div = 10;

		mult *= i;
		while(mult % div == 0) 
		{ 
			div *= 10; 
			zeros++;
		}

		mult /= (div/10);
		mult %= 100000;
	}

	printf("%d %d\n", zeros, mult%10);

	return 0;
}

첫 문제에 이어 두 번째 문제에 도전했다. (책표지 서비스~ 부탁받은대로~ㅋㅋ)

아래 책에 있는 문제라네.

두번째 문제는 개인적으로 너무 어려웠다. 아.. 남은 문제들은 어떻게 푸냐 -_-;;;

규칙을 찾는데 상당히 오래 걸렸는데 그 규칙은 다음과 같다.

이렇게 되는 것이다. 이걸 찾아내는게...참.. 후덜덜..ㅠㅠ

Python, C++, Perl 등 고차원 언어로 짜면 더 간단하게 표현 할 수 있겠지만 난 C로 짰다.

C로 구현하려니 독립적인 집합 표현하기가 힘들었다.

구조체를 이용하다가 코드가 지저분해져서 array의 index를 집합에 들어갈 값으로 하고, 

array 값을 집합 번호로 만들어 구현했다. 덕분에 코드는 좀 깔끔하게 나온듯하다.

#include <stdio.h>

//================================================
// TEST SET
//================================================
const int MAX_N = 16;
const int N = 4;
//================================================

int getMaxGroup(int *array, int size)
{
	int maxGroup = -1;

	for(int i = 0; i < size; i++) {
		if (array[i] > maxGroup) 
			maxGroup = array[i];
	}

	return maxGroup;
}

void printArray(int *array, int size)
{
	int maxGroup = getMaxGroup(array, size);

	for(int i = 0; i <= maxGroup; i++) 
	{
		printf("{");
		for(int j = 0; j < size; j++) {
			if (array[j] == i) {
				printf(" %d ", j);
			}
		}
		printf("}");
	}
	printf("\n");
}

void makeset(int *array, int size, int depth)
{
	if (depth == N) {
		printArray(array, size);
		return ;
	}

	// make new group 
	int maxGroup = getMaxGroup(array, size);

	array[depth] = maxGroup+1;
	makeset(array, size, depth+1);
	array[depth] = -1;

	// attach new element to each group
	for(int i = 0; i <= maxGroup; i++) {
		array[depth] = i;
		makeset(array, size, depth+1);
		array[depth] = -1;
	}
}

int main()
{
	int array[MAX_N];

	// init
	for(int i = 0; i < N; i++) {
		array[i] = -1;
	}

	makeset(array, N, 0);
	return 0;
}

어쨌든 풀어서 기분이 좋군 :)

실행결과

인사이트 에서 재미있는 행사를 하길래 도전해보았다.

문제는 다음과 같다.

구체적인 조건에 대한 언급은 없지만 별도의 메모리는 사용하지 않는게 좋겠다는 생각이 들었다. 

그리고 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안된다고 하니 O(n)으로 풀기를 원하는구나.

해결전략은 코드와 같다.

#include <stdio.h>

const int MAX_ELEM = 10;

void rotate(int *array, int s, int t, int k)
{
	int range = (t - s + 1);
	int idx = s, cycle = s;
	int insert, save;

	if (k % range == 0) return ;
	if (k > range) k %= range;

	insert = save = array[s];

	for(int i = 0; i < range; i++) 
	{
		insert = save;

		int nextIdx = idx + k;

		// invalid range check
		if (nextIdx > t) {
			nextIdx = (nextIdx % (t+1)) + s;
		}

		save = array[nextIdx];
		array[nextIdx] = insert;

		idx = nextIdx;

		// avoid cycle 
		if (idx == cycle) {
			idx++; cycle++;
			save = array[idx];
		}
	}
}

int main()
{
	int array[MAX_ELEM];

	// make test set
	for(int i = 1; i <= MAX_ELEM; i++) {
		array[i-1] = i;
	}

	rotate(array, 0, 6, 3);

	// print result
	for(int i = 0; i < MAX_ELEM; i++)
		printf("%d ", array[i]);
	printf("\n");

	return 0;
}

간단히 설명하면, 저장될 곳에 있는 값을 변수에 저장해둬서 덮어쓰더라도 값을 보존시켜가는 방식이다.

그 다음 이동은 지금 덮어씌워진 위치에서 시작한다. 현재 덮어쓴 자리에 있던 값은 저장해두었기 때문에 

다음 위치에 저장할 값을 보존할 수 있다. 마찬가지로 다음 위치에 있는 값을 save에 저장하고, 

기존에 있던 값(insert)으로 덮어쓰면 된다. 

이 과정을 범위만큼 반복하면 별도 메모리 필요없이 풀 수 있다.