[이것이 코딩테스트다] 21일차 - DP 문제풀이 | 못생긴 수, 편집 거리

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 8 다이나믹 프로그래밍

오늘 풀이한 문제 - 다이나믹 프로그래밍 예제

[이코테 381p] 못생긴 수

문제

못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미합니다.
다시 말해, 오직 2,3,5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴수라고 가정합니다. 따라서 못생긴 수들은 {1,2,3,4,5,6,8,9,10,12,15...}순으로 이어집니다. 이때 n번째 못생긴수를 찾는 프로그램을 작성하세요

입력 조건
1<= n <= 1,000

 

접근 방법

처음에는 문제이해를 잘못하고 1~1000까지중에 못생긴수를 고르는줄 알았다 ㅜㅜ

아 ㅋㅋ 입력조건 걸려있고 DP 재귀로도 된다했으니까 이건 재귀로 푸는거네 ㅋㅋ 문제 다양하고 좋네 생각하고 코드를 작성했다

재귀로 했더니 500부터 조금 버벅대기 시작,,,,, 문제 이해를 잘못한것이었음,, 되긴 된다,, 오래걸릴뿐

 

책의 점화식을 이해했다일단 못생긴 수 2,3,5를 리스트에 추가하고 리스트에 있는 못생긴수에 2,3,5를 곱한수를 추가한다-> 못생긴 수에 못생긴수를 곱해 추가하는 방식 

 

소스 코드

## 재귀 코드 *오래걸림
def ugly(num):
    if num % 2 == 0:
        num = ugly(num//2)
    if num % 3 == 0:
        num = ugly (num//3)
    if num %5 == 0:
        num = ugly(num //5) 
    if num == 1:
        return num
    else:
        return -1

n = int(input())
a = [1]
cnt = 1
i = 2
while cnt < n:
    num = ugly(i)
    if num == -1:
        pass
    else:
        cnt += 1
        a.append(i)
    i += 1
    if cnt == n:
        break
print (a[n-1])

## 책 풀이 보텀업 방식

ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블)
ugly[0] = 1 # 첫 번째 못생긴 수는 1

# 2배, 3배, 5배를 위한 인덱스
i2 = i3 = i5 = 0
# 처음에 곱셈 값을 초기화
next2, next3, next5 = 2, 3, 5

# 1부터 n까지의 못생긴 수들을 찾기
for l in range(1, n):
    # 가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[l] = min(next2, next3, next5)
    # 인덱스에 따라서 곱셈 결과를 증가
    if ugly[l] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    if ugly[l] == next3:
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[l] == next5:
        i5 += 1
        next5 = ugly[i5] * 5

# n번째 못생긴 수를 출력
print(ugly[n - 1])

[이코테 382p] 편집거리

문제

두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다.

• 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다.
• 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다.
• 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.

이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다.

 

접근 방법

이건 도저히 모르겠어서 검색을 했다

이러한 유형을 스트링 편집 거리(string edit distance) 알고리즘이라고 한다.

이는 두 문자열의 유사도를 측정하기 위해 사용되는 알고리즘으로 Levenshtein distance(LD)라고도 부른다

• 논문, 보고서 등의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용

이러한 문제는 각 문자를 행, 열에 담고 최소 편집거리를 테이블에 저장하며 계산한다 

 

현재 문자에서 A,B의 알파벳이 같다면 편집하지 않아도 되므로, 죄측 위 수를 그대로 대입

A,B 알파벳이 같지 않다면 좌측, 좌측 위, 바로 위 수 중 가장 작은 수에 +1한다 

좌측 = 삽입하는 경우

좌측 위 = 교체하는 경우

바로 위 = 삭제하는 경우

	0	s	a	t	u	r	d	a	y
0	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

맨 윗줄

0(공백)에서 0,s, sa, sat, satu, satur, saturd, saturda, satruday가 되는데 필요한 각 편집거리

 

소스 코드

str1 = "sunday"
str2 = "saturday"
 
n = len(str1)
m = len(str2)
dp = [[0] * (1+m) for _ in range(1+n)]
## 맨윗줄 (공백에서 str2까지)
for i in range(1, n+1):
    dp[i][0] = i

## 맨 왼쪽행 (공백에서 str1까지)
for j in range(1, m+1):
    dp[0][j] = j

for i in range(1, n+1):
    for j in range(1, m+1):
    	## 글자가 같을때
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1]
        ## 글자가 다를때 
        else:
            dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1

print(dp[n][m])

사실 완벽하게 이해는 못했다 ㅜ 아래 두개의 블로그를 참고했다!

https://lsh424.tistory.com/78

[알고리즘] DP - 스트링 편집 거리(문자열 유사도 측정)

https://bgspro.tistory.com/36

편집거리 알고리즘 (Python)