말랑한 하루

[ 개념 ] 거쳐가는 정점을 기준으로 최단거리 구하기 [ 시간복잡도 ] O(|n|^3) [ 흐름 ] Dynamic Programming의 일종! 현재까지 계산된 최소비용을 나타내는 정점에대한 테이블이 필요함! 이를 나타낼때 Array[y][x] = y->x로 가는 비용으로 나타냅니다. 플로이드와샬은 자기 자신으로 되돌아오는 길이 존재하지않습니다. 그래서 (1) 자기자신으로 되돌아오는 길을 배제할것 (2) 현재위치에서 다른정점을거쳐 현재위치로 올 수 있는 경우와 비교하여 최소값을 가져가면됩니다. 즉, 정점 1, 2, 3이 존재할 때 1->3 의 값과 1->2->3 으로 가는값을 비교하는겁니다 이를 나타내면 Array[1][3] compare Array[1][2] + Array[2][3] 이 됩니다. 위 두..

[ 개념 ] 이진트리로 구성된 정적트리 [ 시간복잡도 ] O(n logn) [ 흐름 ] (1) 최상위 Root Node가 1부터 시작함 → 자식노드를 찾아가기 편하게 하기위해서 (2) 자식노드들은 부모노드의 2배이거나 2배+1노드로 분배 → 왼쪽자식 Left_node = root_node *2 , 오른쪽자식 Right_node = root_node*2+1 (3) 세그먼트트리 전체 노드의 개수는 배열의크기보다 큰 제곱근 중 가장 작은수의 두배이다 → ArySize = 9 일때, 9