풀소유

플로이드-와샬 알고리즘은 모든 정점 간의 최단 경로를 찾는 알고리즘으로, 음의 가중치를 가진 그래프에서도 사용할 수 있습니다. 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루지는 것이 이 알고리즘의 핵심 아이디어이다. (S -> E까지의 최단 거리는 S -> K -> E의 최단 거리와 같다.) 이 원리로 다음과 같은 점화식을 도출할 수 있다. D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 해당 알고리즘은 3중 for 문으로 이루어져 있어 O(V^3)에 시간복잡도를 가지고 있다. 알고리즘 동작 순서 초기화: 최단 거리를 저장하는 2차원 배열을 초기화한다. 초기에는 직접적인 간선이 존재하면 해당 가중치를, 그렇지 않으면 무한대(INF)로 설정한다. 동적 ..

벨만-포드 알고리즘은 모든 정점 간의 최단 경로를 찾기 위한 알고리즘 중 하나이다. 다익스트라 알고리즘이 간선의 가중치가 음수일 때 제대로 동작하지 않는 경우가 있지만, 벨만-포드 알고리즘은 음의 가중치를 가진 그래프에서도 사용할 수 있다. 알고리즘의 기본 아이디어는 각 정점에 대해 현재까지 발견한 최단 경로의 추정치를 저장하고, 이를 반복적으로 업데이트하여 최종적으로 최단 경로를 찾아내는 것이다. 그리고 마지막에 음의 사이클이 있는지를 확인하여 음의 사이클이 있다면 최단 경로를 정의할 수 없다는 것을 알 수 있다. 시간 복잡도는 O(VE)이다. 알고리즘 동작 원리 초기화: 시작 정점을 제외한 모든 정점에 대한 최단 거리를 무한대로 초기화하고, 시작 정점의 최단 거리를 0으로 설정한다. 모든 에지를 확인..

다익스트라 알고리즘은 그래프에서 출발 노드와 모든 노드 간의 최단 거리를 찾는 데 사용되는 효율적인 알고리즘 중 하나이다. 이 알고리즘은 양의 가중치를 가진 간선으로 이루어진 그래프에서 사용할 수 있다. 시간 복잡도는 O(ElogV)이다. 알고리즘 동작 원리 시작점 설정: 최단 경로를 찾을 시작점을 선택한다. 거리 초기화: 시작점을 제외한 모든 정점까지의 거리를 무한대로 설정하고, 시작점의 거리를 0으로 설정한다. 우선순위 큐 초기화: 우선순위 큐를 사용하여 현재까지의 최단 거리를 가진 정점을 방문한다. 시작점을 우선순위 큐에 삽입한다. 최단 경로 갱신: 우선순위 큐에서 가장 최단 거리를 가진 정점을 추출하고, 해당 정점과 이웃한 정점들의 거리를 갱신한다. 새로운 거리가 더 짧으면 해당 정점의 거리를 갱..

위상 정렬(Topological Sorting)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 시간 복잡도는 O(노드의 수:V + 에지 수:E)이다. DFS를 이용하는 방법과 BFS를 이용하는 방법이 있다. 위상 정렬 수행 과정진입 차수가 0인 노드를 큐에 저장한다.큐에서 데이터를 poll 해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 한다.큐가 빌 때까지 1~3을 반복한다. import java.util.*; public class topologicalSort { public static List topologicalSort(..

퀵선택 알고리즘은 특정 위치의 원소를 찾는 데 사용되는 효율적인 분할 정복 알고리즘 중 하나이다. 퀵정렬 알고리즘 일부를 이용하여 전체를 정렬하지 않고 특정 위치의 원소를 찾을 수 있다. 이 알고리즘의 평균 시간 복잡도는 O(n)이며, 최악의 경우에 O(n^2)이 될 수 있다. 동작 순서 피벗 선택: 배열에서 피벗을 선택한다. 일반적으로 배열의 가운데 원소를 선택한다. 분할: 피벗을 기준으로 배열을 두 그룹으로 나눈다. 작은 원소는 피벗 왼쪽에 위치하고, 큰 원소는 오른쪽에 위치한다. 쿼리 위치 확인: 찾고자 하는 원소의 위치를 확인한다. 이 위치가 현재 피벗의 위치와 일치하면 찾은 것이다. 재귀적으로 반복: 찾고자 하는 위치가 피벗의 위치보다 작으면 왼쪽 부분 배열에서 반복적으로 알고리즘을 수행한다. ..

달러의 투자 장점달러는 유동성 위기를 방어하기 위한 안전자산으로 분류되며, 금에 비해 가지고 있기 쉽고 이자를 주는 장점이 있다. 여기서는 5가지 달러 투자 방법과 가치 확인 방법을 알아보겠다. 달러 가치 확인 방법1. 달러인덱스(절대 가치)세계 주요 6개 통화와의 상대가치를 지수화한 값1973년 3월 값을 100으로 출발하여 달러의 전반적인 가치 상승과 하락을 확인100을 기준으로 높으면 비싸다고 낮으면 싸다고 평가2. 원달러환율(상대 가치)원화와 달러 간의 환율을 통해 달러의 상대적 가치를 확인환율 하락은 원화의 가치 상승과 달러의 가치 하락을 의미하며, 반대로 환율 상승은 원화의 가치 하락과 달러의 가치 상승을 나타냄 달러 투자법 달러예금국내 ETF미국 ETF달러 RP달러 발행어음매수처은행국내주식시..

CDS 이해하기CDS (Credit Default Swap)는 기업이나 국가의 부도 위험과 신용을 맞바꾸도록 설계된 금융 파생상품이다. 예시로 이해해 보자. 주요 참여자는 채권 투자자(A), 국가 또는 기업(B), 그리고 CDS 판매자(C)로 구성된다.A가 B의 채권을 구매하려고 할 때,B 국가 또는 기업이 금융 위기 등으로 여러 차례 부도 위험을 경험했다면,A는 B가 부도 시, C가 원금을 대신 갚아주는 조건으로 C에게 보험료(CDS 프리미엄)를 지불한다. CDS 프리미엄(CP)기업 부도 가능성 및 국가의 부도 가능성을 나타내는 지표로 활용된다.CDS 프리미엄은 계약 당사자의 위험이 높을수록 높아지며, 낮을수록 낮아집니다.국가의 경제 상태를 나타내는 중요한 지표로 사용되며, 높은 CDS 프리미엄은 해당..

RP와 발행어음은 단기채권형 상품이다. 두 상품은 달러와 원화로 투자가 가능하다. 수시 입출금이 가능하며, 자금을 자유롭게 운용할 수 있는 수시형 상품과 예금처럼 기간을 정해두는 형태로, 일정 기간 동안 투자를 유지해야 하는 약정형 상품이 있다. RP(Repurchase Agreements)란? 환매조건부채권을 말한다. 일반적인 채권은 만기가 길어 장기금융상품에 속한다. 하지만 고객이 해당 채권을 사고는 싶지만, 만기가 길어 꺼려질 경우가 있다. 이 경우 증권회사에서 3개월 등 상대적으로 짧은 기간 후에 되사주기로 한다면 고객은 만기가 짧아지는 효과가 있다. 이렇듯 장기금융상품의 대명사인 일반 채권이 RP로 바뀌면서 단기금융상품으로 재탄생하는 것이다. 운용 과정 고객이 RP를 구매하면 증권사는 고객 계좌..

코픽스(COFIX)란?코픽스(COFIX)는 은행이 자금을 조달하는 데 드는 비용을 반영한 기준금리로, 자금조달비용지수로도 불린다. 은행은 예금을 받아서 이를 기반으로 대출을 하고, 대출에서 얻은 이자로 수익을 창출한다. 이때, 은행은 예금 이자를 비용으로 간주한다. 따라서 실제로 은행이 자금을 조달하는 데 드는 비용을 반영한 것이 코픽스금리이다.매월 15일, 시중 은행 6곳과 특수은행 2곳의 총 8개 은행에서 취합된 자금조달비용 자료를 기반으로 은행연합회에서 산출된다.이는 은행이 실제로 어떤 이자율로 자금을 조달했는지를 반영한 데이터로, 은행들 간의 자금 조달비용 차이를 나타낸다.코픽스는 주택대출 등의 금리 결정에 중요한 역할을 하며, 금융시장에서의 금리 동향을 파악하는 데 도움을 준다.가중평균금리금융상..

유니온-파인드(Union-Find) 알고리즘은 여러 집합을 효율적으로 관리하는 데 사용되는 알고리즘이다. 주로 서로소 집합(disjoint-set)을 다루는 데에 활용된다. 유니온-파인드 알고리즘은 각 집합을 대표하는 원소를 찾거나, 두 집합을 합치는 등의 연산을 수행할 수 있다. 대표적으로 "합집합 찾기(Union)"와 "찾기(Find)" 연산이 있다. 간단한 버전 class UnionFind { private final int[] parent; public UnionFind(int size) { this.parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } public void union(int x, int y) { i..