일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 디자인강의
- 구현
- UXUIPrimary
- 오픈패스
- 백준
- 백엔드개발자
- UXUI기초정복
- KDT
- 문자열
- 국비지원교육
- OPENPATH
- js
- 부트캠프
- 디자인챌린지
- 코드스테이츠
- baekjoon
- 기초
- javascript
- knu
- 오픈챌린지
- 디자인교육
- UXUI챌린지
- Be
- 백엔드 부트캠프
- 직무역량캠프
- 환급챌린지
- 국비지원
- 패스트캠퍼스
- 국비지원취업
- 내일배움카드
- Today
- Total
군만두의 IT 공부 일지
[백준] 15483번: 최소 편집 (C++) 본문
✅문제: 15483번
15483번: 최소 편집
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
www.acmicpc.net
📌개념정리
(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;
}
- 두 문자열 A와 B를 입력받음.
- A와 B의 길이에 1을 더한 크기의 2차원 동적 배열 dp를 선언하고 메모리를 할당함. 여기서 dp[i][j]는 A의 첫 번째 문자부터 i번째 문자까지의 부분 문자열을 B의 첫 번째 문자부터 j번째 문자까지의 부분 문자열로 변환하는 데 필요한 최소 연산의 수를 나타냄.
- dp 배열의 첫 번째 행과 열을 초기화함.
- 이중 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]) 중에서 최소 비용을 선택함.
- 배열의 마지막 셀에는 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
'코딩테스트 > 백준' 카테고리의 다른 글
[백준] 3273번: 두 수의 합 (파이썬) (0) | 2024.04.10 |
---|---|
[백준] 18429번: 근손실 (파이썬) (0) | 2024.04.09 |
[백준] 4949번: 균형잡힌 세상 (파이썬) (0) | 2024.03.12 |
[백준] 25083번: 새싹 (파이썬) (0) | 2022.12.29 |
[백준] 1000번: A+B (파이썬) (0) | 2022.12.28 |