12-1. 다음에 주어진 프로그램을 참고해서 주어진 자료에 대한 컨벡스 헐(Convex Hull)을 결정하여 출력하는 프로그램을 완성하고 실습하시오. 또한, N(>20)개의 점을 randon() 함수로 발생하고, 이점들에 대한 컨벡스 헐(Convex Hull)을 구하고, 이 과정에서 실행한 2 점 사이의 수평각 계산 회수와 각의 비교회수 및 Convex Hull 내부 점 수를 count 해서 출력하시오. 단, 수평각들을 sort하는 알고리즘은 임의로 선택하고, x와 y좌표값은 100보다 작게 한다.

 

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

 

#define Nmax 30

 

// 점(point) 구조체

struct point

{

int x;

int y;

char c;

};

 

 

class Polygon

{

private :

 

int computeCount; // 수평각 계산 회수

int compareCount; // 각의 비교 회수

int innerDot; // 볼록껍질 내부 점의 개수

int wrapped_count; // 볼록껍질의 꼭지점 수

 

public :

 

Polygon(struct point *poly, int N);// Polygon 생성자

void printPoly(struct point *poly, int N); // 점들의 좌표 출력

float ComputeAngle(struct point p1, struct point p2); // 수평각 계산

int PointWrapping(struct point P[], int n); // 볼록껍질 구하기(짐꾸리기 알고리즘)

void Polygon::Swap(struct point *a, struct point *b); // Swap 함수

};

 

 

 

 

Polygon::Polygon(struct point *poly, int N)

{

wrapped_count=0; computeCount=0; compareCount=0; innerDot=0;

 

cout<<"-----------------------------------------\n\n";

cout << "\n주어진 점들의 좌표\n";

 

printPoly(poly, N-1); // 점들의 초기값

 

// 리턴된 볼록껍질의 꼭지점 수를 wrapped_count에 저장

wrapped_count = PointWrapping(poly, N);

 

cout << "\n점 집합의 볼록 껍질\n";

printPoly(poly, wrapped_count-1); // PointWrapping에서 구성된 점집합을 출력

 

// 마지막 인덱스에 복사된 볼록껍질의 첫번째 점을 출력해서 연결시킨다.

cout << " -> " << poly[N].c << "[" << poly[N].x << "," << poly[N].y << "]" << "\n";

 

// Convex Hull 내부의 점의 개수(전체 점의 개수 - wrapping된 점의 개수)

innerDot = N - wrapped_count;

 

// 연산 카운터 출력

cout << "수평각 계산 회수 : " << computeCount;

cout << "각의 비교 회수 : " << compareCount;

cout << "Convex Hull 내부 점의 수 : " << innerDot ;

cout<<"------------------------------------------\n\n";

}

 

// 점들의 좌표 출력 함수

void Polygon::printPoly(struct point *poly, int N)

{

for(int i=0; i<N; i++)

{

cout << poly[i].c << "[" << poly[i].x << "," << poly[i].y << "]" << " -> ";

}

cout << poly[N].c << "[" << poly[N].x << "," << poly[N].y << "]";

}

 

// 수평각 계산 함수

float Polygon::ComputeAngle(struct point p1, struct point p2)

{

int dx, dy, ax, ay;

double t;

 

computeCount++; // 수평각 계산회수 카운터 증가

 

dx = p2.x - p1.x; ax = abs(dx);

dy = p2.y - p1.y; ay = abs(dy);

 

t = (ax+ay == 0) ? 0 : (float)dy/(ax+ay);

 

if(dx < 0) t=2-t; else if(dy<0) t=4+t;

return (float)t*90.0;

}

 

// 볼록껍질 구하기(짐꾸리기 알고리즘)

int Polygon::PointWrapping(struct point P[], int n)

{

int i, NumVertex;

float MinAngle, MaxAngle, Angle;

int FirstPoint, NextPoint;

 

FirstPoint=0;

 

// 기준점 찾기(Y가 최소인 점)

for(i=1; i<n; i++) if(P[i].y < P[FirstPoint].y) FirstPoint=i;

 

NumVertex=-1;

 

P[n]= P[FirstPoint]; // 첫번째 꼭지점 복사본 저장

 

MaxAngle=0.0;

NextPoint=FirstPoint;

 

// 다음 꼭지점을 찾는 루프, 다음꼭지점을 배열의 왼쪽으로 밀어둠

do{

 

NumVertex++;

Swap(&P[NumVertex], &P[NextPoint]);

NextPoint=n;

MinAngle=MaxAngle;

MaxAngle=360.0;

 

for(i = NumVertex+1; i <= n; i++)

{

Angle = ComputeAngle(P[NumVertex], P[i]);

 

// 직전에 구한 각 보다 크면서 최소인 각을 찾는다.

if(Angle > MinAngle && Angle < MaxAngle)

{

compareCount++; // 비교연산 카운터 증가

NextPoint=i;

MaxAngle = Angle;

}

}

}while(NextPoint != n);

 

// 볼록껍질의 꼭지점 수를 리턴한다.

// 현재 프로그램에서 출력부분과, 내부점의 계산을 위해

// 꼭지점 수에 1을 더한값을 리턴한다.

return NumVertex+1;

}

 

// PointWrapping 에서 데이터 교환에 사용하는 함수

void Polygon::Swap(struct point *a, struct point *b)

{

struct point temp[1];

 

temp[0].c = a->c;

temp[0].x = a->x;

temp[0].y = a->y;

 

a->c = b->c;

a->x = b->x;

a->y = b->y;

 

b->c = temp[0].c;

b->x = temp[0].x;

b->y = temp[0].y;

}

 

 

void main()

{

//주어진 값으로 점의 위치 초기화

struct point poly1[] = { 3, 4, 'A',

1, 2, 'B',

2, 5, 'C',

2, 6, 'D',

9, 3, 'E',

5, 3, 'F',

6, 4, 'G',

8, 4, 'H',

-1, -1, '-' };

 

 

 

cout<<"[ 주어진 자료 ]";

Polygon POLY1(poly1, 8);

 

struct point *poly2;

 

poly2 = new struct point[Nmax]; // Nmax 의 개수 만큼 point 생성

 

srand((int)time(NULL));

 

for(int i=0; i<=Nmax; i++)

{

poly2[i].x = rand()%100;

poly2[i].y = rand()%100;

poly2[i].c = i-1 + 'A';

}

 

poly2[Nmax].x = -1; poly2[Nmax].y = -1; // Nmax번 자리 초기화

 

cout<<"\n\n[ Random" << "(" << Nmax << ") ]\n";

Polygon POLY2(poly2, Nmax);

}

 

 

 

 

  ▣ 결과 출력

 

   

 

 

11-1. 다음에 주어진 프로그램을 참고해서 주어진 자료에 대한 단순 다각형을 결정하여 출력하는 프로그램을 완성하고 실습하시오. 또한, N(>30)개의 점을 randon() 함수로 발생하고, 이점들에 대한 단순다각형 Poly[]를 구하고, 이 과정에서 실행한 2점 사이의 수평각 계산 횟수와 각의 비교회수를 count해서 출력하시오. 단, 수평각들을 sort하는 알고리즘은 임의로 선택하고, x와 y좌표값은 100보다 작게 한다.

 

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

 

#define Nmax 40

 

// 점(point) 구조체

struct point

{

int x;

int y;

char c;

double angle;

};

 

// 선(line) 구조체

struct line

{

struct point p1;

struct point p2;

};

 

// Polygon Class

class Polygon

{

private :

 

int computeCount; // 수평각 계산회수

int compareCount; // 각의 비교회수

 

public :

 

Polygon(struct point *poly, int N); // Polygon 생성자

void printPoly(struct point *poly, int N); // 다각형 출력

void compute(struct point *poly, int N);

double ComputeAngle(struct point p1, struct point p2); // 수평각 계산

 

void insertion_sort(struct point *polygon, int N); // 삽입정렬

};

 

Polygon::Polygon(struct point *poly, int N)

{

computeCount=0; compareCount=0;

 

cout<<"----------------------------------------------\n\n";

 

printPoly(poly, N); // 수평각이 계산되기 전 점들 출력

compute(poly, N); // 수평각 계산

insertion_sort(poly, N); // 다각형의 angle 순으로 정렬

 

cout << "\n\n";

printPoly(poly, N); // 수평각이 계산된 후 정렬된 점들 출력

 

cout << "\n\n수평각 계산 회수 : ";

cout << computeCount << "\n";

cout << "각의 비교 회수 : ";

cout << compareCount << "\n\n";

 

cout<<"-----------------------------------------------\n\n";

}

 

void Polygon::printPoly(struct point *poly, int N)

{

int i;

for(i=1; i<=N; i++)

{

cout << poly[i].c << "[" << poly[i].x << "," << poly[i].y << "]" << " -> ";

}

cout << poly[1].c << "[" << poly[1].x << "," << poly[1].y << "]" << "\n";

}

 

void Polygon::compute(struct point *poly, int N)

{

int i, k=1;

for(i=1; i<N; i++) // 기준점 계산(Y축이 가장 작은 점)

{

if(poly[k].y > poly[i+1].y)

k = i+1;

}

for(i=1;i<=N;i++)

{

 

 

// 수평각 계산, angle에 정보를 저장

poly[i].angle = ComputeAngle(poly[k], poly[i]);

}

}

 

double Polygon::ComputeAngle(struct point p1, struct point p2)

{

int dx, dy, ax, ay;

double t;

 

computeCount++;

 

dx = p2.x - p1.x; ax = abs(dx);

dy = p2.y - p1.y; ay = abs(dy);

 

t = (ax+ay == 0) ? 0 : (float)dy/(ax+ay);

 

if(dx < 0) t=2-t; else if(dy<0) t=4+t;

return (double)t*90.0;

}

 

// 삽입정렬을 사용하여 다각형의 angle 순으로 정렬

void Polygon::insertion_sort(struct point *poly, int N)

{

int i,j;

struct point p;

for(i=2 ; i<=N ; i++)

{

p.angle = poly[i].angle;

p.c = poly[i].c;

p.x = poly[i].x;

p.y = poly[i].y;

 

j = i;

 

while (poly[j-1].angle > p.angle)

{

compareCount++; // 비교회수 카운트

 

poly[j].x = poly[j-1].x;

poly[j].y = poly[j-1].y;

poly[j].c = poly[j-1].c;

poly[j].angle = poly[j-1].angle;

j--;

}

 

compareCount++; // 비교회수 카운트

 

poly[j].angle = p.angle;

poly[j].c = p.c;

poly[j].x = p.x;

poly[j].y = p.y;

}

}

 

void main()

{

struct point poly1[] = { -1, -1, ' ', -1, // 0번 자리 초기화

1, 4, 'A', 0,

3, 2, 'B', 0,

2, 5, 'C', 0,

2, 6, 'D', 0,

9, 8, 'E', 0,

9, 3, 'F', 0,

5, 3, 'G', 0,

6, 4, 'H', 0,

8, 4, 'I', 0,

7, 1, 'J', 0};

 

cout<<"\n[ 주어진 자료 ]\n";

Polygon POLY1(poly1, 10);

 

struct point *poly2;

poly2 = new struct point[Nmax]; // Nmax 의 개수 만큼 point 생성

 

srand((int)time(NULL));

 

for(int i=1; i<=Nmax; i++)

{

poly2[i].x = rand()%100+1;

poly2[i].y = rand()%100+1;

poly2[i].c = i-1 + 'A';

poly2[i].angle = 0;

}

 

poly2[0].x = -1; poly2[0].y = -1; poly2[0].angle = -1; // 0번 자리 초기화

 

cout<<"\n\n[ Random" << "(" << Nmax << ") ]\n";

Polygon POLY2(poly2, Nmax);

 

}

 

▣ 결과 출력

 

 

10-1. 다음에 주어진 프로그램을 참고해서 주어진 Text string 자료에서Pattern을 모두 찾는 Boyer-Moore 의 알고리즘을 구현하고, 알고리즘 수행에서 문자비교회수를 헤아리고, Brute force, KMP 알고리즘의 성능과 비교하시오. 또한, 최악의 상태의 자료에 대해서도 실습하시오.

(예: a[]="AAAAAAAAAAAA", p[]="AAAAAAB")

 

Text String : "A TEXT STRING SEARCHING EXAMPLE CONSISTING OF A GIVEN STRING"

Pattern String : "STRING"

 

#include <iostream>

#include<stdlib.h>

#include<string>

using namespace std;

 

#define max(a,b) (((a)>(b))?(a):(b))

 

int *next; // KMP의next 테이블

int *lp; // BM의Lost Pos

 

int compare_cnt; // 비교회수카운터

 

 

int index(char c)

{

return toupper(c) - 'A'

}

 

void LastPos(char *p) // 불일치문자방책

{

int i, m = strlen(p);

 

for(i = 0; i <= 26; i++)

{

compare_cnt++;

lp[i] = -1;

}

for(i = 0; i < m; i++)

{

compare_cnt++;

lp[index(p[i])] = i;

}

}

 

 

 

void BoyerMoore(char *p, char *a)

{

int i, j, m = strlen(p), n = strlen(a);

compare_cnt = 0;

 

lp = new int[27]; // Lp[] 동적할당

LastPos(p);

 

j = 0;

 

while(j <= n-m)

{

compare_cnt++;

for(i=m-1; i>=0 && p[i]==a[j+i]; i--){compare_cnt++;};

if(i == -1)

{

cout << j << " "

j = j + m;

}

else

{

j = j + max(m-i, m-1-lp[index(a[j+i])]);

}

}

 

}

 

int brutesearch(char *p, char *a)

{

int i, j, m = strlen(p), n = strlen(a);

compare_cnt = 0;

 

for(i = 0, j = 0; j < m && i < n; i++, j++)

{

compare_cnt++;

if(a[i] != p[j])

{

compare_cnt++;

i -= j;

j = -1;

}

}

if(j == m) return i - m;

else return i;

}

 

void initnext(char *p) // next 테이블

{

int i, j, m = strlen(p);

next[0] = -1;

 

for(i=0,j=-1; i<m; i++, j++, next[i]=j)

{

compare_cnt++;

 

while(j>=0 && p[i]!=p[j])

{

compare_cnt++;

j = next[j];

}

}

}

 

int kmpsearch(char *p, char *a)

{

int i, j, m = strlen(p), n = strlen(a);

compare_cnt = 0;

next = new int[m+1];

initnext(p);

 

for(i=0, j=0; j<m && i<n; i++, j++)

{

compare_cnt++;

while(j>=0 && a[i]!=p[j]){

j = next[j];

compare_cnt++;

}

}

 

delete next;

if(j==m) return i-m;

else return i;

}

 

 

void main()

{

char Text[] = "A TEXT STRING SEARCHING EXAMPLE CONSISTING OF A GIVEN STRING" char Pattern[] = "STRING"

 

char w_Text[] = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

 

char w_Pattern[] = "AAAAAAAAAB"

 

cout << "Text : " << Text << "\n"

cout << "Pattern : " << Pattern << "\n\n"

 

cout << "[Brute Force] \nIndexPattern : " << brutesearch(Pattern, Text) << "\n"

cout << "Compare Count : " << compare_cnt << "\n\n"

 

cout << "[KMP] \nIndexPattern : " << kmpsearch(Pattern, Text) << "\n"

cout << "Compare Count : " << compare_cnt << "\n\n"

 

cout << "[Boyer Moore] \nIndexPattern : "

BoyerMoore(Pattern, Text);

cout << "\nCompare Count : " << compare_cnt << "\n\n"

 

cout << "\n\n\n"

 

cout << "Text : " << w_Text << "\n"

cout << "Pattern : " << w_Pattern << "\n\n"

 

cout << "[Brute Force] \nIndexPattern : " << brutesearch(w_Pattern, w_Text) << "\n"

cout << "Compare Count : " << compare_cnt << "\n\n"

 

cout << "[KMP] \nIndexPattern : " << kmpsearch(w_Pattern, w_Text) << "\n"

cout << "Compare Count : " << compare_cnt << "\n\n"

 

cout << "[Boyer Moore] \nIndexPattern : "

BoyerMoore(w_Pattern, w_Text);

cout << "\nCompare Count : " << compare_cnt << "\n\n"

 

}

 

 

 

 

 

 

▣ 결과 출력