SSH는 시큐어 셸(Secure Shell)의 약자이며 네트워크 상의 다른 컴퓨터에 로그인 하거나 원격 시스템에서 명령을 실행할 수 있도록 하는 프로토콜입니다. (기본 적으로 22번 port를 사용) 간단히 말하면 안전한 원격 통신을 위해서 쓰여지는 통신 방식이라고 할 수 있습니다. 이전에는 Telnet이라는 통신 방식이 사용되었는 데 이 같은 통신 방식은 네트워크 상의 누군가 통신을 가로챈다면 그 통신 내용을 모두 볼 수 있는 단점이 있었습니다. 이러한 단점을 보완하기 위해 SSH가 나왔습니다. 이 SSH를 사용하면 누군가 통신을 가로챈다고 하여도 그 데이터는 암호화된 텍스트로 보이기 때문에 스누핑(남몰래 전송 데이터를 훔치는 방법)에 안전하다고 할 수 있죠. 여담으로 이 SSH는 필란드 Tatu Yl..

추상화(abstraction)란 보통 컴퓨터 과학에서는 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 그 기능을 간추려 내는 것을 말합니다. 추상화로 유명한 피카소의 그림을 보면 어떤 사물의 중요한 부분을 특징만 간추려서 나타내는 것을 볼 수 있습니다. 아래 그림과 같은 소가 대표적인데 세부적인 소의 그림보다 소의 뿔, 다리, 꼬리만을 남겨 소의 특징을 확실하게 나타내고 있죠. [파블로 피카소의 소] 이와 마찬가지로 IT에서의 추상화도 비슷한 개념으로 이해하시면 됩니다. 위에서 언급했듯이 중요한 기능, 핵심적인 개념만을 간추려서 노출시키는 것으로 이해하면 될 것입니다. 또한 이 추상화된 정도를 추상화 수준이라고 부릅니다. 예를 들어 운영체제에서는 물리적인 하드웨어의 복잡성을 추상화하여 개발자..

Minimum Spanning Tree(MST) 문제는 그래프에서 모든 정점을 연결해주는 최소 간선의 집합 중 가중치의 합이 가장 작은 간선의 집합을 찾는 문제입니다. MST를 구하는 방법은 크게 2가지가 있습니다. Prim algorithm과 Kruskal algorithm이죠. Prim과 Kruskal의 기본적인 아이디어는 다음과 같습니다. Prim algorithm은 각 정점을 방문하며 그 정점에 연결된 가장 가중치가 작은 간선들을 선택하여 MST를 구합니다. Kruskal algorithm은 각 간선들을 탐색하여 가장 가중치가 작은 간선들을 택하면서 MST를 구합니다. 지금부터, 아래와 같은 그래프를 가지고 Prim algorithm과 Kruskal algorithm의 동작과정을 알아보고 각 알고..

Floyd-Warshall(플로이드-워샬 알고리즘)은 그래프에서 모든 정점 사이의 최단거리를 구하는 알고리즘입니다. 시간 복잡도는 O(V^3)을 가지죠. 이 알고리즘은 음의 사이클이 없는 그래프에 대해서 모든 정점 사이의 최단거리를 구하는 것이 가능합니다. 그래프의 간선 중 음의 가중치가 존재해도 잘 실행되죠. 모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 됩니다. 이 2차원 배열을 이용하여 플로이드-워셜 알고리즘은 동적계획법으로 최적의 값을 계산합니다. 이 알고리즘의 기본 컨셉은 정점 i, j사이 모든 경유지를 탐색해서 그 중 최단 경로를 찾아내는 것입니다. 그래프의 정점이 1~V까지이면, 경유지 K는 이 모든 정점들을 경유지로 하는 경로를 탐색합니다. dp[i][j] = ..

Bellman-Ford(벨만포드) 알고리즘은 음수 가중치가 있는 그래프에서 특정 시작점 Vs에서 다른 나머지 정점(Vi, i=1, N)까지의 최단거리를 구할 수 있는 알고리즘입니다. 이 벨만포드 알고리즘을 그래프의 음수 사이클의 존재 여부도 알 수 있죠. 1. 음수 가중치가 있는 그래프에서 시작점에서 다른 정점까지의 최단거리를 구할 수 있다. 2. 음수 사이클 존재 여부를 알 수 있다. Bellman-Ford 알고리즘의 동작과정은 각 정점들을 차례로 돌아 가면서 해당 정점의 간선들을 탐색합니다, 단 맨 처음은 시작점부터 탐색합니다. 그리고 그 간선의 가중치와 시작점에서 정점까지의 거리의 합이 해당 간선이 도달하고자 하는 정점의 기존 거리보다 작으면 업데이트합니다. 식으로 나타내면 다음과 같습니다. d[T]

LCS(Longest Common Subsequence)는 문자열 A,B가 있을 시, 가장 길이가 긴 공통 부분 문자열을 찾는 알고리즘입니다. 여기서 부분 문자열이라는 것은 연속된 문자열이 아닌 부분 문자열을 뜻합니다. 예로들어, 'HAYOUNG'과 'AONG'이라는 문자열이 있을 시, 공통된 부분문자열은, {A}, {A,O}, {A,N}, {A,G}, .. ,{A,O.N,G} 가 있죠. 그리고 여기서 가장 긴 부분 문자열은 'AONG'입니다. LCS를 푸는 알고리즘은 Dynamic Programming을 이용하며 O(mn), (m = len(A), n = len(B)) 의 시간복잡도를 가지고 해결할 수 있습니다. 푸는 절차는 다음과 같습니다. 먼저, Dynamic Programming을 적용하기 위해 ..

알고리즘에서의 네트워크 유량(Network Flow) 문제는 그래프에서 각 노드들 간의 용량(Capacity)이 정의되어 있을 시, 시작점(source)에서 끝점(target)까지 흐를 수 있는 최대 유량을 구하는 문제입니다. 이 네트워크 유량 문제를 해결하는 일반적으로 많이 쓰이는 방안으로는 크게 두 가지가 있습니다. 첫 번째는 DFS로 구현하는 포드 폴커슨 알고리즘(Ford-Fulkerson Algorithm), 두 번재는 BFS로 구현하는 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm)이 있습니다. 여기서는 에드몬드 카프 알고리즘으로 네트워크 유량 문제를 푸는 방식과 구현 코드를 설명하도록 하겠습니다. 위와 같이 용량에 대한 정보가 명시된 그래프에서, 1(source)에서 7(si..

소수란 1과 자기 자신만으로 나눠 떨어지는 수를 말합니다. 그리고 그 소수를 구하는 가장 간단한 방식은 에라토스테네스의 체라는 알고리즘을 이용하는 것입니다. 알고리즘은 다음과 같습니다. 1. 0,1은 소수가 아님 2. 2는 소수임, 그리고 2의 배수가 되는 수들 (2,4,6,8,10,12 ...) 목록에서 제외 3. 3은 소수임, 그리고 3의 배수가 되는 수들 (9,15,21....) 목록에서 제외 *(6, 12, 18 ... 등은 이미 제외) 4. 4는 이미 제외됨 ... 다음은 이 알고리즘을 구현한 코드입니다. 각 숫자를 표현하는 데 있어서 비트마스크를 이용한 것과 2가지 최적화 방법이 적용되 있는 걸 눈여겨 보세요. 첫 번째 최적화는 어떤 N이 소수인지 판별하는 데 있어서 N까지의 모든 수를 따지는..

비트마스크는 정수의 이진수 표현을 자료 구조로 쓰는 기법입니다. 비트마스크를 사용하는 코드는 다음과 같은 장점이 있죠. 1. 더 빠른 수행 시간 : 보통 O(1)에 실행됨 2. 더 간결한 코드 : 복잡한 코드를 한 줄에 작성 가능 3. 더 적은 메모리 사용량 : 예시로, 32개의 아이템의 유무를 나타내는 배열을 32bit 자료형으로 대체 가능 4. 연관 배열을 배열로 대체 : c++ 경우, map를 사용한다고 하면 이를 단순 int[] 배열로 대체 가능 만일 비트마스크로 코드를 작성 시, c++이나 java같은 자료형의 데이터 범위가 정해져 있는 언어에서는 오버플로우나 언더플로우에 주의해야합니다. bool is_bit_set(unsigned long long a, int b){ return ( a & (..

본 포스팅을 읽기 전에 IP 관련 포스팅을 읽으시는 걸 추천드립니다. [기타 정보/Network] - IP, IP 주소, 클래스 분류 확실하게 짚고 넘어가자 | IP 클래스의 비효율성 IPv4는 초기에 클래스로 나누어서 할당을 방법을 택했습니다. 하지만 이 방식은 크게 비효율적이었습니다. 예로들어 클래스 B를 어느 중소기업체에게 할당했을 경우 65000여개의 아이피를 다 쓰는 것이 아닌 10000개 정도만 쓴다고 가정합시다. 그러나 10000개가 아닌 나머지 50000여개의 IP는 쓰이지 않은 채 이 기업체는 클래스 B의 하나를 점유하고 있는 상태가 되죠. 그렇다고 이 기업체에게 클래스 C를 IP를 할당하자니 IP자원이 너무 부족하게 되구요. 이러한 문제를 해결하기 위해 IP를 사용하는 네트워크 장치 수..