[Python] 편집거리 알고리즘

편집거리 알고리즘은 두 문자열의 유사도를 판단하는 알고리즘이다.

수정, 삽입, 삭제 기능이 있다고 할 때 몇 번의 동작이 필요한지 측정한다. 문자열 내에서 위치 변환 같은 기능이 없다.

2차원 메모이제이션 배열을 사용하는 Dynamic Programming의 한 종류이다.

편집거리 알고리즘의 규칙

1. str1에서 i번째 문자와 str2에서 j번째 문자를 서로 비교한다.
2. 두 문자가 같으면 dp[i-1][j-1]의 값을 그대로 가져온다.
3. 두 문자가 다르면 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 최소값에 1을 더해서 dp[i][j]에 저장

설명

편집 거리를 계산할 때 기준을 먼저 잡아야 한다. 왼쪽 문자열에서 위쪽 문자열로 변환한다고 기준을 잡겠다. 왼 쪽의 H와 위 쪽의 H를 비교할 때는 'PH' 가 'PYTH' 가 되기 위해서 연산이 몇 번 필요한 지 확인하는 것이다.

초기 상태는 위와 같다. 첫 행으로 설명을 하자면 빈 문자열{} 이 {}, P, PY, PYT, ... 로 바뀌기 위해서 몇 번의 연산이 필요한 지 나타내는 것이다. {}에서 {}이 되려면 아무 연산이 필요 없으므로 0, PYT가 되려면 P, Y, T를 각각 삽입해야 하므로 3이 된다.

'PH'가 'PYTH'가 되기 위한 연산의 수는 'P'를 'PYT'로 바꾸는 연산의 수와 같다. 두 문자열에서 똑같은 'H'를 붙이는 것이기 때문이다.

'O'와 'H'를 비교한 경우를 생각해보자.

1. A의 경우를 보면 'PH'에서 'PYT'로 2번의 연산으로 변환이 되었다고 생각한다. 다음 줄로 오면서 'O'가 더해지고 'PYTO'가 된 상황이다. 이 때는 'O'를 'H'로 수정 연산을 하면 된다.
2. B의 경우 'PH'를 'PYTH'로 2번의 연산으로 변환이 되었다고 생각한다. 마찬가지로 다음 줄로 넘어가면서 'O'가 더해지고 'PYTHO'가 된 상황이다. 이 경우에는 'O'를 삭제 연산을 하게 되면 'PYTH'로 만들 수 있다.
3. C의 경우 'PHO'를 'PYT'로 2번의 연산으로 변환이 되었다고 생각한다. 이 경우에는 다음 줄이 되는 것이 아니므로 'O'가 더해지는 것은 아니다. 'PYT'에서 'H'를 삽입하는 연산을 하게 되면 'PYTH'로 만들 수 있다.

각각의 횟수는 2번의 연산에 한 번 더 연산을 하는 과정이 필요하므로 3번 연산을 하면 'PHO'를 'PYTH'로 바꿀 수 있다. 우리는 최소 편집 거리를 찾기 때문에 A, B, C 과정을 한 후 최소값을 dp 테이블에 넣어주면 된다.

위에서 같은 문자끼리 비교하는 경우에는 A의 연산의 특수한 경우로 생각하면 된다. 수정 연산을 생각할 때 두 문자가 같으므로 수정을 굳이 안 해도 되는 경우라고 생각한다. 그리고 dp[i-1][j-1]은 dp[i-1][j] + 1, dp[i][j-1] + 1과 비교했을 때 최솟값을 가지는 것이 보장된다.

결과

모든 계산이 끝난 후의 결과는 그림과 같다. 이 후에 우리는 dp[-1][-1]을 계산하면 최소 편집 거리를 구할 수 있다. 최소 편집 거리를 만드는 경로는 여러가지가 될 수 있다.

CODE

def edit_dist(str1, str2):
    dp = [[0] * (len(str2)+1) for _ in range(len(str1) + 1)]
    for i in range(1, len(str1)+1):
        dp[i][0] = i
    for j in range(1, len(str2)+1):
        dp[0][j] = j

    for i in range(1, len(str1)+1):
        for j in range(1, len(str2)+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]

            else:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

    return dp[-1][-1]


print(edit_dist('PYTHON', 'PHOTO'))     # 4

[Python] 소수 판별 알고리즘

난이도가 낮은 알고리즘 문제 중에서 자주 나오는 문제가 소수 판별 문제이다.

소수 : 1과 자기 자신 이외에 약수를 가지지 않는 2 이상의 자연수

소수를 판별하는 방법은 크게 두 가지로 나뉜다.

반복문 사용

첫 번째 방법은 반복문 사용이다. 자연수 n이 소수인지 판별하기 위해서 2부터 \( [\sqrt{n}] \)까지 나누었을 때 나머지가 0이 있는지 확인하는 방법이다.

Code

from math import sqrt

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

sqrt(n)까지만 확인하는 이유는 \( \sqrt{n} \) 보다 큰 약수는 이미 작은 약수를 확인하면서 확인하기 때문이다. 예를 들어서 n이 20인 경우 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 이지만 9, 12, 18은 4, 3, 2와 한쌍이기 때문에 6까지만 검사하게 되면 9, 12, 18이 36의 약수인 것을 알 수 있다.

에라토스테네스의 체

아스토스테네스의 체는 여러 개의 소수를 판별할 때 유용하다. 또는 큰 수에 대해서 소수 여부를 판별할 때 시간복잡도가 많이 개선된다. 크기가 n인 배열을 만든 후에 처음 두 칸은 False로 설정하고 이후의 배열은 모두 True로 초기화해준다. 이후 배열을 한 번 순회하면서 소수를 찾고 소수의 배수들을 모두 False로 변환해준다.

Code

def is_prime(n):
    prime = [False, False, True] + [True, False] * ( (n - 1) // 2)
    # 2를 제외한 모든 짝수는 소수가 아님
    for i in range(3, n+1, 2):
        if prime[i]:
            for j in range(i*i, n+1, 2*i):
                prime[j] = False

    return prime[n]

코드의 베이스라인은 위와 같다. 소수 판별 문제에서는 어떤 수가 소수인지 판별하는 문제도 있지만 n이하의 자연수 중 소수가 몇 개인지, 어떤 수들인지를 알기 위한 문제가 많다. j에 대한 for문에서 범위가 i * i 부터 n + 1까지 간격은 2 * i로 큰 수들을 False로 변환한다.

i * i부터 시작하는 이유는 i * (i - 2), i * (i - 4), ...은 i - 2번 째 반복문에서 (i - 2) * (i - 2) + 2 * (i - 2)가 되어서 한 번 방문을 했거나 또는 소수가 아닌 수의 배수이기 때문에 방문할 필요가 없다.

2 * i씩 건너띄는 이유는 간단하다. 홀수에 짝수를 더하면 홀수이기 때문이다. 짝수는 2를 제외하고는 소수가 아니기 때문에 굳이 방문할 필요가 없다.

n = 1000000
prime = [False, False, True] + [True, False] * ((n - 1) // 2)
prime_number = [2]
for i in range(3, n+1, 2):
    if prime[i]:
        if i > 1000:                    
            prime_number.append(i)
        for j in range(i*i, n+1, 2*i):    # i * i 이하의 수는 i 전에 한 번씩 검사됨
            prime[j] = False

print(prime_number)        # 1,000과 1,000,000 사이의 소수
print(len(prime_number))# 1,000과 1,000,000 사이 소수의 개수

위에서 처럼 "1,000보다 큰 소수를 모두 구하여라." 같은 문제를 풀 때 에라토스테네스의 체가 유용하게 쓰이고 많은 알고리즘 문제를 해결할 때 에라토스테네스의 체를 사용하다.
하지만 무조건적으로 에라토스 테네스의 체가 좋다고 얘기할 순 없다. n이 소수인지 판별하기 위해서 크기가 n+1인 리스트를 생성해야 한다. 이론상 O(Nlog(logN))이라고 되어 있고 반복문을 사용할 때는 O(sqrt(N))이다.

1000000007 과 같은 큰 소수가 소수인지 판별하는 데에는 반복문을 사용하는 것이 훨씬 빠르다는 얘기다.

Code

import time
from math import sqrt


def is_prime(n):
    prime = [False, False] + [True] * (n - 1)
    for i in range(3, int(sqrt(n))+1, 2):
        if prime[i]:
            for j in range(i*i, n+1, 2*i):
                prime[j] = False

    return prime[n]


def is_prime2(n):
    if n % 2 == 0:
        return False
    for i in range(3, int(sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True


start = time.time()
is_prime(1000000007)        # 에라토스테네스의 체
print(time.time() - start)

start = time.time()
is_prime2(1000000007)       # 반복문 사용
print(time.time() - start)

에라토스테네스의 체도 sqrt(n)까지만 해서 n이 소수인지 판별하도록 했음에도 불구하고 출력 결과에서 보면 많이 차이가 나는 것을 알 수 있다.

결론

에라토스테네스의 체를 사용하게 되면 여러 개의 소수를 한 번에 구할 수 있고, 한 번 구해놓고 나면 O(1)로도 판별이 가능하기 때문에 여러 개의 소수를 구하는 경우에는 꼭 에라토스테네스의 체를 사용하는 것이 좋다. 입력이 하나이고 그 수가 소수인지 판별할 때는 그냥 간단하게 반복문을 사용하는 것이 좋다.

리스트 함수 정리

이번 포스팅은 파이썬 기본 리스트의 내장 함수들을 정리했습니다. 리스트는 삽입, 삭제, 인덱스 위치 찾기, 원하는 원소 갯수 찾기, 정렬 등이 기본적으로 제공됩니다.

>>> 구문이 있는 명령어는 ide상에서의 실행이 아닌 파이썬 내에서 실행 코드입니다.

삽입

1. append()

A.append(x)는 리스트 A 끝에 원소 x를 추가한다. A[len(A):] = [x] 로 사용도 가능하다. 시간복잡도는 O(1)이다.

>>> A = [1, 2, 3]
>>> A.append(4)
>>> A
[1, 2, 3, 4]
>>> A[len(A):] = [5]
>>> A
[1, 2, 3, 4, 5]

2. extend()

A.extend(iter)는 iterable한 항목 iter를 리스트 A에 추가한다. 여러 개의 리스트를 서로 연결할 때 사용된다. 혹은 A += iter로 사용이 가능하다.

>>>A = [1, 2, 3]
>>>B = [4, 5, 6]
>>>A.extend[B]
A
[1, 2, 3, 4, 5, 6]
>>>A += [7, 8, 9]
A
[1, 2, 3, 4, 5, 6, 7, 8, 9]

3. insert()

A.insert(i, x)는 리스트 A의 i 위치에 x를 삽입하는 함수이다. i 이후의 모든 원소들을 한 칸씩 옮겨야 하기 때문에 시간복잡도는 O(N)이 된다.(N은 리스트의 길이)

>>> A = [1, 2, 3]
>>> A.insert(1, 4)
>>> A
[1, 4, 2, 3]

원소 제거

1. remove()

A.remove(x)는 리스트의 원소 x를 제거한다. x는 원소의 인덱스가 아닌 원소의 값이다. x가 존재하지 않으면 ValueError가 발생한다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 3]
>>> A.remove(2)
>>> A
[1, 3]

2. pop()

A.pop(i)는 리스트의 i번째 원소를 제거하면서 해당 원소를 반환한다. remove와는 다르게 위치에 있는 값을 제거하는 함수이고 i를 지정하지 않으면 리스트의 마지막 원소를 제거하면서 반환한다. i를 지정하지 않은 경우 시간복잡도는 O(1)이고 i를 지정한 경우 시간복잡도가 O(N)이 된다.

>>> A = [1, 2, 3]
>>> A.pop(1)
2
>>> A
[1, 3]
>>> A.pop()
3
>>> A
[1]

3. del문

del문은 pop처럼 인덱스를 지정해서 항목을 삭제한다. pop과 다른 점은 삭제한 원소를 반환하지 않는 것이다. 리스트 슬라이싱을 통해서 여러개의 원소를 한 번에 삭제도 가능하다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 3, 4, 5, 6]
>>> del A[2]
>>> A
[1, 2, 4, 5, 6]
>>> del A[1:3]
>>> A
[1, 5, 6]

이외 함수들

index()

A.index(x)는 리스트 A에서 원소 x의 위치를 반환한다. 이 때 주의할 점은 리스트 A에 x가 여러 개가 있다면 가장 앞에 있는 인덱스를 반환하다. 시간 복잡도는 리스트를 순차적으로 모두 확인하므로 O(N)이 된다.

>>> A = [1, 2, 3, 4, 5]
>>> A.index(3)
2

count()

A.count(x)는 리스트 A에 x인 값을 갖는 원소의 개수를 반환한다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 2, 3, 3, 3]
>>> A.count(3)
3

sort()

A.sort(key, reverse)는 리스트 A를 값을 기준으로 오름차순으로 정렬해준다. 시간복잡도는 O(NlogN)이고 내림차순으로 정리하려면 reverse=True를 인자로 주어야 한다. 원하는 기준으로 정렬을 해주고 싶다면 key와 lambda를 사용하여 규칙을 정해주어야 한다.

>>> A = [4, 1, 3, 2]
>>> A.sort()
>>> A
[1, 2, 3, 4]
>>> A.sort(reverse=True)
>>> A
[4, 3, 2, 1]

reverse()

A.reverse()는 리스트 A의 원소들을 반전시켜서 다시 리스트 A에 저장한다. list[::-1]을 하는 것과 같다.

>>> A = [1, 2, 3, 4, 5]
>>> A.reverse()
>>> A
[5, 4, 3, 2, 1]

[Python] 자료형 - (3) 리스트

리스트는 길게 이어진 상자라고 생각하면 된다. 우리는 리스트 안에 숫자, 문자열, 새롭게 정의한 객체 등 다양한 자료형을 넣을 수 있는 상자이다.

리스트의 생성

a = []
b = list()
c = [1, 2, 3]
d = ["Hello", "World"]
e = [1, 2, "Hello", "World"]
f = [[1, 2], ["Hello", "World"]]

a와 b리스트는 빈 리스트를 생성해주는 것이다. e 리스트 처럼 상자마다 다른 자료형을 삽입할 수도 있고 f 리스트처럼 리스트를 삽입할 수도 있다.

리스트의 사용

리스트에 보관된 데이터를 어떻게 사용할 것인가

인덱싱

리스트 명[위치값]의 형태로 리스트 안의 원소에 접근이 가능하다. 이것을 인덱싱이라 한다. 리스트는 0번째 칸부터 저장이 되는 것을 주의해야 한다.

a = [10, 20, 30, 40]
print(a[0])
print(a[3])
print(a[-1])
print(a[4])

인덱스 값으로 음수값을 주면 뒤에서부터 원소를 접근한다. 리스트의 크기는 4이지만 리스트의 마지막 번호는 3이기 때문에 a[4]를 사용하면 에러가 난다. 리스트의 범위를 벗어난 접근에 대한 에러다.

슬라이싱

리스트는 꼭 원소를 하나씩 접근할 필요가 없다. 내가 필요한 부분만 잘라서 리스트를 사용하고 싶을 때는 슬라이싱을 사용한다. 리스트를 토막낸다고 생각하면 된다.
기본적인 형태는 리스트 명[시작 인덱스: 끝나는 인덱스 + 1] 과 같이 사용된다. 시작 인덱스와 마지막 인덱스는 생략이 가능하고 그런 경우 끝에서 시작 또는 끝에서 끝남을 의미한다.

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
b = a[:5]
c = a[5:]
d = a[2:7]
print(a)
print(b)
print(c)
print(d)

사용을 할 때는 : 뒤의 값 전까지 슬라이싱을 하는 것을 명심해야 한다.

리스트의 연산

리스트 역시 문자열처럼 리스트끼리 더하기와 곱하기 연산이 가능하다.

a = ['a', 'b', 'c']
b = ['d', 'e', 'f']
print(a + b)
print(a * 3)

수정, 삭제

a = [1, 2, 3]
a[2] = 4
print(a)

리스트는 직접적으로 값을 바꿀 수 있는 mutable 자료형이다.

a = [1, 2, 3]
del a[1]
print(a)

del 함수는 파이썬의 기본 함수로 객체를 삭제하는 함수이다.

문자열이란

문자열(String)이란 문자를 나열해 놓은 것을 의미한다. 문자는 a, b, c 같은 알파벳과, 가나다 같은 한글, 1,2,3 같은 숫자,!@#같은 특수문자 등 유니코드 내에 문자를 의미한다.

"Hello World"
"123456789"
"010-1234-5678"
"!@#$"

문자열의 표현

파이썬에서는 문자열을 쌍따옴표"로도 나타낼 수 있지만 작은 따옴표'로 나타낼 수도 있다.

str1 = "abc"
str2 = 'abc'
print(True if str1 == str2 else False)

위 예제의 print함수는 두 문자열이 같으면 True를 다르면 False를 출력하는 함수입니다. 두 문자열은 그 내부적으로는 서로 같습니다. 파이썬 내부에서는 기본적으로 문자열을 작은 따옴표로 묶여 있는 것으로 표시된다.

위의 방법 외에도 여러 줄의 문자열을 위해서 여러 줄의 문자열을 한 번에 나타내는 방법이 있다.
큰 따옴표나 작은 따옴표를 3개를 사용해서 나타낸다.
첫번째 줄

str3 = """첫 번째 줄
두 번째 줄
세 번째 줄
"""
print(str3)

이스케이프 문자

이스케이프 문자란 줄바꿈, 띄워쓰기 등 여러 기능을 위해 미리 정해놓은 문자 집합이다..
가장 자주 볼 수 있는 문자는 \n, \t, \\이 있다.

str4 = "첫번째\n두번째\n세번째"
str5 = "1\t2\t3\t4"
str6 = "8\t9\t10\t11"
print(str4)
print(str5)
print(str6)

문자열의 연산

문자열 더하기(Concatenation)

문자열은 문자열끼리 더하기가 가능하다. 문자열의 덧셈은 각 요소를 더하는 것이 아니라 문자열 뒤에 문자열을 추가한다고 생각하면 된다.

str1 = "Hello"
str2 = " World"
str3 = str1 + str2
print(str3)

문자열 곱셈(반복)

문자열의 곱셈은 곱하는 수만큼의 반복을 의미한다.

str1 = 'Hello '
str2 = str1 * 3
print(str2)

2 * 3 = 2 + 2 + 2 인 것을 생각해보면 문자열의 곱셈이 의미하는 것을 알 수 있다. str2 = str1 + str1 + str1이므로 "Hello "라는 문자열을 3번 이어붙인 것이다.

문자열의 기본 함수에 대해서는 다음에 포스팅하겠습니다.