그냥 블로그

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Floyd-Warshall은 최단 경로 알고리즘의 일종이다. (ft. Dijkstra, Kruskal, Prim) - 시간 복잡도는 O(N^3)이 걸리기 때문에, N의 값이 작을 때만 사용하도록 한다. - 다른 알고리즘과는 다르게 음의 값도 사용할 수 있다. - 모든 노드의 최단 경로를 찾을 수 있다. ( 다른건 한 노드에서 다른 노드까지...) 최단 경로 알고리즘 플로이드 - 워셜 (Floyd-Warshall) 알고리즘 => 다익스트라는 하나의 정점 ~ 다른 모..

알고리즘을 풀 때 map을 많이 사용해 왔는데, 이걸 구현하는게 레드 블랙 트리라는 사실은 알고 있었다. 하지만, 색을 지정하고 균형 트리를 이룬다는 것 외에 정확한 개념을 모르고 있기도 했고, STL을 구현하면서 C++ 실력을 올리기 위해 map STL을 잡았는데, 레드 블랙 트리를 모르고 map 자료구조를 구현할 수 없기 때문에 한 번 알아보기로 했다. *약간의 써칭 + 위키피디아 레드 블랙 트리를 참고해서 정리, 구현한 글입니다. 오류나 질문은 환영입니다! 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배..

이진 탐색 트리란?이진탐색을 위한 이진트리.모든 노드의 Key는 유일하다. (중복 없음)왼쪽 자식은 나보다 작다오른쪽 자식은 나보다 크다 이진 탐색 트리의 장점 일반 이진 탐색은 중앙 요소를 알아야하기 때문에 "배열"에서만 사용 가능. 연결 리스트는 이진 탐색에 적합하지 않다. 배열의 크기가 변화면 안되는 정적 이진 탐색 트리 배열을 사용해 탐색할 때보다 시간 복잡도가 작다 O(logN) 동적으로 데이터 집합 크기가 바뀌고 순서가 바뀌어도 문제가 없다. 주의할 점트리 모양이 한쪽으로 치우치면 트리 탐색의 장점인 O(logN) 시간복잡도가 마치 배열을 순차 탐색하는 듯하는 O(N)에 가까워지게 된다. => 데이터를 추가/삭제 할 때 트리 모양을 균형있게 만드는 "레드 블랙 트리"가 있다. (C++ map ..

2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 백준 2357번 최솟값과 최대값 문제를 풀면서 세그먼트 트리에 대해 접하게 되었다. 처음에는 DP로 풀어보려고 끙끙대고 있다가 안되길래 분류표를 보니 세그먼트 트리라는 걸 알 수 있었다.. 새로운 자료구조를 한번 정리해보기로 했당... 세그먼트 트리 (인덱스 트리)? 주어진 데이터의 `구간 합`과 `데이터 업데이트`를 빠르게 수행하기 위해 고안해낸 자료구조 형태 *구간 합과 다른 점은 데이터 업데이트가 빈번하게 일어나도 속력..

순열 ( next_permutation ) C++에서는 algorithm 헤더에 있는 next_permutation을 사용하면 쉽게 순열을 구할 수 있다. 파라미터로 순열을 구할 컨테이너의 시작과 끝 iterator를 인자로 받는다. bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); // custom bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp) next_permutation을 사용할 때 주의할 점 1. 오름차순으로 정렬된 값이어야 한다. 2. default로 operator < 를 사용해서..

그래프 알고리즘 '최소 비용' 대표 알고리즘 1. 다익스트라 알고리즘 2. 벨만- 포드 알고리즘 3. 플로이드 워샬 알고리즘 다익스트라 알고리즘 두 노드(시작 노드, 도착 노드) 사이의 최소 비용인 경로를 찾을 때 유용하게 사용된다. 다익스트라 알고리즘의 동작 원리 1차원 배열인 Dist[]라는 배열에 '비용' 들이 저장되어 있다. 초기 Dist 배열의 모든 값은 무한대(INF)로 초기화 한다. [동작 순서] 1. 시작 노드와 연결된 모든 정점들의 거리를 비교해서 업데이트 한다. 시작 노드를 방문 노드로 체크 2. 방문하지 않은 정점 중, 비용이 가장 적게 드는 정점을 선택한다. 해당 정점의 방문 노드 체크 3. 2번 과정에서 갱신될 수 있는 정점들의 거리를 갱신시켜준다. 4. 2~3 반복 1. 시작 노..