> 6010. 정수 1개 입력받아 int로 변환하여 출력하기 ←

n = int(input())
print(n)

파이썬에서의 모든 입력은 한 줄의 str 클래스로 입력된다. 원하는 형태에서의 계산을 위해서는 반드시 형변환이 필요하다.
파이썬에는 char형이 따로 없다. chr함수가 char형으로 변환해준다고 나와있지만 정확히는 크기가 1인 str 클래스로 변환해주는 함수이다. 기본적으로 int는 28bit, str은 50bit의 크기를 가지고 사이즈가 커지면서 거의 무한하게(메모리 크기만큼) 커질 수 있다.

> 6011. 실수 1개 입력받아 변환하여 출력하기←

f = float(input())
print(f)

파이썬에서는 float함수를 사용하면 문자열로 나타내어진 숫자를 실수로 변환할 수 있다.

> 6012. 정수 2개 입력받아 그대로 출력하기1 ←

a = int(input())
b = int(input())
print(a)
print(b)

input함수는 개행문자까지 입력을 받기 때문에 두 줄로 입력되는 입력에 대해서 두 번 input을 해주어야 한다. print도 마찬가지로 default로 줄바꿈이 되기 때문에 두 번 함수를 실행해 주어야 한다.
만약 출력을 한 번만 실행을 하고 싶다면 다음과 같은 방법이 존재한다.

print(a, b, sep='\n')

input의 경우에는 input().split('\n')으로 줄바꿈을 나누어서 입력을 받지 못하므로 한 번씩 사용해주어야 한다.

> 6013. 문자 2개 입력받아 순서 바꿔 출력하기1 ←

a = input()
b = input()
print(b)
print(a)

> 6014. 실수 1개 입력받아 3번 출력하기 ←

f = float(input())
print(f, f, f, sep='\n')

같은 값을 3번 출력하는 방법은 다양하다. print를 3번 사용해도 되고 for문 같은 반복문을 사용해도 된다.

> 6015. 정수 2개 입력받아 그대로 출력하기2 ←

a, b = map(int, input().split())
print(a, b, sep='\n')

input().split()함수에서는 공백을 default로 문자열을 나누어서 리스트에 저장한다. 따라서 input().split()은 list를 반환한다.
map함수의 첫 번째 인자는 하나의 함수이고 두 번째 인자는 리스트나 튜플같이 iterable한 자료형이다. map은 첫 번째 인자로 들어온 함수를 두 번째 인자의 각각의 요소들에 적용시키는 함수이다.
위에서는 input().split()의 결과로 ['1', '2']가 map의 두 번째 인자가 될 것이고 '1'과 '2'에 각각 int를 적용하여 a, b에 저장한다.

> 6016. 문자 2개 입력받아 순서 바꿔 출력하기2 ←

a, b = input().split()
print(b, a)

print함수에 여러 개의 입력이 있는 경우 default값으로 두 값 사이에 공백이 생기도록 출력한다.

> 6017. 문장 1개 입력받아 3번 출력하기 ←

s = input()
print(s, s, s)

> 6018. 시간 입력받아 그대로 출력하기 ←

h, m = input().split(':')
print(h, m, sep=':')

split함수에 ':'를 입력으로 넣게 되면 ':'를 기준으로 문자를 나누어서 리스트에 저장한다.

> 6019. 연월일 입력받아 순서 바꿔 출력하기 ←

y, m, d = input().split('.')
print(d, m, y, sep='-')

> 6020. 주민번호 입력받아 형태 바꿔 출력하기 ←

front, back = input().split('-')
print(front, back, sep='')

[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)로도 판별이 가능하기 때문에 여러 개의 소수를 구하는 경우에는 꼭 에라토스테네스의 체를 사용하는 것이 좋다. 입력이 하나이고 그 수가 소수인지 판별할 때는 그냥 간단하게 반복문을 사용하는 것이 좋다.

[백준][파이썬] 23080번 - 스키테일 암호

문제 번호 : 23080번 - 스키테일 암호
문제 출처 : https://www.acmicpc.net/problem/23080

Code

k = int(input())
s = input()

answer = ''
for i in range(0, len(s), k):
    answer += s[i]

print(answer)

Idea

막대 둘레에 따라서 문자열을 출력하면 되는 간단한 문제이다.

s\[k\*0\], s\[k\*1\], s\[k\*2\], ... 순으로 출력하면 되기 때문에 range(시작, 끝, 간격) 을 이용해서 k마다 문자를 출력했다.

[Python] 진수 변환

코딩테스트 문제들을 풀다보면 진수 변환을 하는 문제가 자주 등장한다. 오늘은 진수 변환을 하는 방법 2가지를 소개한다.

10 진수 -> n 진수

10진수를 n 진수로 바꾸는 것은 학생 때 배웠던 2진법 변환방법을 코드로 구현한 것과 같다.

바꾸고 싶은 수를 n으로 나누고 나머지와 몫을 확인한다. 몫이 0이 되면 나머지들을 역순으로 문자열에 추가한다.

1. 반복문 사용

def convert_iter(num, base):
    power = 0
    tmp = ''
    while num:
        tmp = str(num%base) + tmp
        num //= base
    return tmp

이 방법으로는 10진수까지의 변환만 가능하다.

2. 재귀함수 사용

import string

def convert_recur(num, base):
    number = string.digits + string.ascii_uppercase
    q, r = divmod(num, base)
    return convert_recur(q, base) + number[r] if q else number[r]

string.digits = '0123456789'이고 string.ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'이다. 둘 다 문자열이고 따라서 우리가 구하고자 하는 수가 x일 때 number[x] = 'x'로 11 진수 이상의 진법도 표현 가능하다.

n 진수 -> 10진수

n 진수를 10진수로 바꾸는 방법은 굉장히 간단하다. 내장 int함수에 구현되어 있다. 사용 방법은 다음과 같다.

base_2 = '10011010010'
base_8 = '2322'
base_16 = '4d2'

print(int(base_2, 2))    # 1234
print(int(base_8, 8))    # 1234
print(int(base-16, 16)) # 1234

int(number_string, base)로 나타낼 수 있다. 첫 번째 인자는 무조건 문자열이어야 하고 base가 달라지면 값도 달라진다. 그리고 만약 문자열이 '1234'인데 2진법으로 나타낸 수라고 하는 것은 에러가 발생한다.

이외의 방법들

내장 함수 사용

2진법, 8진법, 16진법은 파이썬 내장 함수로 진수 변환이 가능하다.

h = hex(1234)
o = oct(1234)
b = bin(1234)

print(h)    # '0x4d2'
print(o)    # '0o2322'
print(b)    # '0b10011010010'
# 다시 10진수로 변환하기
print(int(h, 16)) # 1234
print(int(o, 8)) # 1234
print(int(b, 2)) # 1234

변환 시간 측정

import time

start = time.time()
for _ in range(100000):
    bin(1234)
print("내장 함수 시간 : {}".format(time.time()-start))

start = time.time()
for _ in range(100000):
    convert_iter(1234, 2)
print("반복 함수 시간 : {}".format(time.time()-start))

start = time.time()
for _ in range(100000):
    convert_recur(1234, 2)
print("재귀 함수 시간 : {}".format(time.time()-start))

확실히 파이썬은 내장 함수를 안다면 무조건 내장함수를 쓰는 것이 효율적이다. 재귀 함수가 오히려 더 효율이 좋을 거라 생각했는데 반복 함수를 사용할 때가 더 효율이 좋다. 시간 복잡도의 차이보다 함수 호출에서 시간이 조금 더 걸려서인 듯 하다.