더디지만... 꾸준히...

1. 알고리즘

"C로 배우는 알고리즘"은다음과 같이 알고리즘을 표현합니다.

1. 정수 N을 입력받는다.

2. 정수 i에 2를 대입한다.

2.1 N이 i로 나누어 떨어지는가? (% 연산자를 사용)

2.1.1 나누어 떨어지면 소수가 아니다. 끝

2.2 i를 하나 증가시킨다.

2.3 i가 N보다 작은가?

2.3.1 작으면 2.1로 돌아간다.

3. 정수 N은 소수이다. 끝

2. 동작 코드

이를 코드를 작성하였습니다.

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

개선을 위해서 모든 숫자에 대해서 검사하지 않고, sqrt()를 이용해서 범위를 줄였습니다.

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

3. 실행 코드

실행 코드는 다음과 같이 작성했습니다. ("C로 배우는 알고리즘" 리스트 1-5 : PRIME2.C에 대응)

def print_results(i, n, r, t):
    if r:
        print('Test case', i, ":", n, "is prime in", t)
    else:
        print('Test case', i, ":", n, "is not prime in", t)


# Main function
LOOP = 10000

print("Test input number is prime or not")
print("Input 0 to end program")

while True:
    print()
    input_data = int(input("Input number to test -> "))

    if input_data < 0:
        print("Please input positive integer")

    if input_data == 0:
        print("End of program")
        break

    start_time = time.process_time()
    for i in range(0, LOOP):
        test_result = is_prime(input_data)
    end_time = time.process_time()
    print_results(1, input_data, test_result, end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        test_result = is_prime2(input_data)
    end_time = time.process_time()
    print_results(2, input_data, test_result, end_time-start_time)

4. Tips

1. is_prime2()에서 for loop의 range에 +1을 사용해야 합니다.

5. 예제 코드

1. 알고리즘

최대공약수를 찾기 위해 유클리드 알고리즘을 사용합니다. "C로 배우는 알고리즘"에서 유클리드의 알고리즘을 말로 표현하면 다음과 같다고 합니다. (내용을 조금 바꿨습니다. 인터넷에서 찾은 링크를 참고해도 좋겠습니다.)

1. 두 정수 u와 v를 입력 받는다.

2. v가 u보다 크다면, v와 u의 값을 교환한다.

3. u-v를 u에 저장한다.

4. u가 0인가? 아니면 2로 돌아간다. u가 0이면 v가 최대 공약수이다.

2. 동작 코드

아래와 같이 Python으로 작성했습니다.

# Minus methods
def get_gcd(u, v):
    while u != 0:
        if u < v:
            t = u
            u = v
            v = t
        u = u - v
    return v

단순히 C를 Python으로 옮긴 것입니다.

뺄셈으로는 속도가 느려서, modulus 연산자를 이용해서 속도를 개선합니다.

# Modulus methods
def gcd_modulus(u, v):
    while v != 0:
        t = u % v
        u = v
        v = t
    return u

재귀호출을 이용한 코드는 아래와 같습니다.

# Recursion methods
def gcd_recursion(u, v):
    if v == 0:
        return u
    else:
        return gcd_recursion(v, u % v)

3. 실행 코드

두 수를 입력 받아서 위의 함수들을 호출하는 실행 코드는 다음과 같이 작성했습니다. ("C로 배우는 알고리즘" 리스트 1-3 : EUCLID2.C에 대응)

# Main function
LOOP = 10000

print("Input 0 to end program")

while True:
    print()
    first_input = int(input("Input first integer : "))
    second_input = int(input("Input second integer : "))

    if first_input < 0 or second_input < 0:
        print("Please input positive integer")

    if first_input == 0 or second_input == 0:
        print("End of program")
        break

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = get_gcd(first_input, second_input)
    end_time = time.process_time()
    print("Minus methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = gcd_modulus(first_input, second_input)
    end_time = time.process_time()
    print("Modulus methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = gcd_recursion(first_input, second_input)
    end_time = time.process_time()
    print("Recursion methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

4. Tips

1. Python에서 사용자에게 입력을 받기 위해서 input()을 사용했으며, input()은 'str'을 입력 받기 때문에 int()를 이용해서 integer로 변환했습니다.

2. 시간 측정을 위해서는 Python의 time 모듈에서 process_time()을 사용하였습니다.

5. 코드

책장 한 구석을 차지하고 있는 "C로 배우는 알고리즘" 을 보며 다시 한번 공부해 봐야지 생각만 계속하다, 어차피 새로 한다면 Python으로 코드를 작성해 보면 어떨까라는 생각을 했습니다. 아직 Python 초보자라 필요한 것들은 인터넷에서 찾아야 하고, 작성된 코드는 최적화되지도, 예쁘지도 않고, 많이 부족하겠지만 재미있을 것 같습니다. 대부분은 C 코드를 그대로 옮기는 것이 되겠지만 말입니다.

Python은 3.6.5를, IDE로는 Pycharm community version을 사용했습니다. 설치 방법은 인터넷에서 쉽게 찾을 수 있으니 따로 적지 않습니다.

기본적으로 "C로 배우는 알고리즘"를 그대로 따라할 예정입니다. 작성하면서 이용한 출처는 기본적으로 밝히는 것을 원칙으로 하겠지만, 혹시 실수가 있다면 알려 주십시오. 시작해 봅니다.