재시민

주어진 선분 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 발생 가능성도 있고 무엇보다 느리다.

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

실버를 달성했다.

주말까지 달성하자 했는데 역시 게으른 나에게는 버거운 미션.

실버를 달았는데 뭔가 기분이 묘하다.

알고리즘 문제를 풀면서 느끼는건데 수학적 요소가 정말 많다는게 느껴진다.

그래서 뭔가 모르는 공식이 있을 때 구글링을 해보는데

내 힘으로 풀지 못했다는 기분이 자꾸만 든다.

물론 모방을 함으로 실력이 는다고는 하지만 그냥 기분이 그렇다.

종만북이랑 겸해서 해야겠다.

자꾸만 1일 1솔 하려니까 혼자 부담되고 정작 해야할 일을 못하기도 하고

기초부터 탄탄히 하는 법을 배워야 겠다.