suyeonme

이분매칭(Bipartite Matching)이란? 이분 그래프(Bipartite Graph)에서 그래프의 최대 유량을 구하는 알고리즘으로 최대 매칭 수를 구할 수 있다. 최대 매칭수란, 어떤 정점이 다른 정점을 점유한 상태이며 각 정점은 한 개씩 점유가 가능한 경우를 말한다. 따라서 간선의 용량이 1인 경우에 해당한다. 즉 간선의 용량(capacity)이 1인 네트워크 플로우 문제이며, DFS(Depth-first-search)로 구현할 수 있다. 시간복잡도는 [] 으로, 에드몬드카프 알고리즘보다 효율적이다. 이분 그래프(Bipartite Graph)란? 두개의 정점 그룹이 존재하고 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프이다. 아래 이미지를 보면, U와 V 두개의 정점 그룹이..

네트워크 플로우(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를 띄워야하므로 시작 및 종..

나는 왜 개발자가 되기로 결심했을까? 오늘은 그 이유에 대해서 서술해보려고 한다. (기존에 운영하던 블로그에서 내용을 가져왔습니다.) Who am I? 나는 현재 만 24세 강수연이라고 한다. 현재의 나를 설명하기 위해서, 나의 이야기는 고등학교 시절로 거슬러 올라간다. 재미있는 고등학교 생활을 실껏 만끽하다가 3학년이 되어서 갑작스럽게 대학교에 가야겠다고 생각했다. 큰 이유는 없었다. 친구들이 모두 대학교에 가기 위해서 준비하고 있었고 막연하게 "대학 생활이 재밌을 수도 있겠다" 는 생각이 들었기 때문이다. 결국 뒤늦게 공부를 시작해 수능을 보고 서울여자 대학교에 들어가게 된다. 부푼마음을 가지고 대학교에 입학했지만 나의 예상과 달리 대학 생활은 재미가 없었다. 돌이켜 생각해보면, 처음으로 나의 인생의..

강한 연결 요소(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인 정점을 큐에 삽입한다. 큐에서 노..