🍒 Chae-ri Dev 🍒

신장 트리(Spanning Tree)란?하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미 1. 모든 정점을 포함해야 한다.2. 연결 그래프이자 부분 그래프여야 한다.3. 사이클이 존재하지 않아야 한다. 최소 비용 신장 트리(Minimum Cost Spanning Tree)란?그래프에서 모든 노드를 연결할 때 간선의 가중치 합이 최소가 되는 경우의 신장 트리 최소 비용 신장 트리에는 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재한다. 크루스칼 알고리즘(Kruskal Algorithm)그리디 알고리즘을 통해 최소 신장 트리를 구하는 알고리즘이다.간선 데이터를 비용에 따라 오름차순으로 정렬한다.간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.사..

서로소 집합(Disjoint Set)이란?서로 중복되지 않는 부분(서로소) 집합. 서로 다른 원소들이 같은 집합에 속해 있는지 여부를 확인하는데 사용. 이 서로소 집합을 나타내기 위해 사용되는 알고리즘으로 Union-Find 알고리즘이 있다. Union-Find 알고리즘각 그룹을 트리의 형태로 표현. 각 트리는 항상 최상위 노드인 루트 노드를 가진다.이 루트 노드를 가지고 그룹을 판별한다.(root 노드는 자신을 부모 노드로 설정) union 연산을 확인하며, 서로 연결된 두 노드 A, B를 확인한다.A와 B의 루트 노드를 각각 찾는다.A의 루트 노드를 B의 부모 노드로 설정한다.모든 union 연산 처리할 때까지 이전 과정을 반복한다. Find어떤 노드가 주어졌을 때 이 노드가 속한 집합의 root 노..

다익스트라 최단 경로 알고리즘그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘.음의 간선이 없을 때 정상적으로 동작.기본적으로 그리디 알고리즘으로 분류된다. => 매번 각 노드에 대한 현재까지의 최단 거리를 갱신하기 때문! 알고리즘 원리 과정1. 출발 노드를 설정한다.2. 최단 거리 테이블을 초기화한다.(무한으로)3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.5. 위 과정에서 3과 4번을 반복한다. 각 노드에 대한 현재까지의 최단 거리를 1차원 리스트(최단 거리 테이블)에 계속 갱신한다는 특징이 있다. 힙 자료구조의 우선순위 ..

DP(Dynamic Programming)는 연산 속도와 메모리 공간을 최대한 효율적으로 활용할 수 있게 해주는 알고리즘이다. 대표적인 예시 : 피보나치 수열 피보나치 수열을 점화식으로 표현하면 다음과 같다.프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현(+ dict 자료형)# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현def fibo(x): if x == 1 or ×= = 2: return 1 return fibo(x - 1) + fibo(x - 2)print(fibo(4)) 하지만 위 코드는 n이 커지면 수행 시간이 기하급수적으로 늘어나는 문제가 발생한다.메모이제이션 기법을 사용해서 한 번 구현한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메..

BFS(Breadth First Search)BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 탐색하는 알고리즘이다. BFS를 구현할 때는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. # 동작 방식1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. deque 라이브러리 사용 => 시간 복잡도 O(N)일반적으로 bfs가 더 빠르다. from collections import deque# BFS 메서드 정의def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 dequ..

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.리스트에 담긴 데이터에 순차적으로 접근해야 할 때, 시작점(start)과 끝점(end) 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 특정한 합을 가지는 부분 연속 수열 찾기- N개의 자연수로 구성된 수열이 있다.- 합이 M인 부분 연속 수열의 개수를 구해보자.- 수행 시간 제한은 O(N)이다.  위 문제는 투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다. 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.2. 현재 부분 합이 M과 같다면, 카운트한다.3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.4. 모..

대표적인 탐색 알고리즘인 DFS와 BFS는 스택과 큐, 재귀 함수를 이용하여 정리할 수 있다. DFS(Depth First Search)DFS는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프는 다음과 같이 두 방식으로 쓰일 수 있다.1. 인접 행렬 방식INF = 999999999 #무한의 비용 선언# 2차원 리스트를 이용해 인접 행렬 표현graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0]]print(graph)# [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]2. 인접 리스트 방식# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현graph = [[] for _ in r..

트리 이진 탐색배열 내부의 데이터가 정렬되어 있을 때 사용할 수 있는 알고리즘.탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색을 할때는 시작점, 끝점, 중간점 3개의 변수를 사용한다.# 이진탐색소스코드 구현(재귀함수)def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array, target, sta..