CS/Data Structures7 🌱우선순위 큐, 힙(Heap) 1. 힙(Heap) 개념 우선순위(priority)를 빠르게 결정할 수 있도록 설계된 완전 이진 트리 기반의 자료구조데이터 간 루트, 왼쪽/오른쪽 자식 관계가 존재하는 계층 관계를 가지지만 물리적으로는 배열로 구현되어 선형적인 특성을 가짐부모-자식 간 우선순위 규칙만 유지하고 전체 정렬되지는 않음ex) 최소값이 맨 앞(= 루트 = 인덱스 0)에 오도록 힙 구조를 유지 → 정렬 성질 X, 완전 이진 트리 구조 + 힙 속성 만 만족 최대 힙(max heap) : 부모 노드 ≥ 자식 노드 최소 힙(min heap) : 부모 노드 ≤ 자식 노드삽입, 삭제, 최소/최대값 탐색이 빠름 (로그 시간)※ 정렬이 필요하면 list, 정렬된 추출이 필요하면 heap※ 완전 이진트리 : 왼쪽부터 순서대로 채워짐 2. Pyt.. 2025. 6. 11. 🌱선형 자료구조, 스택(Stack)과 큐(Queue) 관련글 : 튜플(tuple)에 대해서https://waydd.tistory.com/43sort() vs sorted()https://waydd.tistory.com/38리스트의 리스트 순회 (2번 문제)https://waydd.tistory.com/132왜 스택 구현은 deque가 아닌 stack으로 쓰는지 (5번 문제)https://waydd.tistory.com/44단조 스택 (6번 문제)https://waydd.tistory.com/44비슷한 array 모듈 (list 와 차이점 언급)https://waydd.tistory.com/151입출력 (출력 부분 언급)https://waydd.tistory.com/30 1. 스택과 큐 비교 스택과 큐는 데이터를 저장하고 꺼내는 방식이 다름 스택 (Sta.. 2025. 6. 11. 🌱해시(Hash)기반 자료구조 관련글 :defaultdict, Counter (dict 메모리 관점 참고 + 멀티셋)https://waydd.tistory.com/36메모리 사용https://waydd.tistory.com/133그래프 입력 (set 기반 visited)https://waydd.tistory.com/23집합 연산자 사용 (set, dict)https://waydd.tistory.com/71 1. 해시(Hash) 개념 해시는 고정 길이로 데이터를 매핑하여 빠른 탐색을 가능하게 함평균적으로 O(1) 탐색/삽입 - 해시 함수핵심 개념 : 수학적 매핑, 일방향 함수데이터를 고정된 크기의 정수 값으로 매핑/반환하는 함수 →→ 데이터(문자열이나 객체)를 일정한 길이의 숫자(=정수값=해시값)로 변환하는 수학적 계산 도구때문에 그.. 2025. 6. 10. 🧵유니온 파인드(Union-Find) 알고리즘 관련글 :역 아커만 함수https://waydd.tistory.com/47시간 복잡도 참고 (5번 문제)https://waydd.tistory.com/90인접 리스트에 대하여https://waydd.tistory.com/94사이클 판별, 개수 정리 (유니온 파인드 포함)https://waydd.tistory.com/51유니온-파인드 문제https://waydd.tistory.com/142크루스칼 + 유니온-파인드 문제https://waydd.tistory.com/143 1. 유니온 파인드 (Union-Find) 서로 다른 정점들이 같은 집합(트리)에 속해 있는지를 확인하는 알고리즘 (= 탐색/연결 전략) 및 자료구조 (= 구현 기법)혹은 Disjoint Set Union (DSU)서로소 집합(Disjo.. 2025. 6. 9. 🔢 이진탐색트리(BST)부터 균형 잡힌 구조까지 (+ AVL) 관련글 : 이진 탐색 트리 참고https://waydd.tistory.com/16 1. 이진 탐색 트리BST는 이진 트리에 탐색을 빠르게 할 수 있도록 정렬 규칙을 부여한 트리다음 데이터의 크기 규칙을 만족한다→ 왼쪽 서브트리 : 루트보다 작은 값들을 가진 노드들의 트리 → 오른쪽 서브트리 : 루트보다 큰 값들을 가진 노드들의 트리 → 각 서브트리 역시 자체적으로 BST 조건(왼쪽 자식 을 만족하는 재귀적 구조 탐색/삽입/삭제 속도 : 평균 O(log N), 최악 O(N) 중위 순회 시 항상 오름차순 정렬 탐색, 삽입, 삭제 시 비교를 통해 좌우로 이동※ 루트 노드와 중간값의 관계 (정치(Balanced) 구조)- 일반적인 BST는 입력되는 데이터의 순서에 따라 루트 노드가 결정되므로, 무조건 중.. 2025. 6. 9. 🔢계층적 자료구조, 트리(Tree) 관련글 :힙(Heap) (문제 유형 참고)https://waydd.tistory.com/41이진 탐색 트리 구현 (AVL 포함)https://waydd.tistory.com/25그래프 개념https://waydd.tistory.com/15그래프 탐색 알고리즘 (DFS, BFS 참고)https://waydd.tistory.com/11인접 리스트, 인접 행렬 참고https://waydd.tistory.com/94트리에서 DFS 사용 예시https://waydd.tistory.com/95트리 기반 고급 자료구조https://waydd.tistory.com/99 1. 트리(Tree) 란? 사이클이 없는 연결 그래프→ 루트(root)부터 시작해 자식 노드로 내려가는 계층적 구조→ 모든 노드는 루트에서 연결됨 .. 2025. 6. 9. 이전 1 2 다음