카테고리

CamelACT (9)
UVa (3)
Basics (4)
Information (2)
Statistics Graph

'Basics'에 해당되는 글 4건

  1. 2013.04.30 [Basics]라벨링
  2. 2012.12.05 [Basics]구조체를 이용한 희소행렬의 덧셈
  3. 2012.12.05 [Basics]구조체를 이용한 다항식의 덧셈
  4. 2012.12.02 [Basics]모든 경우의 수를 알아내자. (1)

 영상처리에서 처음 접하게 된 라벨링이라는 알고리즘이 있다. 대표적으로 쌀알 같은 물체의 개수를 세는 것을 목적으로 만든 알고리즘이다. 이미지는 배열로 나타낼 수 있고 100*100 정도의 배열에서 배경은 0이고 물체는 1이다. 쌀알을 나타내는 1은 덩어리를 이루며 가로, 세로 +-1에 해당(대각선 포함)하는 영역까지 같은 물체로 간주한다. 이 때 배경에서 쌀알의 개수를 세어 볼 수 있는 알고리즘이 바로 라벨링이다.

 첫 번째로 물체에 번호를 매겨야 한다. 이중 for문을 통해 이미지의 왼쪽 상단(0,0)부터 오른쪽 하단(99,99)까지 한 픽셀씩 처리할 것이다만약 물체에 해당하는 픽셀이라면 라벨을 매긴다. 1, 2, 3… 를 매기다 보면 최종적으로 물체의 개수가 세어질 것이다. 하지만 한 픽셀의 차이라면 같은 물체로 봐야 한다. 물체에 해당하는 픽셀에서 서, 북서, , 북동 방향의 한 픽셀에 만약 물체가 있다면 같은 물체라는 기록을 해야 한다. 이 때 필요한 것이 라벨테이블이다. 이 테이블은 다른 라벨이지만 같은 물체라는 것을 알려주는 테이블이다. 예를 들어, 현재 픽셀이 물체이고 서쪽에 라벨이 4이고 북동쪽에 라벨이 7이라면 (4, 7)이라고 저장을 해 둔 뒤, 나중에 모든 픽셀 검사를 마치고 모든 라벨 4는 라벨 7로 간주한다는 의미를 두어 이미지 배열의 4를 7로 바꾸어 준다.

 위와 같은 방법을 수행하면 인접한 픽셀은 같은 물체로 인식하게 되고 최종적으로 물체의 개수를 셀 수 있다


// start 13:30 // end 18:30 #include <stdlib.h> #include <stdio.h> #include <windows.h> #define SIZE 50 int run_test(const char ranch[SIZE][SIZE]); void main(void) { static char ranch[SIZE][SIZE]; for(int c = 0; c < 1; c++) { for(int y = 0; y < SIZE; y++) for(int x = 0; x < SIZE; x++) ranch[x][y] = '1'; // 토양 for(int c = 0; c < SIZE * SIZE; c++) ranch[rand() % SIZE][rand() % SIZE] = '0'; // 울타리 printf("%d\n", run_test(ranch)); } } int run_test(const char ranch[SIZE][SIZE]) { for(int y = 0; y < SIZE; y++) { // 문제가 [x][y] 더라도 [y][x]로 바꾸어 풀자 for(int x = 0; x < SIZE; x++) { printf("%3c", ranch[y][x]); } printf("\n"); } printf("----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- \n"); int ranchMap[SIZE][SIZE] = {0}; int label = 1; int labelTable[SIZE * SIZE * 4][2] = {0}; labelTable[0][0] = label; // 현재 labelTable[0][1] = label; // 미래 int tableCount = 1; // 서 북서 북 북동 for(int y = 0; y < SIZE; y++) { for(int x = 0; x < SIZE; x++) { if(ranch[y][x] == '1') { bool c0 = false; bool c1 = false; bool c2 = false; bool c3 = false; // 에러 방지 범위 제한 if(x - 1 >= 0 && ranch[y][x - 1] == '1') { // 서 ranchMap[y][x] = ranchMap[y][x - 1]; // 서 c0 = true; } if(y - 1 >= 0 && x - 1 >= 0 && ranch[y - 1][x - 1] == '1') { // 북서 if(c0) { if(ranchMap[y - 1][x - 1] != ranchMap[y][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x - 1]; // 북서 labelTable[tableCount][1] = ranchMap[y][x - 1]; // 서 tableCount++; } } else { ranchMap[y][x] = ranchMap[y - 1][x - 1]; // 북서 } c1 = true; } if(y - 1 >= 0 && ranch[y - 1][x] == '1') { // 북 if(c0) { if(ranchMap[y - 1][x] != ranchMap[y][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x]; // 북 labelTable[tableCount][1] = ranchMap[y][x - 1]; // 서 tableCount++; } } else if(c1){ if(ranchMap[y - 1][x] != ranchMap[y - 1][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x]; // 북 labelTable[tableCount][1] = ranchMap[y - 1][x - 1]; // 북서 tableCount++; } } else { ranchMap[y][x] = ranchMap[y - 1][x]; // 북 } c2 = true; } if(y - 1 >= 0 && x + 1 < SIZE && ranch[y - 1][x + 1] == '1') { // 북동 if(c0) { if(ranchMap[y - 1][x + 1] != ranchMap[y][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x + 1]; // 북동 labelTable[tableCount][1] = ranchMap[y][x - 1]; // 서 tableCount++; } // printf("%3d %3d, x = %3d y = %3d\n", labelTable[tableCount][0], labelTable[tableCount][1], x, y); } else if(c1){ if(ranchMap[y - 1][x + 1] != ranchMap[y - 1][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x + 1]; // 북동 labelTable[tableCount][1] = ranchMap[y - 1][x - 1]; // 북서 tableCount++; } // printf("%3d %3d, x = %3d y = %3d\n", labelTable[tableCount][0], labelTable[tableCount][1], x, y); } else if(c2){ if(ranchMap[y - 1][x + 1] != ranchMap[y - 1][x]){ labelTable[tableCount][0] = ranchMap[y - 1][x + 1]; // 북동 labelTable[tableCount][1] = ranchMap[y - 1][x]; // 북 tableCount++; } } else { ranchMap[y][x] = ranchMap[y - 1][x + 1]; // 북동 } c3 = true; } if(!(c0 | c1 | c2 | c3)) { // 독립이라면 ranchMap[y][x] = label++; } else { // 독립이 아니라면 } } else { ranchMap[y][x] = 0; } } } // printf("label = %3d\n", label); // for(int L = 0; L < SIZE * SIZE; L++) { // if(!labelTable[L][0]) { // break; // } // printf("%3d %3d\n", labelTable[L][0], labelTable[L][1]); // } // printf("----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- \n"); for(int m = 0; m < SIZE * SIZE; m++) { for(int y = 0; y < SIZE; y++) { for(int x = 0; x < SIZE; x++) { if(ranchMap[y][x] == labelTable[m][0]){ ranchMap[y][x] = labelTable[m][1]; } } } for(int n = 0; n < SIZE * SIZE; n++) { if(labelTable[n][0] == labelTable[m][0] && n != m // 자기 자신마져 바뀌어 버리면 더 이상 비교가 불가능 하다. ) { labelTable[n][0] = labelTable[m][1]; } if(labelTable[n][1] == labelTable[m][0] // && n != m ) { labelTable[n][1] = labelTable[m][1]; } } } // for(int m = 0; m < SIZE * SIZE; m++) { // if(!labelTable[m][0]) { // break; // } // printf("%3d %3d\n", labelTable[m][0], labelTable[m][1]); // } for(int y = 0; y < SIZE; y++) { for(int x = 0; x < SIZE; x++) { if(!ranchMap[y][x]) { // 0 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 255); printf("%3d", ranchMap[y][x]); } else { SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ranchMap[y][x] + 255); printf("%3d", ranchMap[y][x]); } } printf("\n"); } SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 0xb2); int countTable[SIZE * SIZE] = {0, }; int count = 0; for(int y = 0; y < SIZE; y++) { for(int x = 0; x < SIZE; x++) { countTable[ranchMap[y][x]]++; } } for(int m = 1; m < SIZE * SIZE - 1; m++) { if(countTable[m]) count++; } return count; }


Input and Output



신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Basics l 2013.04.30 22:03

 일반적인 행렬의 덧셈은 프로그래밍으로 할 때 모든 행과 열을 검사하여 더해주면 된다. 하지만 매우 큰 행렬에 0의 개수가 대부분을 차지하는 행렬 간의 덧셈에서는 위와 같이 프로그래밍 할 경우 불필요한 시간의 낭비가 초래된다. 따라서 0의 개수가 대부분을 차지하는 행렬을 희소행렬이라 지칭하고 이와 같은 행렬의 덧셈에 대한 새로운 계산 방법을 고안해 보자.

 희소행렬 구조체의 구성은 0이 아닌 값의 행과 열, 값으로 이루어진 element 구조체가 존재하고 SparseMatrix 구조체는 배열로 element 구조체를 갖는다. 그리고 전체 행과 열의 개수와 0이 아닌 값의 개수를 나타내는 변수를 갖는다.

 예를 들어, SparseMatrix m1 = {{{ 1,1,5 },{ 2,2,9 }}, 3,3,2 };의 경우 1행 1열에 5, 2행 2열에 9가 있고 총 행렬의 크기는 3행 3열이고 0이 아닌 값은 2개 있다는 의미이다.

 나머지 알고리즘은 이전 포스트인

[Basics]구조체를 이용한 다항식의 덧셈

과 동일하다.


#include <stdio.h>

#include <stdlib.h>

#define ROWS 3
#define COLS 3

#define MAX_TERMS 10 
typedef struct { 
    int row; 
    int col; 
    int value; 
} element; 

typedef struct SparseMatrix {
	element data[MAX_TERMS];
	int rows;	// 행의 개수
	int cols;	// 열의 개수
	int terms; 	// 0이 아닌 항의 개수
} SparseMatrix;

// 일반 행렬 덧셈 함수
void sparse_matrix_add(int A[ROWS][COLS], 
		int B[ROWS][COLS], int C[ROWS][COLS])  // C=A+B
{	
	int r,c;
	for(r=0;r<ROWS;r++)
		for(c=0;c<COLS;c++)
			C[r][c] = A[r][c] + B[r][c];
}

// 희소 행렬 덧셈 함수
SparseMatrix sparse_matrix_add2(SparseMatrix a, SparseMatrix b)  // C=A+B
{	
	SparseMatrix c;
	int ca=0, cb=0, cc=0;
	// 크기가 같은지를 확인
	if( a.rows != b.rows || a.cols != b.cols ){
		fprintf(stderr,"희소행렬 크기에러\n");
		exit(1);
	}
	c.rows = a.rows;
	c.cols = a.cols;
	c.terms = 0;

	while( ca < a.terms && cb < b.terms ){
		int inda = a.data[ca].row * a.cols + a.data[ca].col;
		int indb = b.data[cb].row * b.cols + b.data[cb].col;
		if( inda < indb) {
			// b 항목이 더 나중에 와야 함
			c.data[cc++] = a.data[ca++];
		}
		else if( inda == indb ){
			// a와 b가 같은 위치
			c.data[cc].row = a.data[ca].row;
			c.data[cc].col = a.data[ca].col;
			c.data[cc++].value = a.data[ca++].value +
					      b.data[cb++].value;
		}
		else 
			c.data[cc++] = b.data[cb++];
		
	}
	// 나머지항들을 옮긴다.
	for(; ca < a.terms; ca++)
		c.data[cc++] = a.data[ca++];
	for(; cb < b.terms; cb++)
		c.data[cc++] = b.data[cb++];
	c.terms = cc;
	return c;
}
// 주함수
main()
{
	SparseMatrix m1 = {	{{ 1,1,5 },{ 2,2,9 }}, 3,3,2 };
	SparseMatrix m2 = {	{{ 0,0,5 },{ 2,2,9 }}, 3,3,2 };
	SparseMatrix m3;

	m3 = sparse_matrix_add2(m1, m2);
}



신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Basics l 2012.12.05 23:05

 차수와 계수를 갖는 구조체를 만든다. 이를 이용하여 다항식의 덧셈을 수행할 것이다. polynomal 구조체 두 개를 만들고 덧셈 함수에 넣는다. 각 구조체의 차수를 미리 변수에 저장한다. 두 구조체의 차수를 비교하여 같은 경우와 다른 경우로 나눈다. 다른 경우는 차수가 큰 구조체의 계수만 더하고 같은 경우는 두 구조체의 계수를 더하여 새로운 구조체를 구성한다. 종료조건은 덧셈할 두 개의 구조체가 모두 검사가 끝나야 하므로 둘 중 하나가 아닌 둘 다 종료 될 때까지 위 작업을 반복한다.


#include <stdio.h>

#define MAX(a,b) (((a)>(b))?(a):(b))
#define MAX_DEGREE 101
typedef struct { 			// 다항식 구조체 타입 선언
	int degree;			// 다항식의 차수
	float coef[MAX_DEGREE];	// 다항식의 계수
} polynomial;
// 
polynomial poly_add1(polynomial A, polynomial B)  // C=A+B
{	
	polynomial C;				// 결과 다항식
	int Apos=0, Bpos=0, Cpos=0;	// 배열 인덱스 변수
	int degree_a=A.degree;
	int degree_b=B.degree;
	C.degree = MAX(A.degree, B.degree); // 결과 다항식 차수

	while( Apos<=A.degree && Bpos<=B.degree ){
		if( degree_a > degree_b ){
		  C.coef[Cpos++]= A.coef[Apos++];
		  degree_a--;
		}
		else if( degree_a == degree_b ){
		  C.coef[Cpos++]=A.coef[Apos++]+B.coef[Bpos++];
		  degree_a--; degree_b--;
		}
		else {
		  C.coef[Cpos++]= B.coef[Bpos++];
  		  degree_b--;
		}
	}
	return C;
}

void print_poly(polynomial A)
{
	int temp = A.degree;
	int i;	

	printf("degree : %d\n", temp);
	for(i = 0 ; i <= A.degree ; i++){
		printf("%d coef : %.f\n", i, A.coef[i]);
	}
}

// 주함수
void main()
{
	polynomial a = { 5, {3, 6, 0, 0, 0, 10} };
	polynomial b = { 4,    {7, 0, 5, 0, 1} };

	polynomial c;
	c = poly_add1(a,b);

	print_poly(c);
}



신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Basics l 2012.12.05 22:32

 알고리즘 문제에서 가장 기본이 되는 모든 경우의 수를 뽑아내기!

가장 빈번하게 사용되며 문제에서 부분적인 활용에 쓰인다.

반드시 알고 갈 필요가 있다.


Problem

n개의 정수를 입력하여 나열할 수 있는 모든 경우의 수를 표현하여라.

단, 1 <= n <= 100 이다.


Input

n 개의 정수를 입력한다.


Output

나열할 수 있는 모든 경우의 수를 한 줄씩 출력한다.

출력되는 라인 순서는 상관이 없다.


Sample Input

1 2 3


Sample Output

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1


풀고 싶다.



신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Basics l 2012.12.02 14:51
1 
get rsstistory! Tistory Tistory 가입하기!

티스토리 툴바