aeightchill

우선순위 큐(Priority Queue)우선순위 큐는 가장 중요한(우선순위가 높은) 요소가 먼저 처리되는 자료구조→   일반적인 큐(Queue)는 선입선출(FIFO, First In First Out)→   우선순위 큐는 우선순위가 높은 요소가 먼저 나오는 구조  특징자동 정렬요소를 삽입할 때마다 내부적으로 정렬하고 꺼낼 때 항상 최우선 요소가 반환된다.힙(Heap) 자료구조 활용일반적으로 이진 힙(Binary Heap)을 사용하여 O(logN)의 시간복잡도로 삽입/삭제 가능최소 힙(Min Heap) / 최대 힙(Max Heap)최소 힙(Min Heap, default)  :  값이 작은 요소가 먼저 반환된다.최대 힙(Max Heap)  :  값이 큰 요소가 먼저 반환된다.  Python heapq 모듈..

그리디 알고리즘 (탐욕 알고리즘)그리디 알고리즘은 매 단계에서 가장 최적이라고 판단되는 선택(Local Optimal Solution)을 반복하여 최종적으로 전체 문제의 최적해(Global Optimal Solution)를 구하는 기법→   가장 좋은 선택을 하는 방식으로 동작하며 최적해를 보장하는 경우가 많다.그리디 알고리즘의 조건Greedy Choice Property (탐욕적 선택 속성)현재 단계에서의 최적 선택(전체적인 최적해)이 이후 단계에서도 최적 선택이 되어야 한다.Optimal Substructure (최적 부분 구조)문제를 작은 부분 문제로 나누었을 때, 각 부분 문제의 최적해를 모아서 전체 문제의 최적해를 구성할 수 있어야 한다.예제 1.  거스름돈 문제 (동전 최소 개수)거스름돈을 줄..

Two Pointers리스트에 순차적으로 접근할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. (응용문제) _ 특정한 합을 가지는 부분 연속 수열 찾기문제 설명N개의 자연수로 구성된 수열이 있다.합이 M인 부분 연속 수열의 개수를 구하라수행 시간 제한은 O(N)문제 해결 아이디어시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.현재 부분 합이 M과 같다면, 카운트한다.현재 부분 합이 M보다 작다면, end += 1현재 부분 합이 M보다 크거나 같다면, start += 1모든 경우를 확인할 때까지 2번부터 4번 과정을 반복한다.  참고이것이 코딩 테스트다 with Python

DFS 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법(스택 or 재귀 함수를 통해 구현)가능한 한 깊이 내려가면서 탐색을 진행한다.특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다..def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited)visited = [False] * ndfs(graph, 1, visited)BFS 루트 노드 혹은 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법인접한 노드를 먼저 탐색한다.최단 경로를 찾는 데 유용하다.def bfs(graph, start, visited): queu..

Disjoint Set(서로소 집합)은 서로 겹치는 요소가 없는 집합들을 저장하고 관리하는 자료구조.주로 Union-Find 알고리즘을 사용하여 구현하며, 아래와 같은 작업들을 지원Union(합집합 연산): 두 개의 서로소 집합을 하나의 집합으로 합친다.Find(대표자 찾기 연산): 특정 원소가 속한 집합의 대표자를 찾는다.같은 집합 여부 확인: 두 원소가 같은 집합에 속해 있는지 확인한다. (대표자가 동일한지 확인)예제사람들 간의 친구 관계를 관리하는 시스템새로운 친구 관계 추가: x가 y의 친구가 된다. (집합에 새로운 요소 추가)특정 두 사람이 직접적 또는 간접적으로 친구인지 확인한다.예시a, b, c, d, e, f, g, h, i, j 총 10명의 사람이 있다고 가정한다. 다음과 같은 친구 관계..