-
편집거리(boj 7620)알고리즘 2020. 4. 11. 02:45728x90
최근 며칠동안 편집거리 문제 푸느라 엄청 고생했었어요
사실 쉽게 푸는 방법이 있었는데 편집거리(Hard) 로 풀어보고 싶어서 고집 피우다가 결국 실패했네요.. ㅠㅠ
학교 과제로 나온거라 기한이 있어서, 나중에 시간나면 하드로 다시 풀어보려구요
간단히 요약하자면
최대 17000 글자인 두 문자열 A, B 를 입력받게되면 문자열 A를 B로 만드는데 필요한 비용을 편집거리라고 해요
우리는 이 편집거리를 최소한으로 하는 방법을 찾으면 됩니다.연산과 그 비용의 정의는 다음과 같아요
a 'n' : add 출력 문자열에 'n' 을 출력 ( 비용 : 1 )
d 'n' : delete 입력 문자열의 'n'을 삭제 ( 비용 : 1 )
m 'n' : modify 입력 문자를 'n'으로 수정 ( 비용 : 1 )
c 'n' : copy 입력 문자 'n'을 복사하여 출력 문자열에 출력 (비용 : 0 )
잘 이해가 안되신다면 위 링크를 통해 문제를 읽고오셔야해요!
문제를 보는 순간 일단 뭔진 몰라도 m이 무조건 많이 쓰일 것 같고, c 가 많을 수록 비용이 감소하니까 최대한 c를 많이 활용해야겠다는 생각이 들었어요
문제를 이해했으니 이제 솔루션에 대해 생각해볼게요
Edit Distance 알고리즘은 그 설명을 LCS(Longest Common Subsequence) 로 하는게 편해요
그럼 LCS 란 무엇이냐?
LCS : 두 문자열 A, B 가 있다고 할 때 두 문자열이 공통으로 갖고 있는 가장 긴 subsequence 를 말해요
잠깐 용어 정의를 하자면 subsequence 는 연속하지않아도 되는 부분 문자열이고, substring 은 연속하는 부분 문자열이에요
예를 들어 apple 에서 대표적인 subsequence 는 apl 이고, 대표적인 substring은 ppl 이에요
A = abc
B = qascd
LCS는 qascd 가 되겠죠? = 즉 "ac" 가 LCS 입니다.
Edit distance 는 LCS에서부터 시작된다는걸 눈치 채셨나요?
LCS를 찾게 되면 해당 문자들은 copy 연산을 통해 cost 0으로 출력해낼 수 있어요
이제 남은건 LCS에 속하지 않은 문자들을 어떻게 잘 출력해낼까? 만 남았어요
여기서부터는 DP 개념이 필요해요 (사실 LCS 도 DP 로 구해야해요)
LCS
먼저 LCS를 구하는걸 설명해볼게요. DP 정의는 다음과 같아요
table[i][j] = A의 i 번째 문자와 B의 j 번째 문자까지만 고려했을 때 LCS 의 길이
q a s c d 0 0 0 0 0 0 a 0 b 0 c 0 초기 테이블의 상태는 다음과 같아요. 이 dp 는 특이하게 빈 문자열도 고려해요 그래서 테이블의 0번 row, col 이 빈 문자열을 의미하죠
table[0][0] = 빈 문자열과 빈 문자열의 LCS = 0
table[1][0] = "a" 와 빈 문자열의 LCS = 0
table[2][0] = "ab" 와 빈 문자열의 LCS = 0
table[0][1] = 빈문자열과 "q"의 LCS = 0
점화식은 다음과 같아요
table[i][j] = if ( A[i] == B[j] ) : table[i - 1][j - 1] + 1
else : max( table[i - 1][j], table[i][j - 1] )
말로 풀어볼게요
table[i][j] 는 두 가지 경우로 생각할 수 있는데 A의 i 번째 글자와 B의 j 번째 글자가 같은 경우와 아닌 경우이다.
같은 경우에는 A[i - 1]과 B[j - 1] 까지만 고려하여 만들어진 LCS (table[i - 1][j - 1]) 에 한 글자를 덧붙인다. ( + 1 )
A의 i 번째 글자와 B의 j 번째 글자가 다른 경우에는 지금까지 만들어진 최대 LCS를 가져온다.
A[i - 1] 와 B[j] 까지만 고려한 LCS와 A[i] 와 B[j - 1] 까지만 고려한 LCS 둘 중 큰 놈을 가져온다는 것이다.
잘 이해가 안된다면 아래 예시를 보며 이해해봅시다.
table[1][1] 은 우선 A[1]( = 'a')와 B[1]( = 'q') 가 다르므로 table[0][1], table[1][0] 즉 윗놈과 왼쪽 놈 중 큰 놈을 가져오게 됩니다.
둘 다 0이므로 table[1][1] 은 0입니다.
q a s c d 0 0 0 0 0 0 a 0 0 b 0 c 0 LCS를 추적해서 출력해야하므로 출력 테이블을 만들어 두겠습니다.
이 테이블은 각 원소가 어느 방향으로부터 왔는지 기록하게 됩니다. NORTH_WEST 는 왼쪽 위, NORTH 는 위, WEST는 왼쪽에서부터 왔다는 의미입니다.
q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH b NORTH c NORTH table[1][2]는 어떤가요?
A[1] 과 B[2] 가 'a'로 같으므로 table[0][1] + 1을 넣어줍니다.
table[0][1] 을 가져오는 이유는 A[1]과 B[1]이 고려되지 않은 경우 중에서 가장 큰 LCS 값을 갖는 경우이기 때문입니다.
만약 table[0][2] 를 가져오면 어떻게 될까요? 지금 당장은 1로 동일한 값을 갖겠지만, 이는 우연일 뿐 실제로는 이상한 값을 갖게 될 것입니다.
table[0][2] 는 정의상 A[ ~ 0]과 B[ ~ 2] 를 고려한 경우입니다. 이 값을 가져와 + 1을 한다는 것은 B[2]를 두 번이나 고려하게 된다는 의미입니다. (B[ ~ 2] 는 0번째 글자부터 2번째 글자를 모두 일컫는 표현입니다 "qa" 가 되겠네요)
이미 "qa"를 고려하여 최대 LCS를 구하여 table[0][2]에 저장해뒀는데, 'a' 를 또 고려한다? 이는 논리적으로 맞지않죠
q a s c d 0 0 0 0 0 0 a 0 0 1 b 0 c 0 q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH NORTH_WEST b NORTH c NORTH table[1][3] 은 A[1] 과 B[3] 이 다르므로 윗놈과 왼쪽놈 중 큰 놈을 가져와야합니다.
따라서 1이 되겠죠
q a s c d 0 0 0 0 0 0 a 0 0 1 1 b 0 c 0 q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH NORTH_WEST WEST b NORTH c NORTH table[0][3] ( 윗놈 ) 이 의미하는건 빈 문자열과 "qas" 의 LCS 길이
table[1][2] ( 왼쪽놈 ) 이 의미하는건 "a"와 "qa" 의 LCS 길이
이 둘 중 최대 값을 가져오는 이유는 table[0][3] 은 A[1] 이 고려되지 않은 경우의 수 중 가장 큰 경우이고,
table[1][2] 는 B[3]이 고려되지 않은 경우의 수 중 가장 큰 경우이기 때문입니다.
같은 방법으로 쭉 이어가게되면
q a s c d 0 0 0 0 0 0 a 0 0 1 1 1 1 b 0 c 0 q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH NORTH_WEST WEST WEST WEST b NORTH c NORTH q a s c d 0 0 0 0 0 0 a 0 0 1 1 1 1 b 0 0 1 1 1 1 c 0 0 1 1 2 2 q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH NORTH_WEST WEST WEST WEST b NORTH NORTH NORTH NORTH NORTH NORTH c NORTH NORTH NORTH NORTH NORTH_WEST WEST 따라서 A[3][5] 는 2 이므로 최대 LCS의 길이는 2입니다.
출력은 A[3][5] 부터 DFS 로 타고 들어가면서 [0][0] 까지 가보면 됩니다. 그리고 NORTH_WEST 를 만날때마다 print 해주면 되겠지요
왜냐하면 NORTH_WEST를 만난 경우는 두 문자가 같아서 LCS의 값이 추가된 경우이기 때문에 해당 문자는 LCS에 포함되기 때문이에요
쭉 따라가볼게요
q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH NORTH_WEST WEST WEST WEST b NORTH NORTH NORTH NORTH NORTH NORTH c NORTH NORTH NORTH NORTH NORTH_WEST WEST 맨 좌측 상단은 빈 문자열이라 출력해주지 않습니다!
굵은 글씨 처리한 부분들을 출력하게 되면 "ac" 가 나오네요 정답이 맞죠? 헤헤
Edit Distance
그럼 LCS를 기반으로 한 Edit distance 를 DP로 구해볼게요. 테이블의 정의는 다음과 같아요
table[i][j] = i 번째 문자까지의 A로 j 번째 문자까지의 B를 만드는 최소 cost 의 Edit distacne
= A[ ~ i] 로 B[ ~ j] 를 만드는 최소 cost의 Edit distance
q a s c d 0 1 2 3 4 5 a 1 b 2 c 3 table[0][0] = 빈 문자열을 빈 문자열로 바꾸는 비용 = 0
table[1][0] = "a" 를 빈 문자열로 바꾸는 비용 = 1 -> delete 1번
table[2][0] = "ab" 를 빈 문자열로 바꾸는 비용 = 2 -> delete 2번
table[3][0] = "abc" 를 빈 문자열로 바꾸는 비용 = 3 -> delete 3번
table[0][1] = 빈 문자열을 "q"로 바꾸는 비용 = 1 -> add 1번
table[0][2] = 빈 문자열을 "qa"로 바꾸는 비용 = 2 -> add 2번
...
그럼 dp 답게 1번 row 부터 채워나갈거에요
점화식은 다음과 같습니다.
table[i][j] = if (A[i] == B[j]) : table[i - 1][j - 1]
else : min(table[i - 1][j - 1], table[i - 1][j], table[i][j - 1]) + 1
말로 풀어볼게요
table[i][j] 는 두 가지 경우로 나누어서 생각합니다.
A의 i 번째 글자와 B의 j 번째 글자가 같다면 table[i - 1][j - 1]을 그대로 가져옵니다.
그대로 가져오는 이유는 LCS는 +1 을 해주면서 최대 길이의 공통 subsequence 를 찾아가는 것이였지만 Edit distance 는 최소 코스트를 찾는 것이므로 A[ ~ i] 와 B[ ~ j] 에서 공통 문자 A[i]( = B[i]) 를 copy 해왔기에 cost 는 증가하지 않습니다.
A의 i 번째 글자와 B의 j 번째 글자가 다르다면 table[i - 1][j - 1], table[i - 1][j], table[i][j - 1] 이 셋 중에 값이 가장 적은 것을 가져와 +1 해준 값을 저장합니다.
table[i - 1][j - 1] 을 가져오는 경우는 A[i] 를 B[j] 로 modify(수정) 하는 경우
table[i - 1][j] 를 가져오는 경우는 A[ ~ i - 1] 만으로 B[j]를 만들어버렸으니 사용되지 못한 A[i] 를 버리는 delete(삭제) 하는 경우
table[i][j - 1] 를 가져오는 경우는 A[ ~ i] 로 B[ ~ j - 1]을 만들었으니 끝에 B[j]를 붙여 add(더하기) 하는 경우
이 세 경우를 각각 고려하여 셋 중에서 가장 적은 cost를 갖는 방법으로 A[ ~ i] 를 B[ ~ j] 로 바꾸어냅니다.
table[1][1] 을 생각해보죠
'a' 와 'q'는 같은 문자가 아니니까 왼쪽위, 위, 왼쪽 셋 중에 가장 작은놈 + 1을 합니다.
q a s c d 0 1 2 3 4 5 a 1 1 b 2 c 3 q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH_WEST b NORTH c NORTH table[1][2] 을 생각해보죠
'a' 와 'a'는 같은 문자이므로 왼쪽윗놈을 그대로 가져옵니다.
q a s c d 0 1 2 3 4 5 a 1 1 1 b 2 c 3 q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH_WEST NORTH_WEST b NORTH c NORTH 계속 채워나가면 다음과 같이 됩니다.
q a s c d 0 1 2 3 4 5 a 1 1 1 2 3 4 b 2 2 2 2 3 4 c 3 3 3 3 2 3 q a s c d NORTH_WEST WEST WEST WEST WEST WEST a NORTH NORTH_WEST NORTH_WEST WEST WEST WEST b NORTH NORTH_WEST NORTH_WEST NORTH_WEST NORTH_WEST NORTH_WEST c NORTH NORTH_WEST NORTH_WEST NORTH_WEST NORTH_WEST WEST 따라서 최소 코스트는 3
그 과정을 DFS로 출력해보면
a q
c a
m s
c c
a d
가 됩니다.
주의할 점은 NORTH_WEST 라고 그냥 막 출력하는게 아니라 두 문자가 같으면 copy, 다르면 modify 인것만 구분지어서 출력해주면 어렵지 않게 출력할 수 있습니다.
N = 문자열 A의 길이
W = 문자열 B의 길이라고 할 때
두 DP 는 시간복잡도 O(NW), 공간복잡도는 O(NW)가 됩니다.
맨 위 링크타고 보시면 시간은 8초, N, W는 각각 최대 17000이므로 17000 * 17000 = 289000000 대략 10^8 이라서 충분히 돌아갑니다만 메모리 제한이 128MB 에요 그래서 dp 테이블이랑 출력 테이블을 char 형 배열로 선언하더라도 289 MB 짜리 두 개라서 가볍게 터집니다. (하나도 못만들어요...ㅎ)
그래서 공간 복잡도를 최적화해야하는데 DP 테이블은 O(W) 로 최적화하여 토글 방식으로 생성이 가능합니다.
쉽게말해서 어느 한 요소를 만들 때 필요한건 그 윗놈, 왼쪽놈, 그 왼쪽 윗놈만 필요하니까 한 row를 채우는데는 그 바로 위 row만 있으면 된다고 생각하는겁니다.
q a s c d 0 1 2 3 4 5 a 1 1 1 2 3 4 b 2 2 2 2 3 4 c 3 3 3 3 2 3 q a s c d 0 1 2 3 4 5 a 1 1 1 2 3 4 b 2 2 2 2 3 4 c 3 3 3 3 2 3 q a s c d 0 1 2 3 4 5 a 1 1 1 2 3 4 b 2 2 2 2 3 4 c 3 3 3 3 2 3 q a s c d 0 1 2 3 4 5 a 1 1 1 2 3 4 b 2 2 2 2 3 4 c 3 3 3 3 2 3 이렇게 색깔 칠한 순서대로 배열을 구성해서
table[0]에 구한 값을 table[1] 을 만들때 사용하고, 여기서 다시 table[0] 을 table[1] 을 통해 만들어가는 방식입니다.
근데 이게 문제가 dp 테이블은 토글방식으로 최적화가 가능한데 출력 테이블은 이게 안되거든요
하는 방법은 Hirschberg 알고리즘이라고 있긴한데 이거 코딩을 제대로 해내지 못해서 일단 단순하게 메모리 최적화를 시켰어요
제가 한 방법은 C언어의 비트필드를 이용해서 NORTH_WEST, WEST, NORTH, NORTH_WEST_BY_COPY 이렇게 4가지 경우를 표현하려면 2비트로 표현이 가능하므로 char 하나(8 비트)를 통해 4개의 출력 테이블 element 를 표현할 수 있어요
원래 char 1개로 하나의 element를 표현하다가 4개를 표현할 수 있게 되니 사이즈는 당연히 4분의 1로 줄어들것이고
그러면 280MB / 4 = 70MB 남짓 되므로 128MB 제한에 들 수 있게 되는거죠
제 소스 첨부합니다~
#include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <vector> #include <deque> #include <list> #include <queue> #include <memory.h> #define INF 98765432 #define MAX 17000 #define NORTH_WEST 0 #define NORTH 1 #define WEST 2 #define COPY 3 typedef struct { unsigned char leftTop : 2; unsigned char rightTop : 2; unsigned char leftBottom : 2; unsigned char rightBottom : 2; } Path; int N, K; int dp[2][MAX + 10]; Path path_log[MAX / 2 + 10][MAX / 2 + 10]; char str1[MAX + 10]; char str2[MAX + 10]; int length1, length2; int direction[4][2] = { {-1, -1}, {-1, 0}, {0, -1}, {-1, -1} }; int get(int y, int x) { Path p = path_log[y / 2][x / 2]; if (y % 2 == 1 && x % 2 == 1) return p.rightBottom; if (y % 2 == 1) return p.leftBottom; if (x % 2 == 1) return p.rightTop; return p.leftTop; } void set(int y, int x, int val) { if (y % 2 == 1 && x % 2 == 1) path_log[y / 2][x / 2].rightBottom = val; else if (y % 2 == 1) path_log[y / 2][x / 2].leftBottom = val; else if (x % 2 == 1) path_log[y / 2][x / 2].rightTop = val; else path_log[y / 2][x / 2].leftTop = val; } void print(int y, int x) { if (y == 0 && x == 0) return; int dIndex = get(y, x); int newY = y + direction[dIndex][0]; int newX = x + direction[dIndex][1]; print(newY, newX); char op, c; if (dIndex == NORTH_WEST) { op = 'm'; c = str2[x - 1]; } else if (dIndex == NORTH) { op = 'd'; c = str1[y - 1]; } else if (dIndex == WEST) { op = 'a'; c = str2[x - 1]; } else { op = 'c'; c = str1[y - 1]; } printf("%c %c\n", op, c); } int main() { scanf("%s %s", str1, str2); length1 = strlen(str1); length2 = strlen(str2); for (int i = 0; i <= MAX; i++) { dp[0][i] = i; set(0, i, WEST); set(i, 0, NORTH); } for (int i = 1; i <= MAX; i++) { int index = i % 2; dp[index][0] = i; for (int j = 1; j <= MAX; j++) { if (str1[i - 1] == str2[j - 1]) { dp[index][j] = dp[!index][j - 1]; set(i, j, COPY); } else { dp[index][j] = std::min( dp[!index][j - 1], std::min( dp[!index][j], dp[index][j - 1] ) ) + 1; if (dp[index][j] == dp[!index][j - 1] + 1) { set(i, j, NORTH_WEST); } else if (dp[index][j] == dp[!index][j] + 1) { set(i, j, NORTH); } else { set(i, j, WEST); } } } } print(length1, length2); return 0; }'알고리즘' 카테고리의 다른 글
MT 문제 (boj 10265) (0) 2020.05.16 위상정렬 (0) 2020.05.16 사과와 바나나 (boj 3114) (0) 2020.04.17 구간합 구하기 (0) 2020.04.17 DFS 메모이제이션 (0) 2020.04.15