알고리즘 문제풀이: 이진분류, 하노이

숫자 찾기

백준 1920

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
-> 정말 쉬운 문제이지만, 배운 것을 적용하기 위해서 이진 탐색 관련 알고리즘으로 구현하였다.

우선 처음에 작성한 코드

def binary_search(ordered_list, target):
    left, right = 0, len(ordered_list) - 1
    mid = (left + right) // 2

    if left == right:
        if ordered_list[left] == target:
            return True
        else:
            return False

    elif ordered_list[mid] > target:
        mid -= 1
        return binary_search(ordered_list[left:mid], target)
    elif ordered_list[mid] < target:
        left = mid + 1
        right += 1
        return binary_search(ordered_list[left:right], target)
    else:
        return True


data = [1, 2, 4, 7, 13, 17, 19]
t = 0

print(binary_search(data, t))

이 코드의 문제점은 인덱스값을 반환하지 않는 것에 있다. 그리고 재귀를 이용하기 위해 쓸데없는 슬라이스 객체를 만들어 내는 것 또한 문제다. 물론 문제에서는 참과 거짓만을 요구하였지만 탐색 과정에는 인덱스(위치) 값 도출이 중요하다고 생각한다. 정석으로는 while문을 이용하면 깔끔하다.

import bisect
import random

def binary_search(ordered_list, target):
    index = bisect.bisect_left(ordered_list, target)

    if index < len(ordered_list) and ordered_list[index] == target:
        return index
    else:
        return None

a = int(input())
list_a = list(input().split())
list_a.sort()

b = int(input())
list_b = list(input().split())

for i in range(b):
    print(binary_search(list_a, list_b[i]))

bisect를 이용한 탐색이다.

_index < len(ordered_list)_

개인적으로 이 부분이 가장 중요하다고 생각한다.

-> bisect_left란?

배열에서 주어진 값을 정렬된 상태로 삽입할 수 있는 index 출력

하노이 탑

백준 11729번

def hanoi_top(n):
    if n == 1:
        return 1
    else:
        return 2 * hanoi_top(n-1) + 1

num = 3
print(hanoi_top(num))

단순히 횟수만 구하는 코드이다. 다음은 문제의 요구에 맞게 변화를 주었다.

# 하노이 탑 문제
# 구하고자 하는 것 : 최소로 옮기는 것은 몇 번일까?

def hanoi_top(n, dstn, start=1):
    dict = [1, 2, 3]
    dict.remove(dstn)
    dict.remove(start)
    subdstn = dict[0]

    if n == 1:
        print("{} {}".format(start, dstn))
    else:
        hanoi_top(n-1, subdstn, start)
        print("{} {}".format(start, dstn))
        start = dstn
        hanoi_top(n-1, dstn, start=subdstn)


num_circle = int(input())
print(pow(2, num_circle)-1)
hanoi_top(num_circle, 3)

옮길 때마다 횟수를 누적시키는 것은 글로벌 변수를 어떻게 쓰는지 몰라서 구현 못했다. 하노이 경우의 수는 알고 있었기에 정답만 맞추자는 식으로 짰다. 다음은 모법 답안이다.

def hanoi(disks, src, dst, extra):
    if disks == 1:
        hanoi.count += 1
        print("{} {}".format(src, dst))
    else:
        hanoi(disks-1, src, extra, dst)
        hanoi.count += 1
        print("{} {}".format(src, dst))
        hanoi(disks-1, extra, dst, src)


hanoi.count = 0
num = int(input())
print(pow(2, num)-1)
hanoi(num, 1, 3, 2)

차이점은 백준 채점 기준 작동 시간이 200ms 줄었다는 것이고
문제는 횟수를 표시함에 있어서 모범답안을 그대로 가져왔지만 저 부분은 나중에 생각하기로 했다.
리스트를 이용해서 해결했지만 작동 시간이 2배나 느는 바람에 폐기했다.