오래 못 할 짓 하지 않기

BI - Connected Component : Undirected + Maximal biconnected subgraph  ● Articulation Point: Vertex V가 사라졌을 때 하나의 Component가 2개로 나눠질 때!  해부학적으로는 '관절'이라 생각하면 될 것 같다.  = 다리에서 무릎 관절 역할!   ▶ BI-Connected 라는 것은  하나의 Vertex가 사라져도 하나의 Component가 분해되지 않는 것!! 위 그래프는 Bi-Connected가 아니다. 이걸 쪼개면 오른쪽같은 단위로 쪼갤 수 있고, 그만큼이 Articulation Point라는 뜻이므로Articulation Point가 존재한다는 건 Bi-Connected가 아니라는 것!     이렇게 생긴 Tree에..

DAG에서 Dependency가 있는 그래프에서각각의 Task의 Duration이 정해져있다.  외출하는 데 필요한 작업들은 다음과 같다.하지만 이 중에서도 순서가 중요함.   Time Complexity는 세타 ( Vertex + Edge ) 우리가 각 노드에 대해서 알아야 하는 건- Earliest start time ( EST )         =  앞에 완료되어야 하는 애가 끝난 시간 - Earliest finish time ( EFT ) 이다.    = EST + Duration    EST 를 계산하는 건Dependency가 있는 노드의 앞에 완료되어야 하는 작업이 있다면그 작업 중에 가장 Max로 끝나는 시간으로 한다.  Vertex가 Weight에 영향을 받는다는 개념으로 풀어야 한다.방향..

Topological sort위상 정렬 DAG 에서 이루어진다.= Directed Acyclic Graph ( 비순환 방향 그래프 ) 위상 정렬이란 DAG에서 정점을 선형으로 정렬하는 것을 말한다.   (u,v) 이렇게 있는 Edge는 u먼저 오고 그 뒤에 v가 오는 Edge를 말한다.    우선 DFS로 한 번 돌리고Finished Time가 큰 순서대로 정렬을 한다.  주로 예시로는 옷을 입는 걸로 예시를 들 수 있다.  우선 (자신을 가리키는 게 없는 vertex에 한해서) 어디서 먼저 시작하든제대로 된 결과가 나올 것이다. Pants 를 먼저 입으면 안 되고, 그 전에 Underwear를 항상 먼저 입어야 하며,Watch같은 경우는 무엇을 하든지 중간에 끼어들어서 할 수 있다. Finish Tim..

Depth First Traversal 들어갈 수 있는만큼 최대한 들어갔다가 나오는 것 ● BFS = Level order   →  같은 레벨들 차례차례 보고 내려감 ● DFS = Pre in Post order로 할 수 있음→ 인접해있는 아래 노드로 쭉 내려감→ 다 Explore 했으면, Backtrack 하여 돌아온다.    = 어디서 왔는지 알아야 함     = Stack 형식으로 구현한다.     특징) 1. 인접한 Vertex가 이미 Discover되었다면,     그 사이에 있는 Edge는 Explore는 되지 않지만, Check는 되었다고 할 수 있다. 2. 색깔별 의미    ● White  : Discover되지 않음    ● Gray    : Discover 되었지만 작업하지는 않음  (..

Graph Traversal: Graph G에 있는 모든 Vertex를 방문하는 것이다.  ● 모든 Vertex를  ● 한 번만 방문하는 알고리즘 2가지1) BFS ( Breadth First Search ) - QUEUE 로 구현2) DFS  ( Depth First Search )   - STACK으로 구현   BFS ( Breadth First Search )(Tree 형태 기준) Level Order 방식 Root 로 설정한 노드에서 연결되어있는 노드들을 Discover 하고 , 그 사이에 있는 Edge를 Explore 했다고 할 수 있다.+ Discover and Explore의 기준은 목적지에 있는 노드가 Discover 되지 않았을 때  1. Root 노드인 A → 연결되어있는 B,C 를 (..

Knapsack problem ( 배낭 알고리즘) 한 도둑이 박물관에 쳐들어가서 물건을 훔친다. 가져갈 수 있는 배낭의 크기는 정해져 있으므로 어떻게 훔쳐야 가장 이득(?)일까? 를 고려하는 알고리즘이다. 케이스는 두 가지로 나뉜다. 1) 0-1 knapsack : 조각상이나 모나리자 같은 작품은 가져오거나 안 가져오는 거임. 쪼개거나 부수면 가치가 사라진다. = 담으려는 Item을 쪼갤 수 없는 경우 이런 경우에는 DP로만 해결할 수 있으며 Greedy 알고리즘은 효과가 없다. 2) Fractional kanpsack : 다이아가루, 금가루는 그냥 쪼개서 들고 나와도 괜찮음 = 담는 Item을 쪼갤 수 있는 경우 이 때는 반대로 Greedy 알고리즘만 사용할 수 있다. 1. Fractional knap..

칸 채우기 [ 값 채우는 Table , 어디에서 잘라야 Optimal인지 저장하는 Table 나눠야 함 ] 답 ▼ 더보기 문제 : 동전 개수 최소화 하는 문제가 Greedy 알고리즘으로 안 될 수도 있다. 그런 경우를 제시해봐라. 100보다 작은 값에, Coin 개수가 4개인 걸로. ▶ (영국 돈 단위) 잔돈은 30원인데 , 동전 단위는 {1,10,25} 일 때, ● Greedy 알고리즘 : 25 *1 + 1*5 = 6개 ● DP 알고리즘 : 10 * 3 = 3개로 바로 끝남 DP 알고리즘으로 해서, 각 위치별로 동전 개수를 채워넣는다. 3,3을 보자. ▶ 3원을 거슬러 줘야 한다. ▶일단 뺄 수 있는 1원을 빼면 2가 남는다. ▶ 2원을 거슬러 줄 때 Optimal값을 사용한다. = 2 , 내가 뺐던 ..

우리는 문자를 0과 1로 표시하여 나타내려고 한다. Huffman 알고리즘은 Text Encoding 을 위한 알고리즘이다. : 문자의 출현 빈도에 따라 다른 길이를 사용하여 압축한다. = 많이 나오는 문자는 짧은 길이로, 그렇지 않으면 길게 표현하여 비트 수를 줄인다. 우선 이걸 이해하기 전에 Prefix라는 개념을 이해해야한다. Prefix (free) code : 어느 하나의 코드가 다른 하나 코드의 접두code가 되지 않아야 한다. - 목적 : 모호성( Ambiguity ) 을 피하기 위해 - 원인 : Huffman 코드는 각 문자마다 다른 길이를 사용하기에 어느 길이만큼 잘라야 하는지에 대한 Ambiguity 이 있다. ex) [ A, B, C, D ] 라는 문자를 각각 [ 0, 01, 10 ,..

An Activity-Selection Problem : 각 Exclusive한 Activity 에 스케줄이 있고, 그 Activity들의 수를 최대한 많이 선택하는 문제 ex) 주어진 시간동안 많은 놀이기구를 타는 경우 [ 2 ,3 ) [ 3, 5 ) 는 서로 Mutually compatible하다. *Compatible : 'Overlap이 없다' ▶ Compatible한 Activity들을 최대한 많이 선택하기 si = 시작하는 시간 → [ fi = 끝나는 시간 → ) ● S 라는 set은 n 개의 activity 가 있다. ● Si,j 는 ai로 시작해서 aj로 끝나는 S의 Subset이다. 얘를 DP로 풀어보자. 1. 우선 Si,j에 대한 Optimal schedule을 구한다. - 양 끝 ai..

보호되어 있는 글입니다.