방구석프로의 이야기

개념

편집거리 알고리즘이란 두 문자열이 주어졌을 때 문자열을 비교하는 알고리즘입니다. 여기서 비교한다는 것은 삽입, 삭제, 교체 즉 3가지의 액션이 주어졌을 때 두 문자열이 같게 하기 위해 취할 수 있는 액션의 최솟값을 구하는 알고리즘이라는 것입니다. 예를 들어서 str1 = python, str2 = pyytthon 라 가정하고 문제를 해결해보겠습니다. 이 알고리즘은 다이내믹 프로그래밍 즉 dp의 일종이기 때문에 dp 테이블의 형태로 이차원 리스트를 구현하면 쉽게 해결할 수 있습니다. 

다음의 표를 봅시다.

먼저 str1을 행으로 str2를 열로 넣고 각 행과 열에 숫자를 넣은 상태입니다. 여기서 만약 p, p를 비교하는 경우 즉 2행 2열의 경우는 두 문자가 같기 때문에 좌측 위의 0이 그대로 2행 2열에 대입됩니다.

그러나 p, y와 같은 두 문자열이 다른 경우 즉 2행 3열의 경우 좌측, 좌측 위, 위 의 3가지 경우 중 최솟값에 1을 더한 값이 대입됩니다. 여기서는 최솟값이 2행 2열 즉 0 이기 때문에 0에 1을 더한 1이 대입됩니다. 그 과정을 전부 다 하면 다음과 같습니다.

이 표의 최우 측 하단의 값이 두 문자열을 비교한 후 서로 같게 하는 최소의 액션의 수입니다. python에 y뒤에 혹은 y앞에 y를 삽입하는 1번의 과정으로 pyyhton을 만들 수 있기 때문입니다.

소스코드

개념

가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차순으로 가장 긴 증가하는 부분의 숫자가 몇 개가 존재하는지를 카운트하는 알고리즘입니다. 예시와 함께 알아보겠습니다.

array = [10, 20, 10, 30, 20, 50]일때 가장 긴 증가하는 부분의 숫자를 출력하시오 라는 문제가 있다고 가정하면 10, 20, 30, 50 즉 4가 정답입니다. 이중 for문이 있다면 쉽게 해결할 수 있습니다. array의 길이만큼의 리스트 dp를 1로 초기화한 후 이중 for문으로 조회하면서 해당하는 값에 1을 더한 값과 원래 값의 max값을 넣어주면 되는 것입니다.

소스코드는 다음과 같습니다.

소스코드