suyeonme

네트워크 플로우(Network-Flow) 알고리즘이란? A지점에서 B지점으로 데이터가 얼만큼 많이 흐르고 있는지를 측정하는 알고리즘으로 , 최대 유량 문제(Maximum flow problem)를 해결하는데 사용된다. 최대 유량 문제란, 네트워크상에서 얼마나 많은 양의 데이터를 보낼 수 있는지,즉 최대 유량(Max Flow)을 찾는 문제이다. 최대 유량 알고리즘은 유량을 보내는 순서가 상관이 없다. 용어 유량(flow): 현재 흐르는 데이터의 양 용량(capacity): 간선에 흐를 수 있는 최대 데이터의 양 일반적으로 BFS(Breadth-first search)를 이용하며, 에드몬드 카프(Edmonds-Karp) 알고리즘이라고도 한다. 시간복잡도는 O(VE^2)이다. 도로의 교통 흐름, 전자 회로의 ..

VM(Virtual Machine) VM은 하이퍼바이저(hypervisor)로 컴퓨터 환경을 가상화(emulation)하는 방법이다. 하이퍼바이저를 이용하여 HostOS위에 특정 운영체제(가상 이미지)로 GuestOS를 올려 여러개의 VM을 생성할 수 있다. 하드웨어 스택을 가상화한다. 예를 들면, HostOS가 window이고 그 위에 GuestOS로 Linux를 설치할 수 있다. GuestOS 입장에서는 물리 서버와 동일하게 사용이 가능하다. 하이퍼바이저의 종류로 virtual box, Xen, KVM, VMware등이 있다. 장점 각각의 VM간 완전한 격리로 보안성이 높다. GuestOS로 다양한 OS를 사용할 수 있다. 단점 크기가 GB단위로 사이즈가 크다. 각각의 OS를 띄워야하므로 시작 및 종..

강한 연결 요소(Strongly Connected Component, SCC)란? 그래프안에서 강하게 결합된 정점 집합을 의미한다. 강한 결합 요소의 특징 같은 집합에 속하는 두 정점은 서로 도달이 가능하다. 사이클이 발생하는 경우 무조건 SCC에 해당한다. 따라서 방향그래프일 때 의미가 있다. 타잔 알고리즘(Tarjan's Algorithm)이란? 타잔 알고리즘(Tarjan's stronly connected components algorithm)은 SCC를 추출하는 대표적인 알고리즘으로 모든 정점에 대해 DFS를 수행하여 SCC를 탐색한다. 이 때 부모 노드로 돌아올 수 있는 경로에 한해서 SCC가 성립된다. SCC 그룹을 정점으로하여 전체 그래프를 구성한 경우, 사이클이 발생하지 않는 방향 그래프..

구글 엔지니어는 이렇게 일한다 책의 21장 "의존성 관리" 챕터를 읽고 정리한 내용입니다. Semantic Versioning(SemVer)이란? Semantic Versioning은 오늘날 의존성 네트워크를 관리하는 가장 대표적인 방법으로, 의존성의 버전을 표기하는 보편적 방식이다. 버전은 숫자 세개로 표현한다. 예를 들어, library ≥ 1.5는 1.5나 1.5.1 혹은 1.6이상을 포괄한다는 의미이다. MAJOR: API가 변경되어 의존성을 이용하던 기존 코드를 깨뜨릴 수 있음 MINOR: 순수한 기능추가만 있음(기존 코드를 깨뜨리지 않음) PATCH: API에 영향을 주지 않는 내부 구현 개선과 버그 수정 Semantic Versioning(SemVer)의 한계 변경이 얼마나 위험할지를 사람이..

로그를 남기는 이유 운영환경에서 어플리케이션에서 문제가 발생한 경우 원인 파악을 하기 위해서는 문제가 발생했을 당시의 정보가 필요하다. 따라서 Exception이 발생했거나, 중요 기능이 실행되는 부분에서는 로그를 남긴다. 로그는 재현하기 힘든 버그에 대한 정보를 제공한다. 로그는 성능에 관한 통계와 정보를 제공한다. 로그 사용시 장점 쓰레드 정보, 클래스 이름등 부가 정보를 출력할 수 있고 출력 포맷을 조정할 수 있다. 로그 레벨에 따라 개발 서버에서는 모든 로그를 출력, 운영 서버에서는 특정 레벨 이상의 로그만 출력하는등의 조절을 할 수 있다. 시스템 아웃 콘솔에 출력 및 파일이나 네트워크등 별도의 위치에 로그를 남길 수 있다.(파일 분할, 파일 압축등) 내부 버퍼링, 멀티스레드등 측면에서 성능이 S..

위상 정렬(Topology Sort)이란? 순서가 존재하는 작업을 수행할 때, 순서를 결정하기 위해 사용하는 알고리즘이다. 위상 정렬은 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)에만 적용할 수 있으며 여러개의 결과가 존재할 수 있다. 방향성이 있지만 사이클이 없어야 진입차수가 존재할 수 있다. 진입차수(in-degree), 진출 차수(out-degree)란? 진입차수(in-degree): A노드를 향하는(A노드로 들어오는) 간선의 개수 진출 차수(out-degree): A노드에서 외부로 향하는(나가는) 간선의 개수 노드 2의 경우, 진입차수는 2, 진출차수는 0이다. 구현 방법 Stack Queue 구현 순서 진입차수가 0인 정점을 큐에 삽입한다. 큐에서 노..

플로이드 와샬 알고리즘(Floyd Warshall Algorithm)이란? 음수 사이클이 없는 그래프에서 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘으로, 거쳐가는(경유) 정점을 기준으로 거쳐가는 경로가 기존의 경로보다 더 효율적인지 판단하여 최단 거리를 구한다. 정점의 개수만큼 3중 반복문을 수행하기때문에 O(V^3)만큼의 시간 복잡도를 갖는다. 동적 프로그래밍 기법을 사용한다. 음수 사이클이 존재하지 않으면 음의 가중치를 가질 수 있다. (≠ 다익스트라 알고리즘) 음수 사이클 사이클의 모든 경로의 합이 음수가 되는 사이클이다. 1 --> 2 --> 3 --> 1의 경우, (1 -3 -2) = -4 이므로 음수 사이클이 존재한다. 구현 순서 인접 행렬을 생성하고 간선의 정보를 저장한다..

우선순위 큐(Priority Queue)란? 큐의 구조를 따르지만(FIFO, First In First Out) 우선 순위를 결정하고 높은 우선순위를 가진 요소를 먼저 꺼내서 처리하는 자료구조이다. 우선순위큐는 내부적으로 힙(Heap)으로 구성되어 이진트리의 구조로 이루어져있다. 따라서 O(N log N)의 시간복잡도를 가진다. Heap이란? Heap은 완전 이진트리로 구현되었으며 우선순위 큐를 위한 자료구조이다. 부모 노드의 값은 자식 노드의 값보다 크거나(Max Heap) 작아야(Min Heap)한다. 이러한 구조를 이용하여 최댓값과 최솟값을 빠르게 찾아낼 수 있다. 힙은 배열로 구현된다. 편의상 0번 인덱스는 사용하지 않는다. 왼쪽, 오른쪽 노드의 위치가 대소 관계를 반영하지 않는다. 즉 왼쪽 노..