공대생 도전 일지

퀵 정렬 Alg quickSort(l) 1. if(l.size()>1){ k = a position in l lt, eq, gt = partition(l,k) quickSort(lt) quickSort(gt) l = merage(lt,eq,gt) } 2. return 피봇을 기준으로 큰 것은 오른쪽, 작은것은 왼쪽으로 나눈뒤 그 나눈 것 다시 재귀하여 크기 1이 될 때 까지 돌리기. 합치는 것은 그대로 합치기 분할 합병정렬에선 merge가 오래걸렸지만 퀵정렬에서는 partition이 오래걸린다. Alg partition(l,k) 1. p = l.get(k) 2. lt,eq,gt = empty list 3. while(!l.isEmpty()){ e = l.removeFirst if(e p} gt.addLa..

기말 요약 퀵 기본 원리 1. lt, eq, gt = partition(l,k) 2. quickSort(lt) 3. quickSort(gt) partition(l,k) 1. p = l.get(k) 2. e = l.removeFirst 3. if (e p} gt.addLast(e) 4.return lt,eq,gt inPlacePartition(a,l,r,k) 1. p = a[k] 2. a[k] swap a[r] 3. i = l 4. j = r-1 5. while(i

연습문제 n개의 항목집합 S의 각 항목 i는 양의 이득 bi와 양의 무게 wi로 이루어졌다. 주어진 무게 W를 넘지 않으면서 최대 이득이 되는 S의 부분집합을 계산하는 효율적인 탐욕 알고리즘 Fractional-knapsack(S,W)을 작성하라 Alg fractionalKnapsack(S,W) 1. for dach i to S{ xi = 0 vi = bi/wi //무게에 따른 효율 } 2. w = 0 3. Q = a priority queue contaning all the items of S using vi as keys 4. while (w < W){ i = Q.removeMin() //왜 remove min인진 모르겠지만 고효율 부터 뽑아서 넣는다. xi = min(wi,W-w) // 무게가 넘치..

인경이는 외국어를 좋아하여 다음 아홉개의 언어 과목을 수강할 계획을 세우고자 한다. LA15, LA16(LA15), LA22, LA31(LA15), LA32(LA16,LA31), LA66, LA67, LA71, LA89 각 과목에 대한 선수 과목들은 괄호안에 있다. 그냥 LA15,LA16, LA31순서로 듣고 나머진 맘대로 들으면 되는거 아님? ㅇㅈ 답은 무쟈게 많다. 피보나치 수열 만들기 선형공간으로 수행하는 버전 이건 배열을 하나 만들어서 쭉 작성해놓기 Alg f(n) 1. if(n = 0 || n = 1) return 1 2. A[0] = 1 3. A[1] = 1 4. for i = 2 to n A[i] = A[i-1] + A[i-2] 5. return A[n] 상수공간으로 수행하는 버전 이건 와일..

요약 최단경로 문제는 가중그래프와 두 개의 정점 u와 v가 주어졌을 때 u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제를 말한다. 출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다. 이를 단일점 최단경로라고 부른다. 가중 방향그래프에 음의 무게를 가진 싸이클이 존재한다면 최단경로는 존재하지 않는다. 마찬가지로 가중 무방향 그래프에 음의 무게를 가진 간선이 존재해도 최단경로는 존재하지 않는다. 최단경로를 찾는 알고리즘은 그래프의 형태에 따라 선택이 달라진다. 즉, 음의 무게를 가진 간선이 있는지 없는지, 무방향인지 방향인지, 그리고 비싸이클(DAG)인지 아닌지에 따라 최적 알고리즘이 따로 존재한다. Dijkstra 최단경로 알고리즘은 탐욕법에 기초하며 음의 무게를 가진 간선이 없..

요약 가중그래프는 그래프 내 간선이 무게 또는 비용이라 부르는 관련 수치값을 가진 그래프를 말한다. 최소신장트리는 가중 그래프의 간선 무게의 합이 최소인 신장트리다. 최소신장트리의 두 가지 중요한 속성인 싸이클 속성과 분할 속성은 MST 알고리즘의 정확성 검증에 사용된다. 탐욕법은 일반적인 알고리즘 설계 기법 가운데 하나다. 중요한 요소로는 다양한 선택으로 된 구성과 최대화 또는 최소화해야 할 목표가 있으며, 탐욕적 속성이 있는 문제에 적용할 경우 잘 맞는다. MST를 구하는 Prime-Jarnik, Kruskal, Baruvka 알고리즘은 최악실행시간이 O(mlogn)으로 동일하지만 외부 데이터구조 사용과 접근 방식에 있어서 상이하다.

요약 방향 그래프는 모든 간선이 방향간선인 그래프를 말한다. 방향그래프 G의 어느 두 정점 u와 v에 대해서나 u와 v에 도달하며 v는 u에 도달하면 G를 강연결이라고 말한다. 동적프로그래밍은 언뜻 보기에 많은 시간이 소요될 것 같은 문제에 주로 적용한다. 적용에 적당한 문제들은 공통적으로 부문제 단순성, 부문제 최적성, 부문제 중복성 등 세 가지 특성을 가진다. 방향 비싸이클 그래프는 방향싸이클이 존재하지 않는 방향그래프를 말한다. 방향그래프의 위상순서는 모든 i < j 인 간선 $(v_i,v_j)$에 대해 정점들을 번호로 나열한 것을 말한다. 위상 정렬은 DAG로부터 위상순서를 얻는 절차를 말한다. 진입차수를 이용하는 방법과 DFS를 특화해서 얻는 방법 등 두가지 방식이 있다.

최단 경로 최단 경로 속성 최단경로의 부분경로 역시 최단경로다. 출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다. 이를 단일점 최단경로라고 부른다.음의 무게를 가지는 간선과 싸이클 가중 방향, 무방향 그래프에 음의 무게를 가진 싸이클이 존재한다면 최단경로는 존재하지 않는다. 그래프 알고리즘 시간 음의 무게를 가진 간선이 없는 그래프 Dijstra $O(mlogn) or O(n^2)$ 음의 무게를 가진 간선이 있는 방향 그래프 bellman-Ford $O(mn) 비가중그래프 BFS $O(m+n)$ DAG 위상순서 $O(m+n)$ ## 최단경로 알고리즘 ### Dijkstra Alg DijkstraShortestPaths(G,s) 1. for each v to G.vertices() d..

최소 신장 트리 가중그래프 각 간선이 무게라 불리는 수치값을 가진다. 최소 신장 트리 신장 부그래프란 그래프 G의 모든 정점들을 포함하는 부그래프를 말하며 신장트리는 (자유) 트리인 신장 부그래프를 말한다. 가중그래프 G의 최소신장트리MST는 G의 신장트리 가운데 간선 무게의 합이 최소인 것을 말한다. 최소 신장 트리의 속성 싸이클 속성 T를 가중그래프 G의 최소신장트리라 하자. e를 T에 존재하지 않는 G의 간선으로 e를 T에 추가하여 형성된 싸이클을 C로 가정하자. 그러면 C의 모든 간선 f에 대해 weight(f)

방향 그래프 모든 간선이 방향 간선인 그래프 속성과 구현 진입간선(in-edge)와 진출간선(out-edge)들을 별도의 부착리스트로 보관한다면 진입간선의 집합과 진출간선의 집합을 각각의 크기에 비례한 시간에 순회할 수 있다. 방향 DFS 간선(v,w) 트리간선 : w가 v의 자식이다. 후향간선 : w가 v의 조상이다. 전향간선 : w가 v의 자손이다. 교차간선 : w가 v와 동일하 레벨 또는 직계가 아닌 다음 레벨에 위치한다.강연결성 정점 u와 v에서 서로 도달 가능하다면 강연결 그래프라고 한다.강연결 검사 G의 임의의 정점 v를 선택 G의 v로부터 DFS를 수행 방문되지 않은 정점 w가 있다면 False를 반환 G의 간선들을 모두 역행시킨 그래프 G&#39;을 얻음 G&#39;의 v로부터 DFS를 수..