2.1 네트워크의 기초 2.1.1 처리량과 지연 시간 네트워크 - 노드와 링크가 서로 연결되어 있으며 리소스를 공유하는 집합 노드: 서버, 라우터, 스위치 등 네트워크 장치 링크: 유선 또는 무선 좋은 네트워크 - 많은 처리량을 처리할 수 있으며 지연 시간이 짧고 장애 빈도가 적으며 좋은 보안을 갖춘 네트워크 처리량: 링크 내에서 성공적으로 전달된 데이터의 양 (얼만큼의 트래픽을 처리했는지) 트래픽: 특정 시점에 링크 내에 흐르는 데이터의 양 대역폭 - 주어진 시간 동안 네트워크 연결을 통해 흐를 수 있는 최대 비트 수 지연 시간 - 요청이 처리되는 시간. 어떤 메시지가 두 장치 사이를 왕복하는 데 걸린 시간 매체 타입, 패킷 크기, 라우터의 패킷 처리 시간에 영향을 받음 2.1.2 네트워크 토폴로지와 ..
1. Counter from collections import Counter list = [1, 1, 2, 3, 3, 4] print(Counter(list)) # 출력 Counter({1: 2, 3: 2, 2: 1, 4: 1}) 동일한 자료가 몇 개인지 확인하기 위해 사용되는 함수 문자열, 리스트 등에서 element의 개수를 파악하기 쉬움 Counter의 반환값은 dictionary 형태 most_common(n) 입력된 값의 요소들 중 빈도수(최빈값)을 n개 반환 most_common() # 요소 전체를 반환 most_common(2) # 최빈값 상위 2개 반환 most_common(n) # 최빈값 상위 1개 반환 2. bisect 이진탐색을 쉽게 구현할 수 있는 라이브러리 정렬된 리스트에서 값이 ..
백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는 데 적합 모든 경우의 수를 탐색하는 대신 조건을 걸어서 유망(promising)하지 않은 경우에는 탐색을 중지하고 이전 노드로 돌아가서 다른 경우를 탐색 DFS와의 차이점 DFS: 완전 탐색 백트래킹: 아닐 때 더이상 진행하지 않음 (모든 경우를 탐색하지 않음) def backtracking(): if 정답: 정답 출력 or 저장 return for 모든 자식 노드에 대해: if 정답으로 선택 가능하다면: 자식 노드로 이동 backtracking() 부모노드로 이동 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그..
가중 그래프 가중 그래프(weighted graph): 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프 무게: 거리, 비용, 시간 등 ex) 오른편 철도 그래프에서, 간선의 무게는 양끝점 역간의 여행거리(km)를 표현 최소 신장 트리 신장 부그래프(spanning subgraph) 그래프 G의 모든 정점들을 포함하는 부그래프 신장 트리(spanning tree) (자유) 트리인 신장 부그래프 최소 신장 트리(minimum spanning tree, MST) 가중 그래프의 총 간선 무게가 최소인 신장트리 응용 통신망 교통망 속성 싸이클 속성 분할 속성 최소신장트리 알고리즘의 정확성 검증에 이용 싸이클 속성 싸이클 속성 T를 가중그래프 G의 최소신장트리라 하자 e를 T에 존재하지 않는 G의 간..
방향그래프 방향그래프(digraph): 모든 간선이 방향간선인 그래프 “directed graph”의 준말 응용 일방통행 도로 항공노선 작업스케줄링 방향그래프 속성 모든 간선이 한 방향으로 진행하는 그래프 G = (V, E)에서, 간선 (a, b)는 a에서 b로 가지만 b에서 a로 가지는 않는다 G가 단순하다면(임의의 정점 두 개에서 동일한 방향으로 진행하는 다른 간선이 없을 경우), m ≤ n(n – 1) 진입간선들(in-edges)과 진출간선들(out-edges)을 각각 별도의 인접리스트로 보관한다면, 진입간선들의 집합과 진출간선들의 집합을 각각의 크기에 비례한 시간에 조사 가능 방향 DFS 간선들을 주어진 방향만을 따라 순회하도록 하면, DFS 및 BFS 순회 알고리즘들을 방향그래프에 특화 가능 방..
그래프 순회 순회(traversal): 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차 예시 수도권 전철망의 모든 역(정점)의 위치를 출력 항공사의 모든 항공편(간선)에 대한 노선 정보를 수집 웹 검색엔진의 데이터 수집 부문은 웹의 하이퍼텍스트 문서(정점)와 문서 내 링크(간선)를 검사함으로써 써핑 주요 전략 깊이 우선 탐색 너비 우선 탐색 깊이 우선 탐색 깊이우선탐색(depth-first search, DFS): 그래프를 순회하기 위한 일반적 기법 그래프 G에 대한 DFS 순회로 가능한 것들 G의 모든 정점과 간선을 방문 G가 연결그래프인지 결정 G의 연결요소들을 계산 G의 신장숲을 계산 n개의 정점과 m개의 간선을 가진 그래프에 대한 DFS는 O(n + m) 시간 소요 DFS를 확장하..
해시테이블 키-주소 매핑에 의해 구현된 사전 ADT ex) 컴파일러의 심볼 테이블, 환경변수들의 레지스트리 해시테이블 - 버켓 배열 + 해시함수 항목들의 키를 주소(배열 첨자)로 매핑함으로써 1차원 배열에 사전 항목들을 저장 성능 탐색, 삽입, 삭제: O(n) 최악시간, 그러나 O(1) 기대시간 버켓 배열 해시테이블을 위한 버켓 배열(bucket array)은 크기 M의 배열 A로서 A의 각 셀을 버켓(키-원소 쌍을 담는 그릇)으로 봄 - 슬롯(slot)이라고도 함 정수 M은 배열의 용량을 정의 키 k를 가진 원소 e는 버켓 A[k]에 삽입 사전에 존재하지 않는 키에 속하는 버켓 셀들은 NoSuchKey라는 특별한 개체를 담는 것으로 가정 버켓 배열 분석 키가 유일한 정수며 [0, M-1] 범위에 잘 분..
비교 정렬 알고리즘 비교 정렬의 안정성 키-원소 항목들을 정렬할 때 중요한 이슈: 동일 키가 어떻게 처리되느냐 L = ((k0, e0), ..., (kn-1, en-1))을 항목들의 리스트라 하자 두 개의 항목 (ki, ei)와 (kj, ej)에 대해 ki = kj며 정렬 전에 (ki, ei)가 (kj, ej)보다 앞서 있었다면 (즉, i k) return NoSuchKey else L.advance(i) 3. return NoSuchKey 이진탐색 이진탐색(Binary search): 키로 정렬된 배열에 기초한 리스트로 구현된 사전에 대해 findElement 작업을 수행 재귀할 때마다, 후보 항목들의 수가 절반으로 줄어든다. 입력 크기의 로그 수에 해당하는 수의 재귀를 수행한 후 정지 참고: 스무고개..
분할통치법 (divide-and-conquer) 일반적인 알고리즘 설계 기법의 일종 분할 (divide): 입력 데이터 L을 둘 이상의 분리된 부분집합 L1, L2, ... 으로 나눔 재귀 (recur): L1, L2, ... 각각에 대한 부문제를 재귀적으로 해결 통치 (conquer): 부문제들에 대한 해결을 합쳐 L의 해결을 구함 재귀의 베이스 케이스: 상수 크기의 부문제들 점화식 (recurrence equations)을 사용하여 분석 ex) 합병 정렬 (merge-sort), 퀵 정렬 (quick-sort) 합병 정렬 합병 정렬 (merge-sort): 분할통치법에 기초한 정렬 알고리즘 힙 정렬(heap-sort)처럼 비교에 기초한 정렬 O(nlogn) 시간에 수행 힙 정렬(heap-sort)과는..
