우리가 흔히 말하는 서버와 클라이언트. 그 둘의 모델에 대해 알아보고, 소켓통신에 대해서도 알아보자. 클라이언트와 서버는 간단하게 말하면 서비스를 요청하는 쪽과 서비스를 제공하는 쪽을 의미한다. 통신은 항상 클라이언트의 요청과 서버의 응답으로 구성된다. 클라이언트 서비스의 요청자를 의미한다. 서버와 통신하는 모든 프로그램이 될 수 있으며, 서버에 요청을 보내 응답을 받는다. 서비스를 사용하는 사용자, 기계 혹은 프로그램이 클라이언트가 될 수 있다. 서버 서비스를 제공하는 컴퓨터. 큰 용량과 성능을 가지고 있으며 클라이언트와 API 통신을 한다. 요즘 대용량 서비스는 microservice 를 활용해 서버를 띄우는 경우가 많다. (ex 도커, 쿠버네티스) 이와같은 배포는 서비스의 수정, 확장성을 용이하게 ..

이번 포스팅에서는 Cut Vertex란 무엇인지 그에 대한 정의와, 판별하는 방법에 대해 알아보겠습니다. 그에 더불어 dfs graph, back edge 에 대한 개념도 살펴봅시다. Definition of Cut Vertex If node s is Cut Vertex, Removing a node s makes Graph G Disconnected. Exists x and y s.t., all paths from x to y goes through s. Cut vertex 정의 1. 연결 그래프 G에서 노드 S를 없앴더니 비연결 그래프가 되었을때, S를 Cut vertex(단절점)라 부른다. 없앴을 때 Disconnected Graph 를 만드는 S를 Cut Vertex 라고 부른다. 2. 노드 X에..

이번 포스팅에서는 Graph traversal(그래프 순회)와, Connected Component 대해 알아보자. Graph Traversal 그래프 순회 정의 모든 Node, Edge를 한번씩 지정된 순서로 방문하는 것이다. 순회를 거친 후에, 그래프에서 뽑아낸 자료구조가 만들어진다. (ex. 트리구조) 트리에서 문제를 푸는 것이 그래프에서 푸는 것보다 쉽다. 그래프 순회의 종류 - Depth First Search (깊이 우선 탐색) - Breadth First Search (너비 우선 탐색) Any-order Traversal Start at a Node S (put S into BOX) While BOX is not Empty Take one Node from BOX If Node not Mar..

우선 approxmiate median 에 대해 알아보기 전에, Quick Sort에 대해 간단히 짚어보자. Quick Sort 저번 포스팅에서 Quick Sort의 평균 시간복잡도가 왜 O(nlogn) 인지 증명해보았다. 시간복잡도 Average : O(nlogn) Worst : O(n^2) 피벗이 중간에 위치해 있다 -> Best Case 피벗이 한쪽 방향으로 계속 쏠려있다. -> Worst Case 정말 운이 안 좋게도 재귀적으로 따라 들어갈 때마다 pivot 이 한쪽 끝이라면 시간복잡도가 O(n^2) 이다. Quick Sort를 쓰는 의미가 없음. 시간복잡도 (최악의 경우) T(n) = n + T(n-1) T(n) = O(n^2) 이렇게 pivot의 위치에 따라 성능에 크나큰 차이가 발생한다. 따..

MergeSort 알고리즘의 시간 복잡도는 O(NlogN) 이다. MergeSort는 매우 준수한 정렬 알고리즘이지만 추가적인 배열 하나가 더 필요하기 때문에 memory allocation이 일어난다. 그리고 새로운 메모리를 할당하는 과정은 꽤 비싸다. 이번 포스팅에서는 퀵정렬에 대해 알아보고, 시간복잡도에 대한 증명도 하고자 한다. Quick Sort 대표적인 divide & conquer 알고리즘. 평균 시간복잡도: O(NlogN) 인 아주 훌륭한 알고리즘이다. 퀵 정렬은 조금 특이한 특징을 가지고 있는데, 바로 피벗(Pivot)을 사용한다는 점이다. 대략적인 소스코드는 다음과 같다. int qsort(int a[], int n){ // pivot int p = a[0]; int i = 1; int..

앞서 최단거리 알고리즘으로 Prim, Kruskal 을 다뤄보았다. 이번 포스팅에서 다룰 Shortest Path 알고리즘은 다익스트라(dijkstra)이다. 다익스트라 알고리즘이 왜 정확한지 정확성 증명을 해보고, 코드로 구현을 해보겠다. Dijkstra Algorithm 정확성 증명 Source 노드에서 시작 각 노드에 적힌 숫자는 source 노드와의 최단거리를 나타낸다. 정답을 찾아가면서 이 노드들의 숫자를 update 하면 된다. 다익스트라의 특징 모든 노드에서 시작점까지의 최단 거리를 구할 수 있다. 단순히 거리만 구하는 것이 아니라, 지나온 경로도 알 수 있다. (백 트래킹) 진행 방법 위처럼 노드들이 있고, 노드마다 적힌 숫자는 시작 노드와의 최단거리를 나타낸다. 빨간 영역은 알고리즘에 의..