파이썬72 알고리즘 - 이진 삽입 정렬 단순 삽입 정렬은 배열 원소 수가 많이지면 비교, 교환 비용이 커지는데 이진 삽입 정렬을 사용하면 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사해서 비용을 줄일 수 있습니다. 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. 알고리즘 - 버블 정렬 버블 정렬은 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘입니다. 4 1 9 2 5 7 3 위와 같은 배열이 있을 때, 오름차순으로 배열을 정렬한다고 생각해봅시다. 이렇게 두 수를 비교하면서 작은 수면 자리를 교환 하고 계속 비교해 나갑니다. 계속 비교하면 가장 작은 수인 1이 제일 앞으로 오게 되고 다음으로 작은 수들이 오도록 비교, 교환 해줘야하고, 이 배열의 크기가 7이기 때문에 이러한 비교, 교환을 총 7 - 1 = 6번 해줘야 오름차순으로 정렬됩니다. 이제 코드로 살펴보겠습니다. def bubble_sort(a) -> None: n = len(a) for i in range(n - 1): for j in range(n - 1, i, -1): if a[j-1] > a.. 2020. 11. 20. 백준 - 6603번 문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 코드 import sys def set(start, index): if index == 6: for i in range(6): print(f'{temp[i]}', end=' ') print() for i in range(start, len(lst)): temp[index] = lst[i] set(i+1, index+1) temp = [0] * 13 while True: lst = .. 2020. 11. 19. 이전 1 2 3 4 5 6 ··· 18 다음
