HappyTomatoLife

단순 삽입 정렬 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 > ..

05-1 재귀 알고리즘의 기본 재귀 알아보기 recursion - 자기 자신을 모함하고 자기 자신을 사용하여 정의하는 경우 - recursive call 팩토리얼 알아보기 #양의 정수 n의 팩토리얼 구하기 def factorial(n: int) -> int: if n > 0: return n * factorial(n-1) else: return 1 if __name__ == '__main__': n = int(input('출력할 팩토리얼 값을 입력하세요 : ')) print(f'{n}의 팩토리얼은 {factorial(n)}입니다.') math.factorial() 함수를 사용할 수도 있음. 직접 재귀 direct 와 간접 재귀 indirect 유클리드 호제법 알아보기 두 정수의 최대공약수 GCD를 재귀적..

링 버퍼로 큐 구현하기 링 버퍼 ring buffer : 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료 구조 -> FIFO에서 First Out을 하는 경우, 나머지 모든 원소의 인덱스를 변경해야 하는 문제(O(n)) 해결 from typing import Any class FixedQueue: class Empty(Exception): pass class Full(Exception): pass def __init__(self, capacity : int) -> None: self.no = 0 self.front = 0 self.rear = 0 self.capacity = capacity self.que = [None] * capacity def __len__(self) -> int: retur..

04-1 스택 스택 프로그램 나머지 꼼꼼하게 공부할 것! from enum import Enum from class_making import FixedStack Menu = Enum('Menu', ['푸시', '팝', '피크', '검색', '덤프', '종료']) enum : enumeration 열거형 - 고유한 상숫값에 연결된 기호 이름의 집합 이 코드에서는 enum 모듈에서 Enum을 호출했다. class enum.Enum : 열거형 상수를 만들기 위한 베이직 클래스 #print(*myList, sep='\n') #리스트를 프린트하는 법 def select_menu() -> Menu: s = [f'({m.value}{m.name}' for m in Menu] while True: print(*s, s..