알고리즘 (11) 썸네일형 리스트형 [알고리즘] 다익스트라(Dijkstra) 알고리즘 개념다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(shortest Path) 탐색 알고리즘이다.정점과 간선에 대하여 최단 경로를 구하는데, 이때 음의 간선은 포함할 수 없다.다익스트라 알고리즘을 dp로 구현할 수 있는 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.즉, 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다.기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 다익스트라 작동 방법출발 노드를 설정한다.출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비.. [알고리즘] 상호 배타적 집합 : 서로소 집합 (Disjoint Set), 유니온-파인드 (Union-Find) 상호배타적 집합 · 유니온 - 파인드 → 크루스칼 · 프림 → 다익스트라 · 벨만-포드 알고리즘 집합이란?집합은 순서와 중복이 없는 원소들을 갖는 자료구조를 의미한다.예를 들어 A라는 그룹의 원소가 {1, 6, 6, 6, 4, 3} 이라면 이는 집합으로 생각할 때 중복을 제외해 {1, 6, 4, 3}으로 생각할 수 있다.순서를 고려하지 않으므로 {6, 1, 3, 4}와 같다고 볼 수 있다. 집합의 종류집합은 특성에 따라 여러 종류의 집합으로 나뉜다.유한 집합 : 원소의 개수가 유한 개인 집합무한 집합 : 원소의 개수가 무한 개인 집합공집합 : 아무런 원소가 없는 집합등.. 이 있다. 상호배타적 집합(Disjoint Sets)이란?이후 계속 언급하는 집합은 상호배타적 집합이다.상호배타적 집합은 교집합이 없.. [알고리즘] 그래프 (Graph) - 2. 그래프 탐색 코딩 테스트 합격자되기 chap 11 그래프를 바탕으로 작성하였습니다. 그래프 탐색자료구조에서 어떤 순서와 방식으로 데이터를 탐색할 지 고민해야 한다.그래프에서 경로를 찾는다고 할 때 경로를 찾는 방법은 크게 2가지가 있다.더 이상 탐색할 노드가 없을 때까지 가본다. 그러다 더 이상 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아간 다음 가지 않은 노드를 방문한다. (깊이 우선 탐색)현재 위치에서 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어간다. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문한다. (너비 우선 탐색) 📌 깊이 우선 탐색 (DFS, depth-first search)1단계노드 A에서 노드 D까지 차례대로 방문한다. 노드 D까지 방문하면 더 방문할 곳이 없다.2단계노드 .. [알고리즘] 그래프 (Graph) - 1. 개념 코딩 테스트 합격자되기 chap 11 그래프를 바탕으로 작성하였습니다. 그래프의 개념그래프는 노드(vertex)와 간선(edge)을 이용한 비선형 데이터 구조이다.보통 그래프는 데이터간의 관계를 표현하는 데 사용노드 : 데이터간선 : 노드 간의 관계나 흐름 - 간선은 방향이 있을 수도 없을 수도 있다. + 가중치📌 그래프 용어 정리 노드 : 동그라미로 표현한 것 → 데이터가 담겨있다.간선 : 화살표가중치 : 간선 위 숫자 📌 그래프의 종류와 특징그래프는 방향성, 가중치, 순환 특성에 따라 종류를 구분할 수 있다.1. 흐름을 표현하는 방향성방향 그래프(directed graph) : 방향이 있는 간선을 포함한 그래프무방향 그래프(undirected graph) : 방향이 없는 간선을 포함한 그래프2. .. [알고리즘] 투포인터 (Two Pointers) 투포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 두 개의 포인터를 사용하여 효율적으로 문제를 해결하는 알고리즘 기법이다.주로 정렬된 배열에서 사용되며, O(n) 또는 O(n log n) 시간복잡도를 가진다. 투 포인터 개념두 개의 포인터를 사용하여 배열을 탐색한다.일반적으로 좌(L), 우(R)포인터를 조작하여 값을 찾거나 특정 조건을 만족하는 구간을 찾는다.정렬된 배열에서 유용하게 사용되며, O(n^2)의 시간복잡도를 O(n)으로 줄일 수 있다. 투 포인터가 사용되는 대표적인 유형 두 수의 합 찾기 (Two Sum)구간 합(Subarray Sum)두 배열에서 공통 원소 찾기팰린드롬(Palindrome) 검사정렬된 배열에서 특정 조건을 만족하는 구간 찾기 (슬라이딩 윈도우와 유사) 1. 두.. [알고리즘] 우선순위 큐 우선순위 큐의 특징우선순위 큐는 일반적인 큐와 다르게 우선순위가 높은 요소를 먼저 처리하는 자료구조파이썬에서는 heapq 모듈을 사용하여 힙(Heap) 기반으로 구현🔹 주요 특징우선순위 기반 처리낮은 숫자가 높은 우선순위(기본 heapq는 최소 힙)최대 힙을 구현하려면 값을 음수(-)로 변환하여 저장효율적인 삽입/삭제 연산삽입(push) → O(logN)삭제(pop) → O(logN)최솟값(또는 최댓값) 조회 → O(1)정렬보다 효율적전체 정렬이 필요할 때 O(N logN)이지만, 우선순위 큐는 필요한 요소만 정렬해서 빠르다. heapq파이썬에서 우선순위 큐(Priority Queue)를 구현할 때 가장 많이 사용하는 모듈은 heapq이다.heapq는 최소 힙(Min Heap)을 기반으로 동작하며 우.. [알고리즘] Heap 구조 힙(Heap)이란?힙(Heap)은 완전 이진 트리(Complete Binary Tree) 기반의 자료구조로, 최댓값 또는 최솟값을 빠르게 찾고 유지하는 데 최적화된 구조이다. 힙의 특징1. 완전 이진 트리(Complete Binary Tree)왼쪽부터 차례대로 채워지는 이진 트리높이가 최소화되어서 연산 속도가 빠름2. 힙 속성(Heap Property)최소 힙(Min-Heap): 부모 노드가 자식 노드보다 항상 작음 → heap[0]이 최소값최대 힙(Max-Heap): 부모 노드가 자식 노드보다 항상 큼 → heap[0]이 최대값이 속성 덕분에 최솟값 또는 최댓값을 O(1)에 찾을 수 있다.3. 탐색보다 삽입/삭제가 빠름일반적인 트리나 리스트는 정렬을 해야 하지만 힙은 O(logN)만에 삽입/삭제 가능다.. [알고리즘] 유클리드 호제법 유클리드 호제법이란?유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다.이 방법은 다음의 원리를 이용한다:두 수 a, b (a>b)가 있을 때, a를 b로 나눈 나머지를 r이라 하면,GCD(a,b)=GCD(b,r)과 같다.이를 반복하여 나머지가 0이 되는 순간, 나누는 수가 최대공약수이다. 유클리드 호제법의 과정 예시예를 들어, 56과 98의 최대공약수를 구해보자.98÷56=198 \div 56 = 1 (몫), 나머지 42 → GCD(98, 56) = GCD(56, 42)56÷42=156 \div 42 = 1 (몫), 나머지 14 → GCD(56, 42) = GCD(42, 14)42÷14=342 \div .. 이전 1 2 다음 목록 더보기
