Reliable data Transferflow control : dst에서 데이터를 처리하는 속도보다 src가 더 빨리 보내지 않도록 하는 것error control error detection : retransmission 요구(ARQ) -> 패킷에서 한 비트만 에러가 발생하더라도 다 버리게 되어있음error correction : 문제가 있는 비트를 맞게 바꿔줌 (Forward Error Correction)feed back feed forwardfeed back 시스템은 다시 보낸 시도가 어떠한 시스템에 영향을 미치는데feed forward는 정방향으로만 흐름이 흐른다. 즉, 다시 되돌아가서 영향을 미치지 않음 ex)12개의 비트로 이루어진 패킷이 있다고 가정해보자101101011011에러가 발..

Routing AlgorithmRouting Algorithm : 루트를 결정하는 알고리즘 (Host-to-Host) & algorithm that finds that least cost path Graph G = (N, E)N = set of Nodes (ROUTER)E = set of Links Cost = 여러 상황을 고려하여 링크에 부여되는 값으로, 한 라우터에 많은 부담이 생기면 바뀔 수 있음cost는 물리적인 거리만 고려한 것은 아니다 라우터를 거치지 않는 것이 더 적은 cost가 드는 것은 아니다.파란색은 cost가 5, 빨간색은 cost가 4이기 때문에 결국 빨간 경로가 cost가 더 작다. c(x,y) or \(C_{xy}\) : 둘 다 x,y의 cost를 나타낸다.If (x,y) \(\..

어떤 문제가 있다4쌍의 부부가 와서 서로 악수를 하는데, 부부끼리는 악수를 하지 않는다.최소 0번 최대 6번의 악수를 할 수 있게 된다그런데, 사람들에게 악수한 횟수를 물어보니 숫자가 7개 다 나왔다.그러면 사람이 8명인데 숫자가 7명이기 때문에 무조건 겹치는 숫자가 하나 나오게 된다이때 겹치는 숫자는 무엇인가? 어딘가는 6이 있어야한다. 즉, 자신의 부부 빼고 모두 악수를 했기 때문에 6과 0은 부부이다0,6을 제외하고 3쌍의 부부만 남는다고 생각하자그럼 3쌍의 부부에게는 최소 0번 최대 4번의 악수를 할 수 있다. 이때 0,4를 또 하나의 부부로 생가각하여 없앨 수 있다.이 과정을 반복하면 1,5 2,4 3,3 이렇게 부부가 되어3이 두번 겹치는 것을 알 수 있다 이것과 Topological Sort..

BCCBiconnected Component : Connected component + Maximal = 연결된 노드에서 노드 집합을 늘릴 수 없을 때까지 늘린것Parts of Graph separated by Cut Vertices Two Nodes in a BCC has two completely different Paths connecting them : edge도 node도 겹치지 않음Meaning of "Separated" can be confusingCut vertex와 반대의 개념이라고 생각할 수 있음connected component들은 노드들은 파티션으로 나눔biconected component는 cut vertex로 나뉘며, 이 cut vertex는 중복되어 들어갈 수 있음 여전히 Cu..

Def Cut VertexRemoving a node s makes Graph DisconnectedExists x and y s.t., all paths from x to y goes through s : 노드 x, y가 있어서 x, y를 연결하는 모든 path가 s를 지나감연결된 그래프에서만 생각한다연결된 그래프에서 특정 노드를 지우면 끊어진 그래프가 될 때 그 노드를 cut vertex라고 한다G = (V,E)|V| = n, |E| = mundirected graph (=>) 노드 S를 제거하면 Connected component가 여러개 생김서로 다른 connected component 에서 x, y라는 노드를 각각 고름이러면 x, y 로 통하는 path 가 없다. 따라서 현재 s를 제거하면서 이..

DFS Tree전진(재귀 호출)을 한 edge로 만듦DFS Tree is the Result of DFSUsually analyze DFS Tree to get information DFS Tree에 있는 edge를 Tree edge라고 부른다그리고 Tree edge에 포함되지 않은 것들을 Back Edges라고 한다 Edges of input Graph becomes Tree or Back edges of DFS TreeBack edges는 전부 자손과 조상을 연결하는 것 밖에 없다그 이유는, 조상이 아닌 다른 것과 연결되어 있었다면, 아래로 호출했을 것이다. 파란색 선을 back edge라고 가정한다면이미 노드가 연결되어있다는 것이다.그렇가면, 만약 맨 아래 leaf가 DFS를 통해 저 노드를 호출할..

TraversalVisit Nodes of a Graph in Some order : 그래프의 노드들을 특정한 순서로 지나간다.May go through a node Several TimesWhile doing some CalculationUsually After the Traversal Some Data Structure Results : Useful Information Extracted 결과적으로 어떤 "정보"가 나오게 된다 Any-Order traversalStart at a Node s (put s into BOX)While BOX is not Emptytake one node from BOXIf Node not Marked -> Mark Node -> Do Computation on Node ..

금화 모으기 만약 연속으로 같은 방향으로 가지 못한다는 규칙이 있다고 생각하자해당 칸에 왔을 때, 이전 방향을 기억하고 있어야한다결국, 중간 부분에서 왼쪽에서 오는 것인지 아래에서 오는 두 가지 모두 알고 있어야한다 결국 과거 일을 덜 기억해야할 수록 더 쉽다 로봇이 (i,j)에 도착할 때까지 모을 수 있는 최대 금화 개수 Pseudo Polynomial 설명 pseudo polynomial 이라는 알고리즘들 중 하나이다.어떤 입력이 n일 때 O(\(n^2\))이 걸린다.n개의 숫자가 얼마나 큰지 작은지에 상관 없이 우리는 항상 n이라고 생각한다. 작은 값들과 큰 값들은 연산에 차이를 보인다사실은 비트 수에 따라서 비교를 해야하기 때문에 엄청나게 큰 숫자는 작은 숫자와 연산에 차이가 있다 즉, 비교하는데..

다양한 Alignment 문제들을 의미한다. edit distance보다 좀 더 확장된 의미이다. Global, Local, Semi-local Alignment ProblemsGlobal Alignment는 두 개의 문자열을 gap symbol("-")을 포함하도록 확장하여 같은 길이의 문자열로 만드는 문제이다edit distance의 경우, gap 부분에 insert한다고 생각하면 된다대응되는 문자들의 쌍에 대하여 score가 입력으로 주어진ㄴ다대응되는 문자들의 쌍들의 score 합의 최대치가 되는 alignment를 구하는 것이 목적이다alignment 문제들은 대부분 동적 계획법으로 해결된다Global Alignment두 개의 스트링 acvcdb와 cadbd가 있을 때 두 스트링은 얼마나 비슷한가..

근사 문자열 매칭 (approximate string matching)비슷한 문자열 비교주어진 문자열과 비슷한 문자열을 검색 ex) 검색 엔진 유사어 추천 등..비슷한 것이라는 것은 무엇인가?이때 사용하는 것이 거리함수이다. 거리 함수해밍거리 (Hamming distance) : 단순 문자열 매칭으로 다른 자리의 갯수 - 글자가 끼어들거나 빠지거나 할 수 없는 경우 사용할 수 있음 편집거리 (edit distance) : 첫번째 문자열을 두번째 문자열로 바꾸는데 얼마나 많은 editing 작업을 해야하는가? 가중편집거리 (weighted edit distance)  편집 거리한 문자열을 다른 문자열로 변경하기 위해 필요한 편집 연산 (edit operation)들의 최소 수 편집 연산삽입 (Inserti..