기술 블로그

1번a) 인접 행렬의 경우 n x n의 배열이 필요해서 시간복잡도가 o(n^2) 입니다.하지만 인접리스트의 경우 각 노드의 연결된 부분만 저장하므로 o(n+m) 입니다. 따라서 간선이 적은 sparce graph의 경우 인접리스트가 더 효율적입니다. b) 인접행렬의 경우, 각 정점에서 다른 모든 정점을 확인해야 하므로 o(n^2)의 시간이 걸립니다. 인접리스트는 각 노드의 실제 연결된 간선만 확인하믈 o(n+m)의 시간에 탐색이 가능하기에 DFS/BFS 알고리즘의 일반적인 시간복잡도입니다. c) 인접행렬은 n x n 배열을 재할당해야 하므로 정점 추가가 어렵고 비용이 크지만 인접리스트는 단순히 리스트에 빈 항목을 추가하면 되므로 정점 추가가 간편합니다. 2번무방향 단순그래프란?무방향 : 간선에 방향이 없..

Floyd-Warshall Algorithm가중치 방향 그래프 G=(V,E) V={1,2, ..., n}모든 노드 쌍들간의 최단경로의 길이를 구함d^k[i,j]중간에 노드 집합 {1,2,...,k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로 길이i.j 사이 어떤 노드도 경유하지 않고 가는 것은 무한대이다 라고 표시합니다. edge가 있으면 edge의 weight로 아니면 무한대로 표시합니다. 노드 i에서 j까지 가는데 1에서부터 n사이의 노드를 지날 수 있고 이것은 i에서 j까지 가는데 어떤 노드를 지나도 상관이 없다라는 것이고 이것이 i에서 j까지 가는 최단경로입니다. i^n[i, j] = 최단경로의 길이다 모든 i.j를 보는 것입니다. wij 자체가 만약 i에서 j로가는 edge가 있..

노드들을 반복해서 bellman-ford를 만들 수 있는 것에서 아무 에지나 릴렉스하지 않고 특별한 조건을 만족하는 relax에만 만족합니다. 그것이 dijkstra 알고리즘입니다. 초기화는 똑같습니다. 출발 노드만 distance estimator가 0이고 출발을 해서 첫번째 round에서 relax 할 때 distance 값이 최소인 노드를 찾습니다. 최소인 노드로부터 나가는 edge들만 relax합니다. 두번째 round에서는 다시 distance가 최소인 애를 찾는데 dijkstra 알고리즘은 이미 이전 round에서 선택이 되어서 edge들을 두번 선택할 필요는 없습니다. 이 노드의 최단 경로는 현재 노드가 가지고 있는 d[s] = 델타[s,s]입니다.dijkstra는 s만 0이고 나머지는 무한..

해쉬 테이블은 dynamic set을 구현하는 효과적인 방법 중 하나적절한 가정하에서 평균 탐색, 삽입, 삭제시간 o(1)보통 최악의 경우 o(n)해쉬함수는 h를 사용하여 키 k를 T[h(k)]에 저장h : U -> {0, 1, ... , m-1} 여기서 m은 테이블의 크기, U는 모든 가능한키들의 집합키 k가 h(k)에 해슁되었다고 말함 각 키에 대한 해쉬 함수값을 그 키를 저장할 배열 인덱스로 저장하는 것입니다. h(x) = x % m 이렇게 하고 search 할 때도 1024라면 24이기에 24에 가서 찾으면 됩니다. 해쉬함수의 예모든 키들을 자연수라고 가정 문자열ASCII 코드 : C=67, L=76, R=82, S=83문자열 CLRS는 (67*128^4) + (76 * 128^2) /// ..

입력 : n개의 도시, 도시와 도시를 연결하는 비용문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다. 해가 유일하지는 않음예 : (b, c) 대신 (a, h)왜 트리라고 부르는가?싸이클이 없는 연결된 무방향 그래프를 트리라고 부른다.MST 문제의 답은 항상 트리가 됨 왜?Generic MST 알고리즘어떤 MST의 부분집합 A에 대해서 Au{(u,v)}도 역시 어떤 mst의 부분 집합이 될 경우 에지(u,v)는 A에 대해서 안전하다고 합니다. Generic MST 알고리즘 1. 처음에는 a =공집합으로 합니다.2. 집합 a에 대해서 안전한 에지를 하나 찾은 후 이것을 a에 더한다.에지의 개수가 n-1이 될 때까지 2번을 반복한다. 안전한 에지 찾기그래프의 정점들을 두 개의 집합 s와 v-s로 분할..

Directed Acyclic Graph - DAG는 방향 사이클(directed cycle)이 없는 방향 그래프 - 예 : 작업들의 우선순위 위상정렬DAG에서 노드들의 순서화 v1, v2, ... ,vn, 단, 모든 에지 (vi, vj)에 대해서 i위상정렬은 답이 유효하진 않습니다. indegree가 0인 것을 찾습니다. 이는 그 작업에 선행해야 하는 작업이 존재하지 않는 것입니다. a와 g는 아무때나 해도 상관없는 것입니다. 맨 처음에 a를 먼저 해도 된다는 것입니다. 그래프에서 indegree에서 0으로 하는 것이 제일 중요하구나 라는 것을 알아야 하며 두 개 이상 존재하면 그 중 하나를 출력합니다. A에서 나가는 엣지들은 이제 생각할 필요 없습니다. 남은 그래프에서 indegree가 0인 ..

Directed Acyclic Graph - DAG는 방향 사이클(directed cycle)이 없는 방향 그래프 - 예 : 작업들의 우선순위 위상정렬DAG에서 노드들의 순서화 v1, v2, ... ,vn, 단, 모든 에지 (vi, vj)에 대해서 i위상정렬은 답이 유효하진 않습니다. indegree가 0인 것을 찾습니다. 이는 그 작업에 선행해야 하는 작업이 존재하지 않는 것입니다. a와 g는 아무때나 해도 상관없는 것입니다. 맨 처음에 a를 먼저 해도 된다는 것입니다. 그래프에서 indegree에서 0으로 하는 것이 제일 중요하구나 라는 것을 알아야 하며 두 개 이상 존재하면 그 중 하나를 출력합니다. A에서 나가는 엣지들은 이제 생각할 필요 없습니다. 남은 그래프에서 indegree가 0인 ..

그래프의 개념과 표현그래프 G = (V,E)V : 노드(node) 혹은 정점(vertex)E : 노드쌍을 연결하는 엣지(Edge) 혹은 링크(link)개체(object)들 간의 이진관계를 표현n = |V|, m = |E|V={1,2,3,4,5,6,7,8}E={(1,2),(1,3),(2,3),...,(7,8)}n=8m=11방향 그래프와 가중치 그래프방향 그래프(Directed Graph) G=(V,E)에지(u,v)는 u로부터 v로의 방향을 가짐가중치 그래프 에지마다 가중치(weight)가 지정인접행렬adjacency matrix정점이 n개인 것을 n x n으로 표현한 것입니다. 1번부터 n번까지 모든 정점을 넘버링 한 것으로 I번째 행 J번째 열을 a_ ij라고 한다면 있으면 1 없으면 0으로 표시합니다...

# 1. 알고리즘의 분석 * 알고리즘의 자원(resource) 사용량을 분석 * 자원이란 실행시간, 메모리, 저장장치, 통신 등 * 여기서 실행시간의 분석에 대해서 다룸 ## 시간복잡도 * 실행시간은 실행환경에 따라 달라짐 * 하드웨어, 운영체제, 언어, 컴파일러 등 * 실행시간을 측정하는 대신 연산의 실행 횟수를 카운트 * 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 * 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐 * 최악의 경우 시간복잡도(worst-case analysis) * 평균 시간복잡도(average-case analysis) ## 점근적(Asymptotic) 분석 ### 점근적 표기법을 사용 * 데이터의 개수 n → ∞ 일때 수행시간이 증가하는 growth rat..

순회 : 이진 트리의 모든 노드를 방문하는 일  Inorderpreorderpostorderlevel order Inorder 순회1. 먼저 T_L을 inorder로 순회하고2. r을 순회하고3. T_R을 inorder로 순회 INORDER-TREE-WALK(x)if x != NIL then INORDER-TREE-WALK(left[x]) print key[x] INORDER-TREE-WALK(right[x])x를 루트로 하는 트리를 inorder 순회 = 시간복잡도 O(n) PREORDER-TREE-WALK(x) if x != NIL then print key[x] PRE-ORDER-TREE-WALK(left[x]) PRE-ORDER-TREE-WALK(r..