2017.07.05 01:36


문제12 암호깨기 (Crypt Kicker)


A common but insecure method of encrypting text is to permute the letters of the alphabet. In other words, each letter of the alphabet is consistently replaced in the text by some other letter. To ensure that the encryption is reversible, no two letters are replaced by the same letter.

Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.

Input

The input consists of a line containing an integer n, followed by n lowercase words, one per line, in alphabetical order. These nwords compose the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above.

There are no more than 1,000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.

Output

Decrypt each line and print it to standard output. If there are multiple solutions, any one will do. If there is no solution, replace every letter of the alphabet by an asterisk.

Sample Input

6
and
dick
jane
puff
spot
yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

Sample Output

dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******


# Source (My Solution)

ddddddddddddddddddd
저작자 표시
신고


Posted by injunech
2017.07.05 01:21


문제1 3n+1문제

출처 : http://www.programming-challenges.com/


Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.

For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.

Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

Output

For each pair of input integers i and j, output ij in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input.

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174




# Source (My Solution)

#include 

//#define DBG

void main(void) {
	int a;
	int b;

	int tmp;
	int i;
	int x;
	int loop_count;
	int max_count =0;

	scanf("%d", &a);
	scanf("%d", &b);
	
	// If A is Biger than B,  Swap A and B
	if (a > b) {
		tmp = a;
		a = b;
		b = tmp;
	}
	
	for (i = a; i <= b; i++) {
		// Start, Init
		x = i;
		loop_count = 1;
#ifdef DBG
		printf("[%d] =============== \n", i);
#endif

		// Loop
		while (x != 1) {
			if ((x & 1) == 0) {	// even
#ifdef DBG
				printf("[%d] is EVEN\n", x);
#endif
				x = x / 2;
			}
			else {	// odd
#ifdef DBG
				printf("[%d] is ODD\n", x);
#endif
				x = (x * 3) + 1;
			}
			loop_count++;
		}

		if (max_count < loop_count)
			max_count = loop_count;

	}

	printf("%d %d %d", a,b, max_count);
	
}

 


저작자 표시
신고


Posted by injunech
2015.12.12 10:03


간단한 큐(Queue)의 구현


순환 큐가 가장 좋은 것으로 알고 있지만 

빠른 알고리즘의 구현을 할 경우에는 전체 큐의 범위를 넉넉하게 잡고 아래와 같은 방식으로 구현하였다.

큐는 BFS 알고리즘을 쓸때 주로 이용된다.


여기서 사용된 Front 와 Rear 의 용도는 다음과 같다.

값의 존재 기준으로 보면
Front 는 값이 존재하는 제일 앞에서 index 값이 -1 만큼인 값
Rear 는 값이 존재하는 제일 마지막에서 index 값이 +1 만큼인 값

값을 넣어야 하는 기준으로 보면
값을 꺼낼 때 Front 의 현재 index 에서 +1의 위치 값을 꺼내온다.
값을 넣을 때 Rear 의 index 위치에 값을 넣는다.

Queue에 Push 할때는 Rear 가 가리키는 Index 에 넣고 Rear 의 값을 +1 한다.
Queue에 있는 값을 Pop으로 꺼낼때는 Front 의 +1한 다음 Index 값이 Rear 와 같은 경우 Null 을 알려주고 그렇지 않은 경우 Front 값을 +1 하고 해당 위치에 값을 Return 한다.


#include <stdio.h>

#define SIZE 100

struct vertex{
	int x;
	int y;
}typedef vertext;

vertext queue[SIZE];
int front=-1;
int rear=0;

void push_rear(vertext a){
	queue[rear++] = a;
}

vertext pop_rear(){
	if (rear == front+1){
		// QUEUE NULL
		printf("QUEUE is NULL\n");
	}
	else{
		return queue[++front];
	}
}

void printQueue(){
	int i=front+1;
	printf("QUEUE : ");
	if (i < rear){
		do{
			printf("(%d, %d) ", queue[i].x, queue[i].y);
			i++;
		} while (i< rear);
	}
	printf("\n");

}

int main(){
	int i=0;
	int T=0;
	vertext value;
	int b,c,d,e,f,g;

	int a[10];
	
	while (1){
		printf("----------------\n");
		printf("1. Push 2.Pop\n");
		scanf("%d", &T);

		if (T == 1){
			scanf("%d %d", &value.x, &value.y);
			printf("%d %d", value.x, value.y);
			push_rear(value);

		}
		else if (T == 2){
			pop_rear();
		}

		printf("----------------\n");
		printQueue();
	}

	return 0;
}
 



신고


Posted by injunech
2015.12.06 19:16


[BackTracking] 체스 여왕말 놓기 (N-Queen Problem)



되추적(Backtracking) 방법을 얘기 할 때 가장 많이 거론 되는 듯한 N-여왕말(N-Queen) 문제이다. 어떤 문제인가하면 서양 장기(Chess:이후 체스)의 여왕말(Queen:이후 퀸)을 서로가 서로의 이동경로가 아닌 위치에 있도록 최대한 많은 퀸을 체스판 위에 놓는 문제이다.


 원래 체스판은 8ⅹ8이지만 간단히 4ⅹ4일 경우에 좌측의 결과와 같이 되는 경우를 찾는 것이 바로 N-Queen 문제 이다.

 4ⅹ4일 경우에는 좌측과 같은 2가지의 경우만 나오지만 체스판이 커지면 커질수록 다양한 경우의 수가 나온다. 우선 정해진 것은 NⅹN의 체스판에 올라갈 수 있는 퀸의 최대 갯수는 언제나 N이 된다는 점이다.


 그렇다면 어째서 이것이 되추적(Backtracking) 방법이 되느냐 하는 것은

① 첫번째 퀸이 (1, 1) 위치에 오게 될 경우

② 두번째 퀸은 (2, 3) 과 (2, 4) 위치에 올 수 있다. 우선 (2, 3) 위치에 퀸을 놓는다면

③ 세번째 퀸을 놓을 수 있는 자리는 없어진다. 그러면 다시 ②로 돌아가서 두번째 퀸을 (2, 4) 위치에 놓게 되면

④ 세번째 퀸을 (3, 2) 위치에 놓을 수 있지만 이렇게 되면 네번째 퀸을 놓을 수가 없어진다. 그렇게 되면 이번엔 다시 ①로 돌아가서 첫번째 퀸을 (1, 2)에 놓고 다시 시작한다.


 위의 과정과 같이 결과값을 찾아가다가 그 방법이 아니라는 것을 알았을 때 이전 단계로 돌아가는 것이 바로 되추적 방법이다.


 N-Queen의 문제의 경우 참고 자료에 있는 책을 본다면 좀 더 쉽게 알 수 있을 것이다. 언제나와 같이 나는 참고자료에 있는 'Foundations of Algorithms.....' 책을 참고로 해서 프로그램을 작성하였다.

 N값을 입력 받아서 결과를 보여주는 N-여왕말 문제 알고리즘


참고자료 

알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역

누워서 읽는 알고리즘 - 임백준 저



#include <stdio.h>
#include <malloc.h>
#include <math.h>

void queens(int i, int n, int col[]);   // n개 여왕말 알고리즘
void printqueen(int n, int col[]);      // n개 여왕말의 위치 출력
int promising(int i, int col[]);    // 유망한지 검사하는 함수

int main()
{
	int i;
	int n;
	int* col;

	printf("How many Columns or Rows?\n> ");
	scanf("%d", &n);
	getchar();

	// 여왕말이 해당행의 몇번째 열에 있는지 저장
	col = (int*)malloc(sizeof(int)*n);

	// 뿌리 노드(0)부터 탐색을 시작
	queens(0, n, col);

	free(col);

	return 0;
}

void queens(int i, int n, int col[])
{
	int j;

	if (promising(i, col)) // 유망한가?
	if (i == n) // n개의 여왕말 위치를 찾았나?
		printqueen(n, col); // 여왕말 위치 출력
	else
	for (j = 1; j <= n; j++) {    // (i+1)번째 행에 있는 여왕말을
		col[i + 1] = j;           // n개의 열에 놓을 수 있는지 각각
		queens(i + 1, n, col);    // 검사한다.
	}
}

void printqueen(int n, int col[])   // 보기 편하게 결과값을 출력
{
	int j, k;
	printf("    |");           // 상단 열의 갯수 출력 부분
	for (j = 1; j <= n; j++)
		printf("%3d |", j);
	printf("\n");

	for (j = 0; j <= n; j++)    // 행을 나누는 선 출력
		printf("----+");
	printf("\n");

	for (j = 1; j <= n; j++) {
		printf("%3d |", j);   // 행의 번호
		for (k = 1; k < col[j]; k++) {
			if (((k + j) % 2))
				printf("▩▩|");    // 여왕말이 없는 칸
			else
				printf("    |");    // 여왕말이 없는 칸
		}
		printf("QUEE|");      // 여왕말
		for (k = col[j]; k < n; k++){
			if (!((k + j) % 2))
				printf("▩▩|");    // 여왕말이 없는 칸
			else
				printf("    |");    // 여왕말이 없는 칸
		}
		printf("\n");

		for (k = 0; k <= n; k++)   // 행을 나누는 선 출력
			printf("----+");
		printf("\n");
	}
	printf("\n");

	printf("Press ENTER to continue");
	getchar();  // 결과 값이 많으므로 하나의 결과값마다 멈추도록
}

int promising(int i, int col[]) // 유망한지 판단하는 함수
{
	int k;
	int bSwitch;

	k = 1;
	bSwitch = 1;
	while (k < i && bSwitch) {
		/* col[i] == col[k] 는 같은 열에 있는지 판별한다
		* abs(col[i] - col[k]) == i - k의 경우는
		* 2개의 여왕말간의  행의 차와 열의 차의 절대값이 같으면
		* 같은 대각선상에 있다는 의미이다. */
		if (col[i] == col[k] || abs(col[i] - col[k]) == i - k)
			bSwitch = 0;
		k++;
	}
	return bSwitch;
}



출처 : http://egloos.zum.com/sakuragis/v/3468837 

신고


Posted by injunech
2015.06.04 17:38


Quick Sort(퀵정렬)

 

알고리즘

 

연속적인 분할에 의한 정렬처음 하나의 축을 정해서 이 축의 값보다 작은 값은 왼쪽에

큰 값은 오른쪽으로 위치시킨다왼쪽과 오른쪽의 수 들은 다시 각각의 축으로 나누어져

축값이 1이 될 때까지 정렬한다

 

특징

 

안정성 없음

 

O(NlogN) : 최선의 경우 log2N (축값이 정확히 가운데를 가질 경우)

O(N^2) : 최악의 경우

 

가장 많이 사용되는 정렬법으로 1960 C.A.R. Hoare에 의해 고안되었다.

 

Code(코드)

 

재귀함수를 사용한다.

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define SIZE 20
#define SWAP(x,y,t) ( (t)=(x), (x)=(y), (y)=(t) )
 
void QuickSort(int left, int right);
 
int array[SIZE];
 
int main(void){
int i;
srand((unsigned int)time(NULL));
 
for ( i = 0; i < SIZE; i++ )
array[i] = rand() % (SIZE*10) + 1;
 
printf("array for sorting : \n");
 
for ( i = 0; i < SIZE; i++ )
printf("%4d", array[i]);
 
 
printf("\nProcessing : \n");
 
QuickSort(-1, SIZE-1);
 
printf("Soredted array : \n");
 
for ( i = 0; i < SIZE; i++ )
printf("%4d", array[i]);
 
printf("\n");
 
return 0;
}
 
void QuickSort(int left, int right){
int m, p, t;
int i, j;
 
for ( i = 0; i < SIZE; i++ )
printf("%4d", array[i]);
 
printf("\n");
 
if ( left < right ){
p = array[right];
for(i=left-1, j=right; ; ){
while ( array[++i] < p );
while ( array[--j] > p );
 
if ( i > j )
break;
 
SWAP(array[i], array[j], t);
}
 
array[right] = array[i];
array[i] = p;
 
QuickSort(left, j);
QuickSort(i+1, right);
}
}


신고


Posted by injunech

티스토리 툴바