'Programming/Algorithms'에 해당되는 글 4건

  1. 2016.04.09 문자열 입력 한자리씩 자르기 (2)
  2. 2015.12.12 [S/W] 간단한 큐(Queue)의 구현
  3. 2015.12.06 [BackTracking] 체스 여왕말 놓기 (N-Queen Problem)
  4. 2015.06.04 Quick Sort (퀵정렬)
2016.04.09 00:14


입력값이 12345 와같은 값으로 들어올때 int 배열의 하나의 공간에 각 한자리 숫자 값을 입력 받는 방법이다.
#include <stdio.h>

int main() {
	char str[50];
	int val[10];

	scanf("%s", &str);
	for (int i = 0; str[i] != '\0'; i++){
		val[i] = str[i] - '0';
		printf("%d ", val[i]);
	}
	return 0;
}
input 값이 12345 인 경우 char str 배열에 들어가는 입력 값은 str[0] 부터 str[4] 까지 차례로 1,2,3,4,5 가 되며 코드 수행시 아래와 같이 출력 된다. 1 2 3 4 5 끝.
신고


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

티스토리 툴바