Python

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): ..

1. 시간 복잡도란?시간 복잡도란 알고리즘이 실행하는 데, 걸리는 시간을 입력크기에 대한 함수로 나타내는 것이다. 즉, 입력 크기가 증가할때 알고리즘의 실행 시간은 어떻게 변하는 지 분석하는 것이다. 빅오 표기법을 사용하여 최악의 경우를 기준으로 나타내는 것이 일반적이다.  1-1. 상수 시간 - O(1)입력 크기와 상관없이 항상 일정한 시간이 걸리는 경우예시) 배열의 첫 번째 요소를 출력하는 경우def get_first_element(arr): return arr[0] # 항상 한 번만 실행됨 → O(1) 1-2. 선형 시간 - O(N)입력 크기가 n이면 실행 횟수도 n번 증가하는 경우예시) 리스트의 모든 요소를 출력하는 경우def print_all_elements(arr): for ele..