재시민

단순 폐쇄 경로 : N 개의 점이 주어졌을 때 이 점들을 모두 경유하고 출발점에 되돌아오는 비 교차 경로

우편배달부 문제를 예로 들어 단순 폐쇄 경로를 찾아보자

방법 

1.  기준점 D 설정
   1. y 좌표가 가장 작은 값으로 설정하되 동일한 값이 있다면 x 좌표도 최소인 점으로 선정
2.  D에서 나머지 점들 P 각각에 대한 반직선 DP 라 할 때, 반직선 Dx 와 DP 사이의 각도들을 계산
3.  각도를 기준으로 P 점들을 오름차순으로 정렬
4.  기준점부터 시작해 정렬된 점들을 순서대로 직선 연결

각도를 구하는 방법을 생각해보자

• 아크탄젠트를 이용해 각도를 구하자
  • 가장 흔한방법이지만 계산속도가 느리다.
• 상대각도
  • 실제각도는 아니지만 효율적인 각도비교가 가능하다.

상대각도 구하는 방법

이 때 점의 사분면 위치에 따라 dx, dy 값이 음수가 되는 경우가 생긴다.

그렇게 되면 점의 정확한 상대각도를 구하기 어려워지기 때문에 식조작이 필요하다.

1사분면에서의 상대각도는 0과 1사이의 값이므로 360도의 상대각도가 4 이므로

2사분면 : 2 - 상대각도

3사분면 : 2 + 상대각도

4사분면 : 4 - 상대각도

이때 상대각도를 구하는 dx, dy 에는 절댓값을 씌워준다.

위의 식을 ComputeAngle 함수로 만들어 표현한 코드는 아래와 같다.

float ComputeAngle(struct point A, struct point B) {
	int Dx, Dy; float Angle;
	Dx = B.x - A.x; Dy = B.y - A.y;
	if ((Dx >= 0) && (Dy == 0)) Angle = 0;
	else {
		Angle = abs(Dy) / (abs(Dx) + abs(Dy));
		if ((Dx < 0) && (Dy >= 0)) Angle = 2 - Angle;
		else if ((Dx <= 0) && (Dy < 0)) Angle = 2 + Angle;
		else if ((Dx > 0) && (Dy < 0)) Angle = 4 - Angle;
	}
    return Angle * 90.0;
}

주어진 선분 AB, CD 가 서로 교차하는지 확인해보자

꺾은선 ABC 와 ABD 가 서로 다른 방향 ( 시계 와 반시계 ) 이며

CDA 와 CDB 가 서로 다른 방향일때 두 선분은 교차한다고 말할 수 있다.

이 때 꺾은선의 방향을 알려주는 함수를 정의하자.

함수 Direction 은 시계방향일 때  1, 반시계일 때 -1, 한 직선위에 세 점이 존재할 때 0 이라고 한다면

교차하기 위해서는 아래 식을 만족해야한다.

이 때 Direction 함수를 코드로 나타내 보자

int direction(struct point A, struct point B, struct point C) {
	int dxAB, dxAC, dyAB, dyAC, Dir;
	dxAB = B.x - A.x; dxAC = C.x - A.x;
	dyAB = B.y - A.y; dyAC = C.y - A.y;

	if (dxAB * dyAC < dyAB * dxAC) Dir = -1;
	if (dxAB * dyAC > dyAB * dxAC) Dir = 1;
	if (dxAB * dyAC == dyAB * dxAC) {
		if (dxAB == 0 && dyAB == 0) Dir = 0;
		if ((dxAB * dxAC < 0) || (dyAB * dyAC < 0)) Dir = 1;
		else if ((dxAB * dxAB + dyAB * dyAB) >= (dxAC * dxAC + dyAC * dyAC)) Dir = 0;
		else Dir = -1;

	}
	return Dir;
}

이 때 A, B, C 가 일직선 상에 있을 때 어떤 점이 중점이 되는지 파악해 줘야한다.

이 부분을 코드로 다시 나타내보면

if (dxAB * dyAC == dyAB * dxAC) {// AC, AB 기울기가 동일한 경우
		if (dxAB == 0 && dyAB == 0) Dir = 0; // A,B,C 중 동일점이 존재하는 경우
		if ((dxAB * dxAC < 0) || (dyAB * dyAC < 0)) Dir = -1; // AB 와 AC가 반대방향 확인
        // 맞으면 A 가 사이점
		else if ((dxAB * dxAB + dyAB * dyAB) >= (dxAC * dxAC + dyAC * dyAC)) Dir = 0;
        // AB, AC 같은방향이면서 |AB| >= |AC| 인지 확인
        // 맞으면 C 가 사이점
		else Dir = 1; // B가 사이점
	}

위의 Direction 함수를 이용해 Intersection 함수를 만들자

int intersection (strcut line AB, struct line CD){
	int LineCrossing;
    if((Direction(AB.A,AB.B,CD.C) * Direction(AB.A,AB.B,CD.D) <= 0) &&
    	(Direction(CD.C,CD.D,AB.A) * Direction(CD.C,CD.D,AB.B) <= 0))
        LineCrossing = true;
    else LineCrossing = false;
    return LineCrossing;
}

수업 시간에 Dynamic Progrmaming 실습으로 편집거리테이블 (string edit table) 에 대해 배웠다.

편집거리는 두 문자열의 차이를 측정하기 위한 문자열 측정 단위 이다.

최소 편집거리는 주어진 문자열을 목표 문자열로 변환하기 위해 필요한 최소한의 편집 거리 이다.

X = bbabb -> Y = abaa (X : 주어진 문자열 , Y : 목표 문자열 ) 

- 삽입 (1), 삭제 (1), 변경(0 or 2)

1) 편집 1 -> x 전부 삭제, y 하나씩 삽입 (비용 : 9)

2) 편집 2 -> x1, x2 를 삭제하고 x5를 a로 변경한 뒤 a 삽입 (비용 : 6)

<편집 거리 테이블>

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int DP(string A, string B)
{
    int aLen = A.size();
    int bLen = B.size();
    int** E;
    char* aChar, * bChar;
    aChar = (char*)A.c_str();
    bChar = (char*)B.c_str();
    E = new int* [aLen + 1];
    for (int i = 0; i <= aLen; i++)
    {
        E[i] = new int[bLen + 1];
    }
    for (int i = 0; i <= aLen; i++)
    {
        E[i][0] = i;
    }
    for (int i = 0; i <= bLen; i++)
    {
        E[0][i] = i;
    }
    for (int i = 1; i <= aLen; i++)
    {
        for (int j = 1; j <= bLen; j++)
        {
            if (aChar[i - 1] == bChar[j - 1])
                E[i][j] = min(E[i - 1][j] + 1, min(E[i][j - 1] + 1, E[i - 1][j - 1]));
            else
                E[i][j] = min(E[i - 1][j] + 1, min(E[i][j - 1] + 1, E[i - 1][j - 1] + 2));
        }
    }
    for (int i = 0;i <= aLen;i++) {
        for (int j = 0;j <= bLen;j++) {
            printf("%d\t", E[i][j]);

        }
        printf("\n");

    }
    printf("-----------------------------------\n");
    return E[aLen][bLen];
}
int main(void)
{
    string A, B;
    getline(cin, A);
    getline(cin, B);
    printf("편집거리테이블\n");
    cout << "최소편집 비용 : " << DP(A, B);
}

 알고리즘 설명

E[i][j] = min(E[i-1][j],min(E[i][j-1],E[i-1][j-1] + 2))

E[1][1] 을 구하기 위해서는 주변의 세 가지 요소의 값 중 최솟값을 구한 후, 삽입, 제거, 교환 연산에 의한 비용을 더해주

면된다.

E[0][0], E[1][0], E[0][1] 중 최솟값은 E[0][0] = 0 이다.

그리과,  0 행과 0 열의 숫자가 다르므로 비용은 2 증가 따라서, E[1][1] = 2이다. 

이런식으로 모든 행렬의 값을 구하면 E[모든행의개수][모든열의개수] 의 값은 최소 편집거리가 된다. 

이때, 목표 문자열과 현재 문자열을 바꾸어 계산해도 값은 같으며, 

연산들의 값을 각 각 다르게 주고 문자열들을 바꾸어 계산해도 값은 같다.

왜냐하면, 결국 최솟값의 합연산 결과들이므로 마지막 최소편집거리는 같다. 

www.acmicpc.net/step/34

고등 확률과 통계에서 배우는 순열과 조합이다.

순열과 조합을 구현하는데에 있어 매번 구글링 하기 귀찮아 좋은 정보를 얻어 정리를 해보려고한다.

출처 : hongchan.tistory.com/5

덕분에 좋은 정보를 얻었다.

순열 nPr

void printArray(int a[], int r) {
    for (int i = 0;i < r;i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void permutation(int pArr[], bool check[], int n, int r, int depth) {
    if (depth == r) {
        printArray(pArr, r);
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!check[i]) {
            check[i] = true;
            pArr[depth] = i;
            permutation(pArr, check, n, r, depth + 1);
            check[i] = false;
        }
    }
}

int main(void) {

    int n, r;
    cin >> n >> r;
    int* pArr = new int[r];
    bool* check = new bool[n + 1];
    for (int i = 0;i < r;i++) {
        pArr[i] = 0;
    }
    for (int i = 0;i < n + 1;i++) {
        check[i] = false;
    }
    permutation(pArr, check, n, r, 0);

    return 0;
}

1. pArr[] : n 까지의 숫자의 경우를 저장할 배열
2. check[] : 순열에서 중복의 여부를 확인하는 배열 ( 이 배열을 뺀다면 중복 순열이 된다. )

알고리즘 설명

1. check 가 false 인지 확인 ( 이미 나온 숫자인가? )
2. false 이면 true 로 할당
3. pArr[] 에 i 할당 ( 1부터 저장하기 위해 i = 1 로 지정 )
4. Permutation(...,depth + 1) 실행하여 중복되지 않는 수를 확인하고 배열에 삽입
5. depth == r 이 된다면 pArr 에 있는 원소 모두 출력
6. check 를 차례대로 false 로 할당하면서 함수 빠져나옴
7. for 문 반복

조합 nCr

void combination(int pArr[], int n, int r, int depth, int next) {
    if (depth == r) {
        printArray(pArr, r);
        return;
    }

    for (int i = next; i <= n; i++) {
        pArr[depth] = i;
        combination(pArr,n, r, depth + 1, i+1);// i+1 을 i로 바꿔주면 중복 허용
    }
}

int main(void) {

    int n, r;
    cin >> n >> r;
    int* pArr = new int[r];
    for (int i = 0;i < r;i++) {
        pArr[i] = 0;
    }
    combination(pArr, n, r, 0, 1);

    return 0;
}

순열과 다른 점 

• 조합은 순열과 달리 오름차순으로 정렬이 된다.

따라서, for 문의 i 값이 combination 이 실행될 수록 이 전 i 값보다 커야한다.

그리고, check[] 배열을 사용하지 않는 이유는 i 값을 늘려줌으로써 이전의 i 값이나 동일한 값이 들어가지 않기 때문이다.

그래서, i 의 값을 유지시킨다면 중복 조합이 된다. 

재귀로된 순열과 조합을 설명해 보았다.

하지만, 재귀인만큼 큰 수로 접근하게 된다면 overflow 발생 가능성도 있고 무엇보다 느리다.

이와 관련된 문제를 풀었었는데 까먹었다. ㅎㅎ