Python

유클리드 호제법은 두 정수의 최대 공약수(GCD)를 구하는 효율적인 알고리즘이다. 기본 아이디어최대 공약수두 수 a와 b가 주어졌을때, a를 b로 나눈 나머지를 r이라고 정의 ( a와 b의 공약수는 b와 r의 공약수와 동일하기 때문 )a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다  ( a와 b의 최대 공약수 == b와 r의 최대 공약수 )즉, gcd(a, b) == gcd(b, r)이라는 식이 만들어진다.b = 0이 되면 최대 공약수가 된다. 예를 들어, a = 48 과 b = 18이라고 생각해보자.gcd(48, 18) = gcd(18, 12) gcd(18, 12) = gcd(12, 6)gcd(12 , 6) = gcd(6, 0)gcd(6, 0) = 6   (b가 0이 되었으므로, 최대 공약수는 ..

1. 힙 이란?힙은 완전 이진 트리 기반의 자료 구조로, 항상 최대값 또는 최솟값을 빠르게 찾을 수 있도록 구성된 트리이다. 최대 힙은 최대 값이 루트 노드로 오는 힙최소 힙은 최소 값이 루트 노드로 오는 힙 2. heapq - 내장 모듈파이썬에서는 heapq 모듈을 임포트 해줌으로써 힙을 쉽게 다를 수 있다.  2-1. heapq.heappush(heap, item)힙에 요소들을 추가하는 함수이다.import heapqheap = []heapq.heappush(heap, 3)heapq.heappush(heap, 1)heapq.heappush(heap, 5)print(heap) # 출력: [1, 3, 5] (최소 힙 유지) 2-2. heapq.heappop(heap)힙에서 최소값을 제거하고 반환해주는 ..

1. 정렬이란?정렬이란 데이터를 특정 기준으로 순서대로 정리하는 과정이다.정렬 알고리즘은 시간 복잡도와 공간 복잡도에 따라 성능이 결정된다.정렬 알고리즘평균 시간 복잡도특징선택 정렬O(n**2)단순하지만 비효율적삽입 정렬O(n**2)대부분 정렬된 데이터에 적합버블 정렬O(n**2)모든 인접 요소를 반복적으로 비교하여 교환 (비효율적)퀵 정렬O(n log n)빠르고 효율적병합 정렬O(n log n)안정적인 정렬, O(n)의 추가 공간이 필요함힙 정렬O(n log n)최대 힙 또는 최소 힙을 활용하여 정렬 파이썬의 sort() 및 sorted()는 팀 정렬 알고리즘을 사용한다. 팀 정렬 알고리즘은 병합 정렬과 삽입 정렬의 조합이다. 1. 선택 정렬배열에서 가장 작은 요소를 찾아,첫 번째 위치로 이동시키는 방..

1. 트리란?트리는 계층적 구조를 가진 비선형 자료구조로, 노드와 간선으로 이루어져 있다. 트리는 하나의 루트 노드를 중심으로 여러 개의 자식 노드와 부모 노드로 연결된다.  2. 트리의 기본 용어루트 노드 - 트리의 최상위 노드부모 노드 - 자식 노드를 가지는 노드자식 노드 - 부모 노드로 부터 연결된 하위 노드형제 노드 - 같은 부모를 가지는 노드리프 노드 - 자식 노드가 없가 없는 노드서브 트리 - 트리의 일부를 이루는 작은 트리레벨 - 루트 노드를 기준으로 특정 노드까지의 깊이높이 - 트리의 최대 레벨 3. 이진 트리3-1. 완전 이진트리마지막 레벨을 제외한 모든 레벨이 노드로 가득 차있음마지막 레벨의 노드는 왼쪽부터 순서대로 채워짐3-2. 포화 이진트리모든 노드가 두 개의 자식 노드를 가지거나,..

1. 스택1-1. 스택이란? 스택은 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO(Last-in-First-out) 자료구조로, 후입선출방식이라고도 부른다.즉, 마지막에 추가된 요소가 가장 먼저 제거되는 자료구조이다. 1-2. 파이썬에서의 스택파이썬은 스택 자료구조를 따로 제공하지 않지만, list 클래스를 사용하여 스택을 구현할 수 있다. 1-3. 사용 방법class Stack: def __init__(self): """ 스택을 초기화하는 생성자 """ self.stack = [] def push(self, item): """ 스택에 요소 추가 """ self.stack.append(item) def pop(self): ..