Little bIT awesome

세그먼트 트리란?세그먼트 트리는 배열과 같이 연속된 구간의 정보를 효율적으로 관리하고 쿼리를 처리하는 데 사용되는 자료구조입니다. 일반적으로 구간 합, 최솟값, 최댓값 등의 쿼리를 빠르게 처리할 수 있습니다.세그먼트 트리의 특징구간 쿼리의 빠른 처리: 세그먼트 트리는 구간 쿼리를 O(log N) 시간에 처리할 수 있습니다.동적 배열 업데이트: 배열의 특정 원소를 업데이트하는 데 O(log N) 시간이 소요됩니다.메모리 사용: 일반적으로 4N 크기의 메모리를 사용합니다(N은 배열의 크기).세그먼트 트리의 기본 구조세그먼트 트리는 트리 구조를 가지며, 각 노드는 특정 구간에 대한 정보를 저장합니다. 루트 노드는 전체 구간을 나타내고, 각 자식 노드는 구간을 절반으로 나눈 서브 구간을 나타냅니다.세그먼트 트리..

MST (Minimum Spanning Tree)그래프 이론에서 사용되며, 주어진 가중치 그래프에서 최소 비용으로 모든 정점을 연결하는 트리를 찾는 알고리즘네트워크 설계, 전력 배선, 클러스터링 등 다양한 분야에서 활용된다.  여러가지 MST 알고리즘이 있지만, 그 중에서도 가장 널리 사용되는 두 가지 알고리즘1. Kruskal's Algorithm (크루스칼 알고리즘)2. Prim's Algorithm (프림 알고리즘)https://littlebitawesome.tistory.com/entry/Week10-MSTMinimum-Spanning-Tree-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 [Week10] MST 알고리즘(1) - Kruskal's AlgorithmMST (Mi..

MST (Minimum Spanning Tree)그래프 이론에서 사용되며, 주어진 가중치 그래프에서 최소 비용으로 모든 정점을 연결하는 트리를 찾는 알고리즘네트워크 설계, 전력 배선, 클러스터링 등 다양한 분야에서 활용된다.  여러가지 MST 알고리즘이 있지만, 그 중에서도 가장 널리 사용되는 두 가지 알고리즘1. Kruskal's Algorithm (크루스칼 알고리즘)2. Prim's Algorithm (프림 알고리즘) Kruskal's Algorithm (크루스칼 알고리즘)기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 크루스칼 알고리즘을 수행하고 완성된 그래프는 최소 신장 트리이다.  크루스칼 알고리즘의 과정1. 간선 가중치 기준 정렬모든 간선을 가중치의 오름차순으로 정렬한다. 2. 최소 ..

Union-Find 알고리즘이란?서로소 집합(Disjoint-Set) 알고리즘이라고도 불리는 알고리즘여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 Disjoint-Set (서로소 집합)?서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조즉, 공통 원소가 없는 부분 집합들로 나눠진 원소들에 대한 자료구조 Union-Find 알고리즘의 과정초기화 (makeSet) - 합치기 (union) - 찾기 (find) 연산 과정을 거친다 1. 초기화 (makeSet)union과 find 연산을 하기전, 각 노드를 하나의 집합으로 초기화하는 과정자기 자신이 가리키는 대상 = 자신이 속한 집합이 되기 때문에, 자..

CloudFrontAWS의 CDN(Content Delivery Network) 서비스이다.CDN (Content Delivery Network)콘텐츠 전송 네트워크로, 전 세계적으로 분산된 서버 네트워크를 통해 콘텐츠를 효율적으로 전송하는 서비스. CDN은 웹사이트, 애플리케이션, 미디어 콘텐츠 등을 빠르고 안정적으로 제공하기 위해 사용된다. CDN의 주요 특징1. 엣지 로케이션: CDN이 콘텐츠를 캐싱하고 Client에게 제공하는 지점 혹은 캐시 서버를 의미. 엣지 로케이션은 사용자에게 가까운 위치에 배치되어 있어 콘텐츠에 빠르게 접근할 수 있도록 도와준다. 2. 캐싱: CDN은 콘텐츠를 엣지 서버에 캐시하여 사용자가 요청할 때마다 원본 서버로부터 콘텐츠를 다시 받아오지 않고도 제공한다. 이를 통해 ..

EC2 Elastic Compute Cloud의 줄임말로, AWS가 제공하는 클라우드 컴퓨팅 서비스이다.클라우드 컴퓨팅이란, 인터넷(클라우드)을 통해 서버, 스토리지, 데이터베이스 등의 컴퓨팅 서비스를 제공하는 것을 말한다.즉, AWS에서 원격으로 제어할 수 있는 가상의 컴퓨터를 한 대 필리는 것과 같다.Elastic은 후불제 PC방과 같이 사용한만큼 비용을 지불할 수 있다는 것을 의미한다.또한, 필요에 따라 성능, 용량을 자유롭게 조절할 수 있다는 의미도 가지고 있다. EC2를 사용해야 하는 이유효율성 : 클릭 몇 번으로 서버를 생성할 수 있기 때문에 실제 서버를 구축하는 것보다 훨씬 간편하고 효율적이다.비용 절감 : 사용한 만큼만 요금을 지불하면 되므로 비용이 절감된다. EC2 인스턴스 생성AWS E..

시작 노드 고정하고 반복 돌면서 최단 거리 갱신전체 노드 수 - 1 만큼 반복하면서 최단 거리 수정(전체 노드 수 - 1) 만큼 반복하는 이유- 노드와 노드 사이의 최대 간선의 수는 최대 (전체 노드 수 - 1) 개임- 일단 반복을 돌았을 때, 거리가 갱신됐다는 것은 경로에 간선의 개수가 하나 늘었다는 것을 의미-> 최단 거리의 간선의 수가 전체 노드 수 - 1보다 높으면 음의 사이클을 돌고 있다는 것- 음의 사이클을 돌면 그냥 그 노드까지이 최단 거리를 구할 수 없음 (무한대로 수렴하기 때문에)  코드 해석 간선 edge가 있을 때edge.v = 간선의 시작edge.w = 간선의 목적지edge.cost = 간선의 가중치 dist[x] = 시작점부터 x까지의 거리  // 전체 노드 수 - 1 만큼 반복f..

1. 다익스트라 알고리즘 (Dijkstra Algorithm)다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다).  일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다. ※ 음의 가중치를 가지면 안되는 이유는1. 최소 비용의 음의 무한대 발산 2. 그리디 알고리즘 적용 불가능 : 최적의 해를 보장할 수 없음   ※ 연결 그래프 : 모든 두 꼭..

그래프 그래프의 구성 요소 정점 간선 그래프의 방향성 방향 그래프 (Directed Graph) 무방향 그래프 (Undirected Graph, 양방향 그래프) 방향성이 없다는 것은 어느 쪽으로든 갈 수 있다는 의미이다. 그래프의 순환성 그래프 내 어떤 부분이라도 순환하는 부분이 있다면 순환 그래프, 한 군데도 없다면 비순환 그래프이다. 순환 그래프 (Cyclic Graph) 비순환 그래프 (ACyclic Graph) 그래프의 연결 요소 (Connected Component) 서로 완전히 분리된 요소들이 여럿 주어지는 그래프도 있다. 각각을 연결 요소라고 한다. 위의 그림은 두 개의 연결 요소를 가진 그래프이다. 트리 (Tree) 그래프의 일종으로 순환성이 없는 무방향 그래프이다. 트리(tree) 구조는..

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 예를 들어 { 6, 2, 5, 1, 7, 4, 8, 3 } 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이 된다. { 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 이기 때문 일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 간편한 방법은 DP를 이용하는 것 아래에서 length[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미한다. ..