0. 서론SSAFY에서 진행한 프로젝트들은 싸피 전용 GitLab에서 진행되기 때문에 나의 기록을 남기기 위해 깃허브에 옮기려고 한다.1. 방법1-1. GibLab 레포지토리 클론git clone --mirror {gitlab repo 주소}1-2. 미러링한 레포지토리로 이동cd {gitlab repo 이름}.git1-3. GitHub로 푸시git push --mirror {옮길 github repo 주소}

0. 세그먼트 트리(Segment Tree)란?세그먼트 트리(Segment Tree)어떤 데이터가 주어질 때, 특정 구간의 결과값(구간합, 최댓값 등)을 구하는데 사용하는 자료구조세그먼트 트리는 이진 트리(Binary Tree) 구조를 가지고 있으며, 특정 구간의 결과값을 시간복잡도 O(logN)으로 빠르게 구할 수 있다는 장점이 있다.또한, 자료의 수정이 빈번히 일어날 때, 사용한다. 이 게시글에서는 누적합을 구하는 세그먼트 트리 기준으로 설명을 한다.만약 구간 최대나 구간 최소를 알고 싶다면, 반환하는 부분만 수정하면 된다.1. 세그먼트 트리 알아보기1-1. 세그먼트 트리 생성(초기화)아래는 [5, 7, 6, 3, 1, 9]인 원본 배열로부터 만든 세그먼트 트리이다.파란 글씨는 해당 노드가 가리키는 ..

0. 최단 경로최단 경로간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로하나의 시작 정점에서 끝 정점까지의 최단 경로다익스트라(Dijkstra) 알고리즘음의 가중치를 허용하지 않음벨만-포드(Bellman-Ford) 알고리즘음의 가중치 허용모든 정점들에 대한 최단 경로플로이드-워셜(Floyd-Warshall) 알고리즘이번에는 이 중에서 플로이드-워셜(Floyd-Warshall) 알고리즘을 알아본다.1. 플로이드-워셜(Floyd-Warshall) 알고리즘모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.시작 정점에서 목표 정점의 최단 경로를 계산할 때, 다른 정점을 경유했을 때 비용을 비교하면서 구하는 방식이다.DP 기법을 사용한 알고리즘으로 인..

0. 최장 증가 부분 수열 LIS최장 증가 부분 수열 LIS어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있을 때, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출하는 문제를 의미한다.ex) 3, 2, 6, 4, 5, 1의 배열의 LIS 해 중 하나는 2, 4, 5이다.이 문제를 부분집합으로 접근하면 시간 복잡도가 O(2^n)이므로, DP나 이진 검색을 활용하여 접근하는 것이 효율적이다.1. DP를 활용한 접근각 원소까지의 LIS 길이를 저장하는 배열인 LIS라고 할 때, LIS(i)를 이전 단계들과의 관계로 표현해보자.Case 1: LIS(i)가 a_i를 부분 수열의 마지막으로 포함하지 않는다면 → LIS(i) = LIS(i - 1)Case 2: LIS(i)가 a_i를 부분 수..