알고리즘49 알고리즘 - 이진 삽입 정렬 단순 삽입 정렬은 배열 원소 수가 많이지면 비교, 교환 비용이 커지는데 이진 삽입 정렬을 사용하면 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사해서 비용을 줄일 수 있습니다. def binary_insertion_sort(a): n = len(a) for i in range(1, n): key = a[i] pl = 0 pr = i - 1 while True: pc = (pl + pr) // 2 if a[pc] == key: break elif a[pc] pr: break if pl > a[0] = 4 이렇게 교환이 됩니다. 이렇게 검색 범위를 축소하고 가운데 값을 기준으로 검색 범위를 좁혀 나가는 것이 이진 삽.. 2020. 11. 23. 알고리즘 - 단순 삽입 정렬 4 2 1 7 9 6 오름차순으로 정렬을 할 때, 위 배열에서 현재 원소 2를 보고있다면 2는 4보다 앞에 있어야 하기 때문에 2 4 1 7 9 6 이렇게 앞으로 한 칸 옮겨주면 됩니다. 원소 1을 올기면 4와 2를 지나쳐 맨 앞으로 옮겨줍니다. 1 2 4 7 9 6 이렇게 가장 작은 원소를 정하는 것이 아닌, 현재 보고 있는 원소를 알맞은 위치로 옮기는 것을 단순 삽입 정렬이라고 합니다. def insertion_sort(a) -> None: n = len(a) for i in range(1, n): j = i tmp = a[i] while j > 0 and a[j - 1] > tmp: a[j] = a[j-1] j -= 1 a[j] = tmp print('단순 삽입 정렬') num = int(input.. 2020. 11. 23. 알고리즘 - 재귀 알고리즘(1) 재귀는 어떠한 작업을 할 때, 자기 자신을 포함 및 사용하는 경우를 말합니다. 재귀를 사용하는 대표적인 예인 팩토리얼 문제를 보겠습니다. def factorial(n: int): if n > 0: return n * factorial(n-1) else: return 1 if __name__ == '__main__': n = int(input('출력할 팩토리얼 값을 입력: ')) print(f'{n}의 팩토리얼은 {factorial(n)}입니다.') 만약 3의 팩토리얼 값을 구한다고 했을 때 factorial(3)을 호출하면 3 * factorial(2)을 반환하고 factorial(2)는 다시 factorial(1)을, factorial(0)일 때는 1을 반환하게 됩니다. 그럼 factorial(1) -.. 2020. 11. 16. 알고리즘 - 해시법(2) 저번 포스팅에 이어서 체인법입니다. 이번에는 노드를 key, value, next 이렇게 세 가지로 구성해서 key 값도 넣겠습니다. 또한 value가 str형일 때 hashlib을 사용해 해시값을 구해보겠습니다. chain_hash.py from __future__ import annotations from typing import Any, Type import hashlib class Node: def __init__(self, key: Any, value: Any, next: Node) -> None: self.key = key # 키 self.value = value # 값 self.next = next # 뒤쪽 노드 참조 class ChainHash: def __init__(self, capac.. 2020. 10. 27. 이전 1 2 3 4 5 ··· 13 다음
