HappyTomatoLife

비재귀적인 퀵 정렬 만들기 from for_class import Stack from typing import MutableSequence def qsort(a:MutableSequence, left:int, right:int)-> None: range = Stack(right - left + 1) range.push((left, right)) while not range.is_empty(): pl, pr = left, right = range.pop() x = a[(left + right) // 2] while pl x: pr -= 1 if pl None: self.capacity = maxlen self.__stk = deque([], maxlen) def __len__(self) -> int: re..

퀵 정렬 quick sort 퀵 정렬 알아보기 피봇 pivot - 기준을 정하고 그룹을 나눈다. 그룹에 1명씩 남으면 정렬이 완료된다. 배열을 두 그룹으로 나누기 - pl 왼쪽 커서, pr 오른쪽 커서로 설정해놓고, 피벗을 정한다. - pl을 오른쪽 방향으로 스캔하여 -> a[pl] > a[pivot]인 pl값을 찾는다. - pr을 왼쪽 방향으로 스캔하여 -> a[pr] = pr이 될 때까지 반복한다. 두 그룹으로 나누는 걸 어떻게 구현해야 하나~ 우선 while 구문에 들어가기 전에 n, pl, pr, pivot을 할당해주었다. while문 안에서 - pl >= pr이 되면 그만하고.. - a[pl] > a[pivot], a[pr] <..

06-5 셸 정렬 셸 정렬 shell sort 단순 삽입 정렬의 문제 삽입 위치가 멀리 떨어져 있으면 이동 횟수가 많아짐 셸 정렬 알아보기 shell sort 알고리즘 - 정렬할 배열의 우너소를 그룹으로 나눔. 그룹별로 정렬 수행. 정렬된 그룹을 합치는 작업을 반복함. 4정렬 -> 2정렬 -> 1정렬을 적용하면 정렬이 완료된다. 'h-정렬' from typing import MutableSequence def shell_sort(a:MutableSequence) -> None: n = len(a) h = n//2 while h > 0: for i in range(h, n): j = i - h tmp = a[i] while j >= 0 and a[j] > tmp: a[j+h ] = a[j] j -= h a..

단순 삽입 정렬 straight insertion sort - 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘 단순 삽입 정렬 알아보기 for i in range(1, n): tmp = a[i] tmp를 (0, i) 사이의 알맞은 위치에 삽입한다. from typing import MutableSequence def insertion_sort(a:MutableSequence) -> None: n = len(a) for i in range(1, n): j = i std = a[i] while j > 0 and a[j-1] > std: a[j] = a[j-1] j -= 1 a[j] = std return a a = [3, 4, 5, 1, 2] print(insertion_sort(a))..

단순 선택 정렬 알아보기 아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택하고 for i in range(n-1) min a[i]와 a[min]을 교환 아직 정렬하지 않은 부분의 맨 앞 원소와 교환하는 작업을 반복한다. 왕 풀었다 from typing import MutableSequence def selection_sort(a:MutableSequence) -> None: n = len(a) min = 0 for i in range(n-1): for j in range(i, n): if a[j] None: n = len(a) for i in range(n-1): min = i for j in range(i+1, n): if a[j]

버블 정렬 bubble sort = 단순 교환 정렬 - 이웃한 두 원소의 대소관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘 버블 정렬 알아보기 pass - 비교/교환하는 과정 1세트 버블 정렬 프로그램 from typing import MutableSequence def bubble_sort(a:MutableSequence) -> None: n = len(a) for i in range(n-1): for j in range(n-1, i, -1): if a[j-1] > a[j]: a[j-1], a[j] = a[j], a[j-1] if __name__ == '__main__': print('버블 정렬을 수행합니다.') num = int(input('원소 수를 입력하세요')) x = [None] * n..

정렬이란? 정렬 sorting : key를 대소관계에 따라 일정한 순서로 늘어놓는 작업 오름차순 ascending order 내림차순 descending order 안정적인 알고리즘 - 안정적이지 않은 알고리즘 internal sorting - 모든 데이터를 하나의 배열에 저장할 수 있음 external sorting - 하나의 배열에 저장할 수 없음 -> 별도 작업용 파일 필요 * 교환, 선택, 삽입 * 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬, 셀 정렬, 퀵 정렬, 병합 정렬, 힙 정렬, 도수 정렬

03-4 해시법 정렬된 배열에서 원소 추가하기 해시법 hashing - 데이터를 저장할 위치 = 인덱스를 간단한 연산으로 수행 hash table, hash function, bucket 해시 충돌 -> 체인법 : 해시값이 같은 원소를 연결 리스트로 관리 -> 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복 체인법 chaining = open hashing 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 =..

05-3 하노이의 탑 하노이의 탑 알아보기 def hanoi(n, st, mid, dest): if n == 1: print(f'{st} -> {dest}') return #n-1개를 mid로 옮긴다. #1개를 dest로 옮긴다. hanoi(n-1, st, dest, mid) print(f'{st} -> {dest}') hanoi(n-1, mid, st, dest) hanoi(3, 1, 2, 3) 예제 코드 -> 기둥 번호의 합으로 표현한다. def move(no: int, x : int, y : int) -> None: if no > 1: move(no - 1, x, 6 - x- y) print(f'원반 [{no}]를 {x}에서 {y}로 옮깁니다.') if no > 1: move(no-1, 6-x-y,..

재귀 알고리즘의 2가지 분석 방법 def recur(n:int) -> int: if n > 0: recur(n-1) print(n) recur(n-2) x = int(input('정수를 입력하세요 : ')) recur(x) genuinely 재귀 - 재귀 호출을 여러 번 실행하는 함수 하향식 분석 top down - 가장 위쪽의 함수 호출부터 계단식으로 조사 - recur(3) -> recur(1), recur(2) -> recur(1), recur(0) -> 상향식 분석 bottom up - 아래쪽부터 샇아 올리며 분석 - recur(0), recur(1), recur(2) - - - > 재귀 알고리즘의 비재귀적 표현 꼬리 재귀를 제거하기 def recur(n:int) -> int: while n > ..