분류 전체보기

Backtracking은 DFS와 같은 방식으로 트리를 탐색하는 방법 중 하나다. 탐색을 진행하다가 더 갈 수 없으면 다시 이전 노드로 돌아와 탐색하는 방법이다. Sum of Subsets 문제도 backtracking으로 풀 수 있는 문제 중 하나다. Sum of Subsets은 집합 wi의 부분 집합 중 그 합이 W와 같은 부분 집합들을 찾는 문제다. 예를 들어서, 𝑛 = 5, 𝑊 = 21, and 𝑤𝑖 = [5, 6, 10, 11, 16]이 주어졌다고 하자. 그러면 21이 될 수 있는 조합은 {5, 6, 10}, {5, 16}, {10, 11}이다. 이렇게 푸는 것을 상태공간트리를 만들어서 풀어보자. 왼쪽은 wi를 포함시키는 것이고 오른쪽은 wi를 포함하지 않을 때의 값이다. weight가 ..

K번째로 작은 값 찾기Median of MediansQuick sort으로 Selection 문제를 접근하는 데에 있어 불균형을 해결하기 위해서, 비교적 균등하게 배열을 나누는 알고리즘이다. 문제를 푸는 방법은 다음과 같다. 1. 배열 L을 5개씩 묶어준다. 즉, n/5로 분할한다.2. 각 묶음에서 median 값을 찾는다. 이때, 묶음은 5개이므로 6번 비교하면 median 값을 찾을 수 있다. 비교 횟수는 총 (6 * n/5)번이다.3. Median들 중에서 median인 m*을 찾는다. 이때 T(n/5)가 걸린다.4. m*과 비교해서 loser 그룹과 winner 그룹으로 나눈다. 비교 횟수는 총 n번이다.5. 재귀호출하거나 m*를 반환한다. 이때 T(|loser|) 이거나 T(|winner|) 시..

K번째로 작은 값 찾기Quick sortn과 K가 주어질 때 K 번째로 작은 값을 찾아야 한다. Quick Sort 방식으로 pivot보다 작은 것은 왼쪽, 큰 것은 오른쪽에 두고 pivot이 K번째에 위치할 때까지 재귀적으로 반복하여 푸는 방법이다. 먼저 pivot을 선택한다음에 Loser 배열과 Winner 배열로 나눈다. Loser는 pivot보다 작고 Winner은 pivot보다 큰 값들의 배열이다. pivot과 같은 값이면 M 배열에 집어 넣는다. 이 배열들을 만들기 위해서는 n-1번의 비교가 필요하다. Loser 집합의 개수가 K보다 큰 경우우리가 찾으려는 K가 Loser에 존재한다는 뜻으로, K번째 값을 반환하면 된다.Loser 집합의 개수와 M 집합의 개수가 K보다 작은 경우우리가 찾으려는..

일반적으로 Selection Problem은 정렬되지 않은 배열에서 K번째로 큰 값 혹은 작은 값을 구하는 문제이다. K = 1이라면, 그 배열에서 가장 큰 값 혹은 가장 작은 값을 구하고 K = 2라면 2번째로 큰 값 혹은 2번째로 작은 값을 찾으면 된다.입력 : n개의 값과 K(1출력 : K번째로 크거나 작은 값목표 : 비교 횟수를 최적화하는 것 최댓값 찾기(K = n)K = n일 때, S 배열에서 가장 큰 값을 찾아야 한다. S 배열의 수가 n일 때, n-1번 비교해야 한다. n-1 번이면 항상 최댓값을 찾을 수 있기 때문에 상한(Upper Bound)이라고 한다. n-1 번이면 최솟값을 찾기 위한 하한(Lower Bound)이다.  최솟값과 최댓값을 동시에 찾기(K = 1, K = n)최댓값과 최..

이전 글에서는 Knapsack problem을 Backtracking으로 접근하여 최적 해를 구했다. 이 방법은 bound가 maxprofit보다 크지 않을 때 non-promising이라고 판단한다. 알고리즘의 효율성을 따지면, 조금 더 나은 방법이 있다.그 방법은 branch and bound로 접근하는 것이다. 이 방법의 특징을 잘 살리면 bound를 보고 판단하는 것 외에, promising한 노드들의 bound를 비교해서 그 중에서 가장 좋은 자식 노드들만 방문할 수 있다. DFS처럼 이미 정해진 순서대로 노드를 방문하는 것보다 더 빠르게 최적값을 찾을 수 있다. 이런 방법을 Best-First Search with branch and bound라고 한다. 이러한 방법은 BFS 방식을 약간 수정..

Knapsack Problem은 아주 유명한 문제이다. 어떤 배낭이 있고 그 배낭에 넣을 수 있는 최대 무게가 W라고 하자. 배낭에 넣을 수 있는  n개의 물건이 각각 무게 wi와 이익 pi를 가지고 있을 때, 배낭이 최대한 비싼 물건들을 담을 수 있는 조합을 찾는 문제이다. knapsack 문제는 원하는 만큼 물건을 쪼개어 담는 문제인 Fractional Knapsack와 물건을 쪼갤 수 없어 무게와 가치가 무조건 정수형태를 가지는 0-1 Knapsack 두 유형으로 나뉜다. 이번에는 0-1 Knapsack 문제를 해결하는 방법에 대해서 생각해보자.먼저 마디가 promising한지 판단해야 한다. Greedy Algorithm으로 접근하면, 해당 아이템의 무게가 배낭에 넣을 수 있는 최대 무게 W보다 ..

Switch현재 이더넷은 star topology 형태로 동작하기 때문에 스위치나 허브의 도움이 필요하다. 스위치와 허브의 차이를 잠깐 짚어보자면, 허브는 각 노드의 위치를 저장하고 있지 않기 때문에 데이터를 받으면 연결된 모든 기기에 데이터를 전송한다. 반면에 스위치는 스위치 테이블이 있어서 해당하는 기기에만 데이터를 전송한다. 스위치가 테이블을 만드는 과정을 알아보자.  스위치는 처음에 모든 기기에 대한 정보를 가지고 있지 않는다. 스위치는 라우터와 같이 프로토콜을 사용해서 테이블을 만드는 것이 아니라 Self-Learning으로 테이블을 만든다. 스위치로 프레임이 들어오면 송신자 주소를 확인하고 이를 스위치 테이블에 기록한다. 스위치에 연결된 모든 기기들이 한번씩 프레임을 보내면 테이블이 완성된다...

이더넷 형태이더넷은 물리적으로 동축케이블 기반 버스 형태를 주로 사용했었다. 그러나 하나에 문제가 생기면 네트워크 전체에 문제가 발생하는 단점이 있었고 최근에는 switched 형태로 사용하고 있다. 아래 그림처럼 A가 B로 패킷을 전달할 때 동시에 C에서 D로도 패킷을 전달할 수 있다.  이더넷 프레임 구조이더넷은 네트워크 카드라고 하는 것으로 구현되어 있는데, 카드마다 이더넷 프레임 구조가 다른다. 일반적으로 주로 사용되는 프레임 구조는 다음과 같다.Preamble : 동기화하는 것으로 다음부터 패킷임을 알려주는 필드Destination Address, Source Address : destination 주소가 broadcast이거나 본인을 가리킬 때 데이터를 읽어야 한다. Type : 프로토콜이 명..

지금까지 한 번에 여러 기기가 데이터를 보낼 때 충돌을 감지하고 충돌에 대처하는 방법을 배웠다. 이러한 데이터를 보낼 때 패킷 헤더에 destination, source 주소를 넣어 보내는데, link layer에서는 어떻게 이를 처리하는지 알아보자.Addressing, ARP 모든 기기는 IP 주소와 MAC 주소를 가진다. IP 주소는 네트워크에 들어갈 때 부여 받는 주소이지만 MAC 주소는 기기가 만들어질 때부터 공장에서 번호를 찍어 나오는 주소이다. 학년이 올라갈 때마다 반, 번호가 바뀌는 것처럼 IP 주소도 같은 원리이고, MAC 주소는 사람의 주민등록번호처럼 영원히 바뀌지 않는 주소라고 생각하면 된다. IP 주소는 32비트 주소 체계를 가지고 있고, MAC 주소는 48비트 주소 체계를 가진다. ..

링크 계층에서 오류를 탐지하고 정정하는 방법을 배웠다. 이번에는 링크 계층에서 여러 기기가 한 번에 데이터를 전송할 때 서로 충돌이 발생하지 않도록 방지하는 방법을 배울 것이다. MAC(Media Access Protocol)링크에는 2가지 타입이 있다. point-to-point는 1대1 연결로 한 기기가 보내면 한 기기는 받는 역할이기에 충돌이 발생하지 않는다. 그러나 Broadcast는 여러 기기가 하나의 링크를 공유하기 때문에 충돌이 발생할 수 있다. 때문에 데이터 링크 계층에는 다중 접속 문제를 해결하기 위한 방법이 필요하다. 그래서 나온 것이 Media Access Protocol(MAC)이다. 이는 broadcast 채널에서 여러 기기가 하나의 버스를 공유할 때 충돌이 발생하는 것을 관리하는..