기록방

💡 벨만-포드(Bellman-ford)는 그래프에서 음수 가중치 간선이 있을 때 최단 거리를 구하는 알고리즘이다. 다익스트라(Dikjstra), 플로이드-워셜(Floyd-Warshall) 알고리즘과 함께 그래프의 최단 거리를 구하는 방법이다.위 알고리즘들과 다르게 음수 가중치의 간선이 있어도 최단 경로를 구할 수 있다.단, 음수 사이클이 있을 경우 최단 거리를 구할 수 없으므로 예외 처리가 필요하다. (음수 사이클의 존재 여부를 파악할 수 있다).매번 모든 간선을 확인하기 때문에 시간 복잡도는 O(VE) = Vertex * Edge로 다익스트라보다 느리다. 🚀 벨만-포드 알고리즘 동작 과정출발노드, 도착노드, 가중치 3개의 변수를 갖은 Edge클래스(혹은 배열)를 선언한다.계산 결과인 최단경로를 저장..

💡 0-1 BFS는 특정 상황의 그래프에서 최단 경로를 찾을 때 사용된다. 가중치가 0과 1로 이루어진 그래프에서 최단 경로를 찾을 때 사용한다.최단 경로를 구할 때 많이 사용하는 우선순위 큐 다익스트라(Dikjstra) 알고리즘은 시간 복잡도가 O(E log V)인 반면에, 0-1 BFS는 일반적인 BFS 시간 복잡도와 같이 O(V + E)의 선형 시간 복잡도를 갖는다.일반 BFS 에서 큐를 사용하는 것과 달리 덱(Deque)을 사용한다. 🚀 0-1 BFS의 동작 과정덱의 front에서 현재 방문한 노드를 꺼낸다.연결된 인접 노드를 살펴본다.(현재 비용+ 다음 노드 가중치) 다음 노드에 기록된 비용을 갱신해 준다.노드가 갱신될 때, 가중치가 0이라면 덱의 front, 가중치가 1이라면 덱의 back..

분리 집합(Disjoint Set)은 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는 지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산 find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 Union-Find 원리 이해하기 Union-Find를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됨 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행 대표 노드가 아..

최장 증가 부분 수열(LIS: Longest Increasing Subsequence)은 원소 n개의 배열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열을 말한다. ex) 수열 A = {10, 20, 10, 30, 20, 50} 의 경우 LIS = {10, 20, 30, 50} 이고, 길이는 4이다. LIS의 풀이 알고리즘은 대표적으로 DP와 이분 탐색이 있다. DP를 활용한 LIS 구현dp[ i ] = max( dp[ i ] , dp[ i - 1] + 1 )dp 배열에 각 인덱스의 원소를 포함 한 LIS의 최대 길이를 저장한다.(현재 인덱스의 앞쪽 dp 배열을 확인해 최대값 + 1. 혹은 현재 dp 배열 값 중 큰 것을 저장한다.)..

신발끈 공식(Shoelace formula)은 좌표평면 상에서 다각형의 꼭짓점 좌표를 알 때 그 면적을 구하는 방법이다. 가우스의 면적 공식이나 사선 공식이라고도 불린다. 다각형의 각 꼭짓점의 좌푯값을 교차하여 곱하는 모습이 신발끈을 묶을 때와 같아 이러한 이름이 붙었다. 삼각형의 넓이를 구해보자. 세 좌표를 지나는 사각형을 그리고, 사각형 넓이에서 구하고자 하는 영역 밖의 넓이를 빼면 된다. 식으로 나타내면 다음과 같다. 사각형의 넓이 = ( x3 - x2 ) * ( y1 - y3 ) A = ( x1 - x2 ) * ( y1 - y2 ) / 2 B = ( x3 - x1 ) * ( y1 - y3 ) / 2 C = ( x3 - x2 ) * ( y2 - y3 ) / 2 D = (사각형의 넓이) - (A + ..