문제 : 사전순으로 단어를 생성하여 N 번째 올 단어를 찾아라  

 


● 특정 문자열이 주어지고 이 문자열 안에 포함된 단어들을 사전순으로 정렬하라. 그리고 주어진 N 번째 오는 단어가 무엇인지 구하라.

단, 문자열의 최대 길이는 1,000 이고, 모두 소문자 알파벳으로만 되어 있다.

중복되는 단어는 한 단어로 생각한다. 

시간제한이 있다. (빠를 수록 점수가 높다, 1초가 넘으면 실패)


● 사전순이란 것은 알파벳 a ~ z 까지 단어를 정렬하는 것을 의미한다. 


● 예를 들어, melon 이란 문자열이 주어졌을 때, 7번째 오는 단어를 구하라. 

melon 안에 포함된 단어를 사전순으로 정렬하면 다음과 같다. 

1 : e

2 : el

3 : elo

4 : elon

5 : l

6 : lo

7 : lon

8 : m

9 : me

10 : mel

11 : melo

12 : melon

13 : n

14 : o

15 : on


즉, 답은 lon 이 된다. 



 

 일반적인 풀이  

 

● 풀이방법 1 : 위 문제와 같이 알파벳 a부터 문자열 안에 단어를 찾고, 그 뒤로 한글자씩 붙여서 단어를 만들어 나간다.

    

○ 문제점 :  주어진 문자열이 최대 1,000으로 길기 때문에 a가 몇번이고 반복될 수 있다. 예를 들어, a 부터 시작할 경우, 문자열 내의 모든 a 의 위치들을 기록하고, 그 뒤에 오는 단어들을 비교해서 순서를 만들어 나가야 한다. a가 세 번 반복된 경우, 각각의 단어의 뒷글자를 확인해서 순서를 정해야 한다. 위 문제의 예제와 같은 경우는 e가 한 번만 나오지만, e가 계속 반복되는 경우, 또 비슷한 알파벳이 많아지는 경우 문제가 복잡해진다. 


● 풀이방법 2 : 문자열의 첫글자부터 문자열을 만들어 나가면서 이 문자열을 이진 트리 형태로 저장하여 빠르게 정렬한다. 이를 통해 n 번째 아이템을 빨리 찾을 수 있다. 풀이방법 1의 반복적인 검색을 생략할 수 있다.

○ 문제점 : 모든 문자열을 다 만들어보아야 해서 메모리 문제가 있을 수 있다. C++이나 Java로 문제를 푸는 경우는 메모리 이슈를 피할 수 있지만 <STDIO.H> 만 허용된 C언어에서는 어려움이 있다. 트릭을 통해 malloc과 유사하게 푼다 하여도 속도 이슈가 발생할 수 있다. 실제로 C++로 이 문제를 푼 경우 제한 시간에 걸렸다. 



   답이 되는 풀이  
 

● 생각의 전환이 필요하다. 문자열로부터 시작하는 것이 아니라 사전 으로 부터 시작한다. 즉, a가 있는지 검색하고 있으면 다시 aa가 있는지 검색한다. 이 때, 문자열 전체를 보는 것이 아니라 a를 찾은 위치에서 그 바로 뒤에 문자와만 비교하면 된다. a를 찾은 위치의 인덱스를 활용한다. 


● 예를 들어, 주어진 문자열이 kdaabdgga 일 때, 

1) 우선 a 를 찾는다. 인덱스가 2에 a가 있음을 발견한다. 

2) 인덱스 2부터 aa가 있는지 확인한다. 인덱스 2에 aa가 있다.

3) 인덱스 2부터 aaa가 있는지 확인한다. 인덱스 2에는  aaa는 없다

3-1) 문자열 전체에서 aaa가 있는지 확인한다. aaa는 없다. 

4) 인덱스 2부터 aab가 있는지 확인한다. aab는 있다. 

5) 인덱스 2부터 aaba가 있는지 확인한다. 인덱스 2에는 aaba가 없다. 

5-1) 문자열 전체에서 aaba가 있는지 확인한다. aaba가 없다. 

6) aabc, aabd 등을 동일하게 확인한다. 


● 이 방식은 풀이방법 1과 비교할 때, 검색 횟수가 현저하게 줄어든다. 문자열이 랜덤하게 만들어진다는 가정하에 a는 여러번 나오겠지만, aa는 그 숫자가 적어질 것이고, aaa는 훨씬 적을 것이기 때문이다. 



   최상의 풀이  
 

● 답이 되는 풀이도 속도 문제는 있다. aaa가 있는지 확인을 첫번째 a의 인덱스 뒤로는 다 해야 하기 때문이다. 즉, 예를 들어, 주어진 문자열이 aac로 시가된다면, aab 가 있는지 aad가 있는지 문자열 전체를 검사하는 작업을 계속 반복하게 된다. 


● 이 검색 시간을 줄이기 위해서 각 알파벳에 대한 해시를 만들어 놓으면 검색 시간을 대폭 단축시킬 수 있다. 헤시 인덱스를 한단어로 만들어도 되고 두 단어로 만들어도 된다. 두 단어 이상으로 만들면 오히려 효율이 떨어질 것으로 예상된다. 주어진 문자열이 일정길이 이상일 때만 헤시 테이블을 만드는 작업을 수행하는 식으로 프로그램을 완성하면 효율적인 검색이 가능하다. 


● 헤시테이블은 간단한 이중배열로 만들 수 있다. int hash[26][10] 정도로 만들어서, 각각의 알파벳의 10번째 나오는데까지 위치만 미리 기억해놔도 문제가 쉬워진다. 워스트케이시를 대응하기 위해서는 int hash[26][1000] 이 되어야 하는데 이는 메모리 낭비가 심하다.  또는 int hash2[26*26][10] 으로 만들수도 있는데 - (aa ~ zz) 이 경우 해시를 만드는데는 시간이 더 걸리겠지만, 검색 속도는 월등히 빨라질 수 있다. 



   예제 코드  
 

● 추후 업데이트할 예정이다.








'Exercise & Quizz > C' 카테고리의 다른 글

사전 순으로 단어 정렬하기  (0) 2014.07.19
빙고 게임 - 연속되는 숫자 찾기  (0) 2012.06.11
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절

문제 : 0~9까지의 정수가 10x10 으로 랜덤하게 배열되어 있다. 가로, 세로, 대각선으로 연속되는 숫자의 갯수를 찾아서, 가장 많이 연속되는 숫자를 출력하라.

 

  흔히 "빙고" 게임으로 불리는, 랜덤하게 배열된 숫자에서 연속된 숫자를 체크하는 문제이다. 가로, 세로 외에 대각선이 두 방향이 있다는 점을 주의할 것. 


  c의 이중배열은 배열은 실제로 손으로 숫자를 나열한 경우와 x, y 좌표가 반대이다. 이 부분은 직접 손으로 해보고 신중하게 검토해 볼 것. 아주 잘 헛갈리는 문제이다. 


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

#define MAX_NUMBER 10
#define SIZE 10
int test[SIZE][SIZE];
int answerList[MAX_NUMBER];

int getAnswer(int game[SIZE][SIZE], int maxNumber);
int checkTopDown(int game[SIZE][SIZE], int px, int py, int maxNumber);
int checkLeftRight(int game[SIZE][SIZE], int px, int py, int maxNumber);
int checkLeftTopRightDown(int game[SIZE][SIZE], int px, int py, int maxNumber);
int checkRightTopLeftDown(int game[SIZE][SIZE], int px, int py, int maxNumber);

int main(void) 
{
	int i,j;

	/* Init game */
	srand ( time(NULL) );

	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{
			test[i][j] = rand() % MAX_NUMBER;
		}
	}

	/* print test */
	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{
			printf("%d", test[i][j]);
		}
		printf("\n");
	}
	printf("\n");
				
	/* init answerList */
	for (i = 0; i< MAX_NUMBER; i++)
	{
		answerList[i] = 0;
	}

	printf ("Longest Number is %d.", getAnswer(test,MAX_NUMBER));

	return 0;	
}

int getAnswer(int game[SIZE][SIZE], int maxNumber)
{
	int i, j;
	int biggestNumber = -1;
	int longestArray = -1;

	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{
			checkTopDown(game, i, j, maxNumber);
			checkLeftRight(game, i, j, maxNumber);
			checkLeftTopRightDown(game, i, j, maxNumber);
			checkRightTopLeftDown(game, i, j, maxNumber);
		}
	}

	/* Return biggest number */
	for (i = 0; i < MAX_NUMBER; i++)
	{
		if (longestArray <= answerList[i])
		{
			biggestNumber = i;
			longestArray = answerList[i];
		}
	}

	return biggestNumber;
}

int checkTopDown(int game[SIZE][SIZE], int px, int py, int maxNumber)
{
	int i;
	int result = 1;

	if ((py -1 >= 0) &&  (game[py][px] == game[py-1][px]))
		return 0;

	for (i = py; i < SIZE - 1; i++) 
	{
		if (game[i][px] == game[i+1][px])
		{
			result++;
		}
		else
		{
			break;
		}
	}

	if (answerList[game[py][px]] < result)
	{
		answerList[game[py][px]] = result;
	}

	return result;
}

int checkLeftRight(int game[SIZE][SIZE], int px, int py, int maxNumber)
{
	int i;
	int result = 1;

	if ((px -1 >= 0) && (game[py][px] == game[py][px-1]))
		return 0;

	for (i = px; i < SIZE - 1; i++) 
	{
		if (game[py][i] == game[py][i+1])
		{
			result++;
		}
		else
		{
			break;
		}
	}

	if (answerList[game[py][px]] < result)
	{
		answerList[game[py][px]] = result;
	}

	return result;
}

int checkLeftTopRightDown(int game[SIZE][SIZE], int px, int py, int maxNumber)
{
	int i;
	int j = 0;
	int result = 1;

	if ((px -1 >= 0) && (py -1 >= 0) && (game[py][px] == game[py-1][px-1]))
		return 0;

	for (i = px; i < SIZE - 1; i++) 
	{
		if (game[py+j][px+j] == game[py+j+1][px+j+1])
		{
			result++;
			j++;
		}
		else
		{
			break;
		}
	}

	if (answerList[game[py][px]] < result)
	{
		answerList[game[py][px]] = result;
	}

	return result;
}

int checkRightTopLeftDown(int game[SIZE][SIZE], int px, int py, int maxNumber)
{
	int i;
	int j = 0;
	int result = 1;

	if ((px + 1 < SIZE-1) && (py -1 >= 0) && (game[py][px] == game[py-1][px+1]))
		return 0;

	for (i = px; i < SIZE ; i++) 
	{
		if (px - i < 0)
		{
			break;
		}
		else if ((px-j-1 > 0) && (py+j+1 < SIZE) && (game[py+j][px-j] == game[py+j+1][px-j-1]))
		{
			result++;
			j++;
		}
		else
		{
			break;
		}
	}

	if (answerList[game[py][px]] < result)
	{
		answerList[game[py][px]] = result;
	}

	return result;
}

#define을 이용하여 사이즈와 숫자 범위를 조정할 수 있도록 했고, 랜덤하게 만들어진 문제를 출력해서 쉽게 비교해볼 수 있도록 했다. 다시 말하지만, x, y 좌표과 실제로 출력되는 x, y는 x,y 순서쌍이 바뀌어 있음을 유의할 것.


'Exercise & Quizz > C' 카테고리의 다른 글

사전 순으로 단어 정렬하기  (0) 2014.07.19
빙고 게임 - 연속되는 숫자 찾기  (0) 2012.06.11
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절

x,y의 좌표가 주어졌을때

각도 구하는 코딩 가르쳐주세요!!

x, y 좌표를 이용해서 좌표축에 만들어지는 삼각함수를 이용하면 됩니다.

각도를 A 라고 하면, tan(A)  = y/x 가 되지요.  반대로, x, y 좌표를 이용해서 각도 A를 구하는 것은 역함수 아크탄젠트를 이용하면 됩니다. 자세한 수학적 이론은 정석의 삼각함수를 찾아보세요.

C 언어 라이브러리 중에 math.h 가 있습니다. 삼각함수를 제공합니다.

함수 설명은 http://www.cplusplus.com/reference/clibrary/cmath/atan2.html 여기를 참조하시고요, 예제코드는 아래 있습니다.

Example

/* atan2 example */
#include
#include

#define PI 3.14159265

int main ()
{
double x, y, result;
x = -10.0;
y = 10.0;
result = atan2 (y,x) * 180 / PI;
printf ("The arc tangent for (x=%lf, y=%lf) is %lf degrees\n", x, y, result );
return 0;
}

Output:


The arc tangent for (x=-10.000000, y=10.000000) is 135.000000 degrees.
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절

안녕하세요. 컴공과 1학년 블로그 과대표 로엔그린 입니다.

네이버에 본래 블로그를 운영하고 있었으나, 좀더 전문적인 내용으로 바꾸기 위하여 컴퓨터 관련된 내용을 새로운 블로그로 독립하여 운영합니다. 기존 블로그는 본의 아니게 지나치게 정치색(?)을 띠게 되어버렸습니다.

과대표 소개를 간단하게 드리면, 최초로 베이직으로 프로그램을 짠지 한 16년 정도 되었습니다. 컴공과에 입학하여 C언어를 배운지 10년 정도 되었습니다. 그리고, 지금도 프로그램을 만드는 것을 업으로 하고 있습니다.

어떤 개그맨은 "16년 정도 하면 달인이다" 라고 주장합니다만, 아직 짠 프로그램의 수가 5만 6천개가 안되서인지... 아직 달인이라고 부르기는 부끄러울 정도의 수준입니다.

프로가된 지금 돌아보면 항상, "그 때 배울 때 이런건 왜 안가르쳐 줬을까?" 란 아쉬움이 남습니다. 이 고민을. 후배들에게는 그 고민을 물려주고 싶지 않아서 새로운 스타일의 C/C++ 스터디를 시작해 보려 합니다.

좀더 실용적이고, 실질적이며, 생각할 거리를 던지는 그런 C언어 공부를 시작해 봅시다.

C / C++ 관련 질문이 있으시다면 방명록을 이용해 주세요.

PS. 이 블로그의 Post 들이 유익하셨다면, 올블로그 link의 클릭을 부탁드립니다.

'Studies' 카테고리의 다른 글

게시판별 용도  (0) 2008.08.10
[개강공지] Computer Engineering 1st year. Blog just opend and Welcome!  (0) 2008.08.08
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절


BLOG main image
일상, 프로그래밍, IT 그리고 직장생활, Dive, 여행 by 지그프리드

카테고리

Class List (402)
Studies (30)
Exercise & Quizz (10)
Term Project (0)
ECIM list (Help!) (10)
Issues & News (0)
Gossip about IT & Job (22)
Tools (2)
Think about the Justice (23)
Book Review (170)
조엘 온 소프트웨어(번역) (28)
Diary (87)
Vacations (9)
Clash of clans 클래시 오브.. (11)

글 보관함

달력

«   2020/08   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
Total : 321,747
Today : 4 Yesterday : 10