[백준] 15483번: 최소 편집 (C++)

✅문제: 15483번

15483번: 최소 편집

📌개념정리

(1) Dynamic Programming (동적 프로그래밍)

• 정의: 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

 

(2) Levenshtein Distance (편집 거리 알고리즘)

• 정의: 두 문자열의 유사도를 판단하는 알고리즘
• 기준: 삽입, 삭제, 교체

 

(3) 이중 포인터와 동적 다차원 배열

• 이중 포인터: int에 대한 포인터를 가리키는 포인터는 두 개의 별표(**)를 사용하여 선언함
• 동적으로 2차원 배열을 할당할 때 이중 포인터가 쓰임

📌문제풀이

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	string A, B;
	cin >> A >> B;

	int** dp = new int* [A.length() + 1];
	for (int i = 0; i <= A.length(); i++)
		dp[i] = new int[B.length() + 1]{};

	for (int i = 0; i <= A.length(); i++)
		dp[i][0] = i;

	for (int j = 0; j <= B.length(); j++)
		dp[0][j] = j;

	for (int i = 1; i <= A.length(); i++)
	{
		for (int j = 1; j <= B.length(); j++)
		{
			if (A[i - 1] == B[j - 1])
            {
				dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
				dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
		}
	}
	cout << dp[A.length()][B.length()];
    
    return 0;
}

1. 두 문자열 A와 B를 입력받음.
2. A와 B의 길이에 1을 더한 크기의 2차원 동적 배열 dp를 선언하고 메모리를 할당함. 여기서 dp[i][j]는 A의 첫 번째 문자부터 i번째 문자까지의 부분 문자열을 B의 첫 번째 문자부터 j번째 문자까지의 부분 문자열로 변환하는 데 필요한 최소 연산의 수를 나타냄.
3. dp 배열의 첫 번째 행과 열을 초기화함.
4. 이중 for 루프를 사용하여 배열을 채움.
   • A의 i번째 문자와 B의 j번째 문자가 같다면, dp[i][j]는 대각선 위의 값 dp[i-1][j-1]을 그대로 가져옴.
   • 다르다면, dp[i][j]는 세 가지 연산 중 최소 연산 횟수에 1을 더한 값임.삽입(dp[i][j-1]), 삭제(dp[i-1][j]), 교체(dp[i-1][j-1]) 중에서 최소 비용을 선택함.
5. 배열의 마지막 셀에는 A를 B로 변환하는 데 필요한 최소 연산의 수가 저장됨. 이 값을 출력하여 문제를 해결함.

📌후기

• 동적 프로그래밍과 문자열 처리에 대한 이해에 도움이 되었음. 이러한 알고리즘을 이해하고 구현할 수 있게 되면, 보다 복잡한 문제에 접근하는 데도 도움이 될 것 같음.
• 이중 포인터 사용과 동적 할당에 대한 경험을 쌓을 수 있었음. 알고리즘을 구현하면서 발생할 수 있는 여러 가지 에지 케이스를 고려할 수 있었음.

📌참고자료

1) 화투의 개발 블로그, "편집 거리 알고리즘(Levenshtein Distance, Edit Distance)", 2016.04.21, https://hsp1116.tistory.com/41

2) 하고 싶은 것을 즐겁게, "[백준 15483번] 최소 편집", 2020.11.15, https://katfun.tistory.com/entry/%EB%B0%B1%EC%A4%80-15483%EB%B2%88-%EC%B5%9C%EC%86%8C-%ED%8E%B8%EC%A7%91

3) 겐지충 프로그래머, "알고리즘 - Dynamic Programming(동적 계획법)", 2021, https://hongjw1938.tistory.com/47

4) 소년코딩, "C++ 07.20 - 이중 포인터와 동적 다차원 배열 (Pointers to pointers and dynamic multidimensional arrays)", 2018.07.30, https://boycoding.tistory.com/212

5) j00hyun.log, "최소 편집 거리 (Minimum Edit Distance) 알고리즘", 2022.03.05, https://velog.io/@j00hyun/%EC%B5%9C%EC%86%8C-%ED%8E%B8%EC%A7%91-%EA%B1%B0%EB%A6%AC-Minimum-Edit-Distance-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98