알고리즘 (9) 썸네일형 리스트형 알고리즘 유형공부 - 우선순위 큐 (Priority Queue) 우선순위 큐 (Priority Queue)1. 개요우선순위 큐는 각 원소에 우선순위를 부여하여, 우선순위가 높은 원소가 먼저 처리되도록 하는 데이터 구조일반적인 큐는 FIFO(First In, First Out) 방식이지만, 우선순위 큐는 우선순위를 기준으로 순서가 정해짐. 주로 힙을 사용하여 구현되며, 배열이나 연결 리스트를 통해서도 만들 수 있음.2. 우선순위 큐의 특성1. 원소의 입, 출삽입: 새로운 원소를 큐에 추가삭제: 가장 높은 우선순위를 가진 원소를 큐에서 제거조회: 현재 가장 높은 우선순위를 가진 원소를 반환2. 배열, 연결리스트, 힙을 통한 우선순위 큐구현 방식삽입 시간복잡도삭제 시간복잡도공간복잡도특징배열 (정렬X)O(1)O(N)O(N)삽입은 빠르지만 삭제 시 전체를 탐색해야 함.배열 .. 알고리즘 유형공부 - 다익스트라 (Dijkstra) 다익스트라 (Dijkstra)1. 개요다익스트라 알고리즘은 가중치가 양수인 그래프에서 특정 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 2. 알고리즘의 원리시작 정점을 기준으로 초기 거리를 설정하며, 시작 정점의 거리는 0으로 설정한다.방문하지 않은 정점 중에서 가장 가까운 정점을 선택한다.선택한 정점을 기준으로 인접한 정점들의 거리를 갱신한다.모든 정점이 반복될 때까지 반복한다.3. 구현3-1. 구현 1 - 인접 행렬 방식설명동작 방식그래프를 인접 행렬로 표현하며, 각 정점 간의 연결 여부와 가중치를 행렬로 나타냄방문 여부를 저장하는 배열과 현재까지의 최소 서리를 저장하는 배열 사용모든 정점을 순회하며, 최소 거리를 갱신시간복잡도시간복잡도는 O(V ^ 2)이다.코드파이썬 코드im.. 알고리즘 유형공부 - 연결 리스트 (Linked List) 연결리스트1. 개요연결리스트란 메모리 상에서 비연속적으로 존재하는 데이터 구조로, 각 데이터(노드)가 다음 데이터의 주소를 포함하고 있다.배열과 달리 고정된 크기가 없고, 동적으로 크기를 조절할 수 있어 데이터 삽입과 삭제가 용이하다.하지만 순차 접근만 가능하여 탐색 속도가 느릴 수 있다.1-0. array와 비교 및 시간 복잡도arraylinked list장점무작위 접근 가능빠른 자료 삽입, 삭제, 자유로운 크기 조절단점느린 자료 삽입, 삭제, 크기 조절 불가능순차 접근만 가능, 메모리 추가 할당 필요시간복잡도탐색 (Search): O(N) (순차 접근 필요)삽입 (Insert): O(1) (노드 추가 시)삭제 (Delete): O(1) (노드 삭제 시)1-1. 단순 연결 리스트단순 연결 리스트는 각 .. 알고리즘 유형공부 - 이분탐색(Binary Search)과 투포인터(Two Pointer) 이분탐색과 투포인터목차이분탐색 1-1. 개요 1-2. 알고리즘 원리 1-3. 예시 1-4. 시간복잡도 1-5. Bisect 라이브러리 1-6. 추천문제 투포인터 2-1. 개요 2-2. 알고리즘 원리 2-3. 예시 2-4. 시간복잡도 2-5. 추천문제 이분탐색과 투포인터 비교이분탐색과 투포인터1. 이분탐색1-1. 개요이분탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾을 때 사용되는 효율적인 탐색 알고리즘이다.배열의 중간 값을 기준으로 탐색 범위를 절반으로 줄여가며 값을 찾는다.1-2. 알고리즘 원리배열의 중간 값을 선택한다. 중간 값이 찾고자 하는 값과 같으면 탐색을 종료한다. 중간 값이 찾고자 하는 값보다 크면 왼쪽 절반을 탐색한다. 중간 값이 찾고자 하는 값보다 작으면 오.. 알고리즘 유형공부 - 위상정렬 (Topological Sorting) 위상정렬 (Topological Sorting)1. 개요위상정렬(Topological Sorting)은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)에서 노드들을 선형으로 정렬하는 방법이다.이 정렬은 그래프의 모든 간선 (u, v)에 대해 노드 u가 노드 v보다 앞에 오도록 정렬한다. 위상정렬은 순서가 필요한 작업 스케줄링, 컴파일러의 의존성 분석, 데이터 처리 파이프라인 등 다양한 분야에서 활용된다.2. 알고리즘의 원리위상정렬은 두 가지 주요 알고리즘을 사용한다: Kahn의 알고리즘 (BFS 기반): 진입 차수(indegree)를 기반으로 정렬한다. 깊이 우선 탐색 (DFS 기반): 각 노드를 방문한 후, 역순으로 정렬한다. 위상정렬이 가능한 그래프는 사이클이 없는 방.. 알고리즘 유형공부 - 비트마스킹 (BitMasking) 비트마스킹 (Bitmasking)1. 개요비트마스킹(Bitmasking)은 정수를 이진수로 표현하여 각 비트를 활용해 데이터를 효율적으로 처리하는 기법.주로 집합의 상태를 표현하거나 조합 문제를 해결할 때 사용된다.2. 알고리즘의 원리비트마스킹은 비트 연산을 통해 데이터를 조작한다.비트 연산을 이용해 특정 비트의 ON/OFF 상태를 확인하거나 변경할 수 있다.비트마스킹의 주요 작업은 다음과 같습니다:비트 켜기 (Set Bit): 특정 비트를 1로 설정한다.비트 끄기 (Clear Bit): 특정 비트를 0으로 설정한다.비트 토글 (Toggle Bit): 특정 비트를 반전한다.비트 확인 (Check Bit): 특정 비트가 1인지 확인한다.3. 비트마스킹을 사용하는 이유메모리 절약: 각 비트를 상태로 사용하기.. 알고리즘 유형공부 - BFS와 DFS DFS와 BFS1. DFS1. 개요깊이 우선 탐색(Depth First Search, DFS)은 그래프 탐색 알고리즘으로, 한 노드를 선택한 후 가능한 깊이까지 탐색한 후 돌아와 다른 경로를 탐색합니다.2. 알고리즘의 원리시작 노드에서 출발합니다.방문하지 않은 인접 노드가 있으면 그 노드로 이동하고 방문 처리를 합니다.더 이상 방문할 수 있는 노드가 없으면 이전 노드로 돌아갑니다.모든 노드를 방문할 때까지 이 과정을 반복합니다.주로 스택을 사용하며, 재귀 호출로 구현할 수 있습니다.3. 시간복잡도 및 공간복잡도시간복잡도 `: O(V + E) (V: 노드 수, E: 간선 수)공간복잡도 `: O(V)4. 예시 코드# DFS 예시 코드 (재귀 버전)def dfs(graph, v, visited): vis.. 알고리즘 유형공부 - 최소신장트리 (MST) 최소신장트리, 최소스패닝트리 - Minimum Spanning Tree개요신장트리란 무엇일까?신장트리(Spanning Tree)란 - 그래프에서 모든 정점을 포함하며, 모든 정점에 대한 최소한의 연결만을 가진 그래프이다.그래프라면서 왜 트리?? - 한 곳으로 도달하는 연결이 두 곳이상이 되는 경우에는, 즉, 사이클이 존재하는 경우, 최소한의 연결이라 볼 수 없기 때문에, 모든 곳에서 한 곳으로 이동하는 경우는 무조건 한 가지 경우, 즉 트리의 형태로 존재하게 된다.최소신장트리? - 이러한 신장트리 중에서 간선의 가중치들의 합이 가장 작은 트리를 최소신장트리(Minimum Spanning Tree)라고 한다.최소신장트리의 해법에는 두 가지, 프림알고리즘과 크루스칼알고리즘이 있다.알고리즘의 선택 기준보통의 .. 알고리즘 유형공부 - 선분교차 알고리즘 외적의 이해외적 (Cross Product) : 두 벡터의 곱을 의미하는 수학적 용어벡터의 곱에 해당하는 외적이라는 개념은 선분교차 알고리즘을 이해하는 데에 필요하다.외적은 두 벡터의 크기와 사잇각의 코사인값을 곱한 값으로 구해진다.특히, 선분교차 알고리즘에서 중요한 값, 또는 나중에 개발을 하게 되는 경우에 중요한 값은 결국 코사인값이다.코사인 값은 -90도에서 90도 사이에서만 양수이다. 즉 어떤 한 벡터가 바라보는 방향을 기준으로 왼쪽 오른쪽에 해당하는 부분 안쪽의 값만 양수가 나온다.다음 그림에서 붉은 색의 벡터와 파란색의 벡터가 기준이 되는 검은 색의 벡터와의 외적을 구한다면 양수와 음수 라는 매우 중요한 차이점을 알 수 있다.세 점의 방향 판단그렇다면 이 성질을 이용하여 세 점이 어떤 방향성을.. 이전 1 다음
