이제 마지막 문제란다. -_-; 

어려운 문제가 나올까봐 긴장하긴 했지만 마지막이라니 왠지 아쉽네잉.


한 번 풀었다가 내가 문제를 잘못 해석한거라서 이전것은 말아먹었다 ㅜㅜ 


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



문제


사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.

[실행 예]

input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

[사전 데이터]

네 글자 단어 - word4

다섯 글자 단어 - word5

 

[심화 문제 - 풀지 않아도 됩니다]

심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.

심화문제 2: 가장 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.


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


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


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


1. 처음 element set에는 출발 단어 하나만 들어있다. 사전을 뒤적거리면서 distance가 1인 단어들을 모두 표시힌다.


2. 1번 과정에서 표시한 단어들과 distance가 1인 단어들도 모두 표시한다.


3. 더이상 새로운 단어가 추가되지 않을때까지 위 과정을 반복한다. 도중에 정답을 찾으면 바로 return.


한마디로 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;
}

trace를 위해서 elem이라는 배열에 어떤 단어로부터 왔는지 해당 index를 저장해두었다. (trace가 더 빡세...)

사전 파일을 보니 7천줄이 안되는 것같아 일단 메모리에 넣어두고 처리하기로 했다.

다음은 시험결과


shell> ./newdic word4.in

damp like

damp -> gamp -> gimp -> limp -> lime -> like


shell> ./newdic word4.in

acne mind

acne -> acre -> agre -> egre -> eire -> mire -> mine -> mind


shell> ./newdic word5.in

worse tasty

worse -> corse -> carse -> carte -> caste -> haste -> hasty -> tasty


shell> ./newdic word5.in

limit zorna

IMPOSSIBLE


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;
}

다음은 시험결과


shell> ./newdic word4.in

damp like

damp -> lamp -> limp -> lime -> like


shell> ./newdic word4.in

acne mind

acne -> aune -> dune -> dine -> mine -> mind


shell> ./newdic word5.in

worse tasty

worse -> torse -> tarse -> tasse -> taste -> tasty


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



Posted by DevMoon

댓글을 달아 주세요

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


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


2012! = 501 8

10000! = 2499 8


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





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


자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예]

input n: 15
output: 3 8

[설명]

15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

* 조건 *

  1. n의 범위는 1 이상, 10000 이하입니다.
  2. 테스트 입력은 다음과 같습니다.
    20! = 2432902008176640000
    30! = 265252859812191058636308480000000
    40! = 815915283247897734345611269596115894272000000000
    50! = 30414093201713378043612608166064768844377641568960512000000000000
    100! = 93326215443944152681699238856266700490715968264381621468592963
    8952175999932299156089414639761565182862536979208272237582511852
    10916864000000000000000000000000
  3. 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
  4.  정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
  5. (심화 문제) 연속된 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;
}


Posted by DevMoon

댓글을 달아 주세요

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


아래 책에 있는 문제라네.




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


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


1. 이전에 만들어진 집합에 현재 값을 포함시켜 새로운 집합으로 만든다. {} 쌍으로 된 것을 하나의 집합이라 한다.


2. 이전 집합과 별도로 독립적인 집합을 만든다. 그리고 그 결과를 취합한다.


ex) {0}에 {1}을 넣어야 하는 경우


기존 집합에 넣기: {0, 1}

독립적 집합 만들어 합치기: {0}, {1}


위에다 {2}를 넣으면?


기존 집합에 넣기: {0, 1, 2}, {0, 2}, {1, 2}

독립적 집합 만들어 합치기: {0, 1}{2}, {0}{1}{2}


...


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


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;
}


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


실행결과


{ 0 }{ 1 }{ 2 }{ 3 }

{ 0  3 }{ 1 }{ 2 }

{ 0 }{ 1  3 }{ 2 }

{ 0 }{ 1 }{ 2  3 }

{ 0  2 }{ 1 }{ 3 }

{ 0  2  3 }{ 1 }

{ 0  2 }{ 1  3 }

{ 0 }{ 1  2 }{ 3 }

{ 0  3 }{ 1  2 }

{ 0 }{ 1  2  3 }

{ 0  1 }{ 2 }{ 3 }

{ 0  1  3 }{ 2 }

{ 0  1 }{ 2  3 }

{ 0  1  2 }{ 3 }

{ 0  1  2  3 }


Posted by DevMoon

댓글을 달아 주세요

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


문제는 다음과 같다.


배열 arr[]과 위치 s, t가 있을 때,
arr[s], arr[s+1], … , arr[t-1]을 오른쪽으로 한 칸씩 이동하고,
arr[t]는 arr[s]로 복사하는 것을 ’1만큼 오른쪽으로 회전시켰다’고 한다.

예를 들어 길이가 8인 배열에서 s=2, t=6이면 다음 그림처럼 바뀐다.

길이가 n인 배열의 위치는 0, 1, 2, … , n-1이다.

문제 :
k를 인자로 받아서 k만큼 오른쪽으로 회전시키는 함수를 작성하라.
단, 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안 된다.

조건 1 : 작성하는 언어에는 제한이 없습니다.
조건 2 : 답안으로 작성하신 글 제목에는 ‘문제로 풀어보는 알고리즘 0.3 생각해보기 풀이’라는 문장이 들어가야 합니다. (저희 블로그에도 트랙백을 걸어주세요.)

(주의: 이 코딩 인터뷰는 인사이트 입사와는 무관합니다. ㅡㅁㅡ /)


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


그리고 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)으로 덮어쓰면 된다. 


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


Posted by DevMoon

댓글을 달아 주세요

  1. DevMoon 2012.08.30 03:07 신고  댓글주소  수정/삭제  댓글쓰기

    코드에 순환하는 경우를 고려하지 못해서 보완... avoid cycle 이 부분..

  2. 망고스파게티 2012.09.12 23:50 신고  댓글주소  수정/삭제  댓글쓰기

    save한 인덱스에서 다시 시작해버리는 거군요. 모든 경우에 다 일정하게 이동하기 때문에 누락되는 인덱스도 없고, 이 방법이 딱 알맞네요! 최고입니다!!

#include <stdio.h>

int main()
{
    printf("hello world\n");
    return 0;
}
Posted by DevMoon

댓글을 달아 주세요