Red-Black Tree특징모든 node는 BLACK 또는 RED의 색을 가진다.root node는 항상 BLACK이다.leaf node도 항상 BLACK이다.RED가 연속되어 있을 수 없다. (부모-자식간)root node부터 leaf node사이의 BLACK의 개수는 동일하다.self-balancing BST로 일반 BST와 다르게 5번 규칙에 의해 skewed binary tree가 되지 않음이 보장된다. (삽입/삭제 O(lgN) 보장)동작색상을 RED = 0, BLACK = 1, DOUBLE-BLACK = 2로 생각하면 이해하기 편하다.조회BST와 동일하게 수행삽입새로 삽입되는 노드는 항상 RED로 시작한다.부모노드가 조부노드의 왼쪽 자식인 경우를 가정하고 설명(오른쪽일 경우 대칭적으로 수행)부..

http://hongjun7.tistory.com/64

http://kks227.blog.me/220802519976 SCC구하는 알고리즘 중 Tarjan Algorithm에 대해 잘 정리해놓은 블로그 개인적으로 kosaraju Algorithm이 더 쉬운것같은데.. 이번에 문제풀다가 타잔알고리즘으로만 풀 수 있게 생긴문제가 나와서 공부하게됐다. 그 문제 : https://www.acmicpc.net/problem/13988

Maximum Sum Subarray라 불리는 문제에서 슬라이딩 윈도우기법으로 O(N)에 해결하는 알고리즘 Maximum Sum Subarray란 수열의 연속 부분합중 가장 큰 값을 찾는 문제 Kadane Algorithm을 간략히 설명하자면 1. 앞에서부터 수를 하나씩 더해가면서 sum이라는 변수에 매번 값을 저장한다. 2. 만약 sum이 음수가 되는 지점이 발생한다면, sum은 0으로 초기화한다. 3. 이 sum들을 매번 maximum값으로 갱신한다. 구간의 index가 필요하다면 sum을 갱신하는 부분에 추가하여 나타낼 수 있다. 위의 내용은 1-dim array에 관한 내용이고 이를 응용하면 2-dim array에서의 문제는 O(N^3)에 해결할 수 있다. (2차원 배열에서 최대 부분합) 참고영상..

잘 정리된 블로그가 있어서 링크로 대체한다. 다익스트라 알고리즘(Dijkstra Algorithm) : 한점 - 다수의점 (음수가중치X)벨만-포드 알고리즘(Bellman-Ford Algorithm) 한점 - 다수의점 (음수사이클X)플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 모든점 - 모든점

Quick Sort : O(NlogN), 최악의 경우 O(N^2)을 보장하는 소팅. Heap Sort : O(NlogN)을 보장하는 소팅 Radix Sort : O(dN)을 보장하는 소팅(자리수) 으로 이론적으로만 알고있어서 오늘 구현해본결과, 속도차이가 그닥 나지않음을 발견했다 알고리즘공부하면서 Big-O표기법에 대해 항상 께림직했던게, 결국 Big-O는 수학에서 말하는 N이 충분히 큰 경우(sufficiently large) 계수는 무시할 수 있기에, 계수를 제외한 값을 표현해준다는 것이다. Quick Sort는 별 할말이없다. 워낙 유명한 소팅이라.. 굳이 한마디 하자면 pivot을 그지같이 잡거나 해서 최악의 경우 N^2이라곤 하지만, 생각보다?(이름만큼?) 속도가 빠르다 Heap Sort Hea..

1. 다익스트라로는 B->C->D경로를 고려할 수 없다. 2. +@해서 모든값을 양수로 바꾼다면 거쳐가는 경로수*@가 되므로 제대로 된 계산이 될 수 없음.

아래 셋은 하는 일이 거의 동일하므로 아무거나 골라 쓰면 됩니다. 개인적으로 Index Tree을 추천합니다.Fenwick (BIT, Binary Indexed Tree)https://www.acmicpc.net/blog/view/21Index Tree (정식 명칭 없음) int N = 15; int l = 3; int r = 8; int left = N+l; int right = N+r; while(left