재시민

수업 시간에 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솔 하려니까 혼자 부담되고 정작 해야할 일을 못하기도 하고

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

Malware

• Virus : 자기증식
• Worm : 자기증식, 스스로 activate
• Spyware malware
  • keystrock
  • Private 정보 위부유출