programmer life guidance 101

> 네트워크 유량(Network Flow) 안녕하세요. 그래프에 대해서 1차적으로 쓸 내용 중에서는 마지막 개념에 달했습니다. 그런데 마지막 개념이기는 한데, 이 개념 한 부류를 설명하는 데 또 글을 엄청 써야 할 것 같네요. 그만큼 중요한 개념입니다. 최단 경로만큼이나... 아니 어쩌면 더... 최단 경로 알고리즘의 경우는 자료구조 수업 때 먼저 접하는 것도 있고, 최단경로가 무엇인가 하는 개념도 기초적인 편이라서 그렇게 어렵지는 않은데(알고리즘 자체는) 이번에 소개하려 하는 네트워크 유량(network flow)이란 개념은 상대적으로 생소합니다. 그래프의 간선에 거리, 시간이나 가중치, 즉 cost 대신에 용량(capacity)이라는 개념이 추가됩니다. 이제 두 정점 u, v를 잇는 간선 (u, v)..

> 오일러 경로, 오일러 회로 이번에 소개할 내용은 오일러 경로(Eulerian trail) 및 오일러 회로(Eulerian circuit)입니다. 위상수학, 이산구조 시간의 그래프 이론 챕터에서 한 번쯤 보셨을 내용입니다. 무향이나 유향 그래프가 있을 때, 그래프에 존재하는 모든 간선을 정확히 1번씩만 방문하는 연속된 경로가 바로 이것들입니다. 이때 시작점과 도착점이 같으면 오일러 회로가 되고, 아닐 경우 그냥 오일러 경로가 됩니다. 이와 같은 무향 그래프가 있을 때, 경로 [A, B, C, D, A]는 시작점으로 돌아오기는 했으나 모든 간선을 사용하지는 않으므로 오일러 회로가 아니지만(물론, 오일러 경로조차 아닙니다), 경로 [A, B, C, E, F, C, D, A]는 오일러 회로입니다. 모든 간선..

programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. programmers.co.kr 문제설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 자연수 n이 매개변수로 주어질 때, n을 124 ..

programmers.co.kr/learn/courses/30/lessons/12924 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr 문제설명 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다. 1 + 2 + 3 + 4 + 5 = 15 4 + 5 + 6 = 15 7 + 8 = 15 15 = 15 자연수 n이 매개변수로 주어질 ..

programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 �� programmers.co.kr 문제설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열..

IP PBX PBX란? Private Branch Exchange PBX, EPABX는 사설 전화 교환기 인데, 기업용 서비스에 특화가 되어 있는 장비이다. PBX는 기업에 필요한 다양한 기능들을 가지고 있어, 기업에서 전화를 이용해 빠르고 편하게 통신을 할 수 있께 해주는 장비이다. 하지만 예전부터 PBX가 지금의 것처럼 좋았던 것은 아닙니다. 예전에는 전화국의 교환원이 전화코드를 통화를 원하는 사람끼리 연결 해주던 시절이 있었습니다. 전화를 걸고자 하는 사람은 전화기에 달려있는 발전기를 돌려서 신호를 보내면 전화국의 교환원이 받게됩니다. 전화를 받은 교환원은 전화받을 사람을 물어보고 수동으로 연결해 주는 방식이었습니다. 이런 방식은 아직 우리군의 야전용으로 많이 사용되고 있습니다. 하지만 PABX 즉..

PCM Pulse Code Modulation, 펄스 부호 변조 최초로 실용화된 '음성의 디지털 부호화' 및 '다중화 전송' 방식 => 일반적으로, 최초 입력단에 ADC, 최종 출력단에 DAC를 갖는다 PCM 방식 주요 특징 아날로그 음성신호의 디지털화 PCM 방식의 이론적 근거 : 기본적으로 샘플링 이론(Sampling Theroy)에 근거 아날로그에서 디지털로 변환 -> A/D 컨버터 참조 음성 부호화 최초의 국제 표준 음성 부호화 방식(G.711) 구현 시분할다중화(TDM Multiplexing) 다중화 방식 표준 : T1방식(북미 표준) 및 E1방식(유럽 표준) PCM 디지털화 과정 표본화(Sampling) > 양자화(Quantizing) > 부호화(Coding) 음성신호에 대해 초당 8천번을(1..

G.711 64 kbps PCM을 위한 '음성부호화' 표준 => 음성부호화 중 음성파형부호화에 전형적임 G.711은 PSTN망(전화망)에 적용되는 가장 기초적인 방식 => 그냥 PCM(Pulse Code Modulation, 펄스부호변조) 방식이라고도 한다. G.711의 기술적 주요 특징 대역폭 : 300Hz ~ 3400Hz 대역의 음성 대역 신호 표본화 주파수 : 8kHz (125 us) 양자화 비트수 : 각 표본을 8비트로 부호화 양자화 방식 : 비선형 양자화 (Companding 방식) => mu-Law(u-Law) 또는 A-Law 모두 사용 가능 전송 비트율 : 8000 [표본/초] x 8 [비트] = 64kbps 통화품질 : MOS(Mean Opinion Score) 다른 G 코덱과의 비교 코덱..

SIP ver.2 VoIP 또는 멀티미디어 통신용 신호 프로토콜 1 이상의 양방향 멀티미디어 세션/호를 설정, 변경, 해제 세션 네트워크 상에서 양 종단간 일회용 논리적 연결 ex) SVC 가상회선, TCP 세션 등 컴퓨터(멀티 사용자 시스템) 상에서, 하니 사용자가 로그인 후부터 로그아웃할 때 까지의 경과 -> 이 경우 사용 이력 기록을 로그(Log)라고 함 세션 계층(Session Layer) OSI 7계층 모델의 5계층에 해당 종단 호스트 프로세스 간에 세션을 생성, 유지, 종료하는데 필요한 여러 기능을 제공 세션 설정 프로토콜 세션의 설정, 변경, 해제와 관련된 프로토콜 ex) SIP, SDP 등 세션 키(Session Key) 하나의 논리적 연결 세션 동안 만 유효한 암호 키 > 세션계층의 주요..

SIP ver.1 Session Initiation Protocol 멀티미디어 통신에 있어 세션이나 호(Call)을 관리하는 프로토콜 멀티미디어 데이터 전송 자체보다는 Signaling을 통한 멀티미디어 통신 관리에 중점을 두고 있다. 다시 말해, 멀티미디어 데이터 전송은 실시간 전송을 기반으로 하는 RTP가 담당하고 SIP는 어플리케이션 레벨의 프로토콜 다음은 실제 SIP의 프로토콜 스택이다. SIP (RFC 3261) : SIP 기본 내용 정의 SDP (Session Description Protocol, RFC 4566/3264) : 멀티미디어 세션 파라미터 설정 Audio Codec (G.711A, G.723.1, G.729A) : 음성 코딩 담당, 다양한 시스템과 호환을 위해 여러 규격 존재 V..

VoIP Voice over Internet Protocol IP네트워크를 활용하여 음성을 데이터 패킷으로 변환해서 통화를 가능하게 하는 통신 서비스 기술 VoIP는 IP를 사용하여 음성전보를 전달하는 일련의 설비들을 위한 IP 전화기술을 지칭하는 용어이다. 일반적으로, 이것은 공중교환전화망인 PSTN 처럼 회선에 근거한 전통적인 프로토콜들이 아니라, 불연속적인 패킷들 내에 디지털 형태로 음성정보를 보낸다는 것을 의미한다. VoIP와 인터넷 전화기술의 주요장점은 기존 IP네트웍을 그대로 활용해 전화서비스를 통합 구현함으로써 전화 사용자들이 시내전화 요금만으로 인터넷, 인트라넷 환경에서 시외 및 국제전화 서비스를 받을 수 있게 된다는 점이다. VoIP는 공중 인터넷 또는 기업 내부의 인트라넷 상에서 IP를..

> 세그먼트 트리(Segment Tree) 각 구간들을 그대로 보존하고 있는 트리 전체 구간이 [0, N-1]이라 할 때, 즉 N개의 공간이 있을 때 이렇게 리프 노드들은 길이가 1인 각각의 구간을 갖고 있고 부모 노드는 자신의 자식들의 구간의 합을 갖고 있으며 모든 구간은 연속적이어야만 합니다. 루트는 전체 구간을 포함하게 됩니다. 이렇게 각 노드가 구간, 혹은 그 구간의 정보를 저장하고 있는 자료구조를 말합니다. 보통은 완전 이진 트리의 형태를 사용해 전체적으로 동일한 재귀적 구조가 반복되도록 이렇게 표현하며, 값의 개수가 2^n 꼴이 아닐 때 남는 구간을 의미없는, 혹은 기본 값으로 채워서 포화 이진 트리 형태로 사용하는 게 대부분입니다. 이렇게 하면 값이 N개일 때 반드시 트리의 높이가 O(log..

> 분할 정복(Divide and Conquer) 알고리즘 이번에 소개해 드릴 것은 역시 유명한 기법인 분할 정복(Divide and Conquer)입니다. 탐색, DP, 그리디 등에 비해서는 등장빈도가 좀 낮지만, 이 기법의 성질 자체가 직접 문제푸는데 뿐 아니라 다른 여러 효율적인 자료구조나 알고리즘에 기여할 때가 많습니다. 분할 정복은 말 그대로 문제를 두 단계, ①분할과 ②정복으로 나눠서 해결하는 것을 말합니다. 분할하는 단계에서는 말 그대로 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아지면 작아질수록 풀기 쉬워지는 성질을 이용한 겁니다. 또한 문제의 크기가 엄청나게 줄어든다면(N=1 또는 N=2 정도) 그야말로 바로 답을 구할 수 있는 수준이 되고, 이게 재귀호출로 문제를 풀 때..

> 플로이드 와샬 알고리즘 Floyd-Warshall algorithm 앞의 두 최단거리 알고리즘과는 다르게 정점 V개가 있고 거리가 다 주어져 있을 때, 단 한번의 시행으로 모든 정점 쌍 사이의 거리를 다 구해낸다. 코드는 굉장히 짧은데, 아주 전형적인 3중 for문의 형태를 하고 있고 O(V^3)입니다. 음의 가중치가 있는 간선 그래프에서도 제대로 동작합니다. -BOJ[11404] : 플로이드 이 문제를 풀 겁니다. 아니 제목부터 대놓고 플로이드입니다. 그러므로 플로이드를 씁시다. 각 정점 u, v 쌍에 대해 u에서 v로 가는 최단 경로를 한 번에 다 구할 것이고, 이를 위해 먼저 2차원 배열 dist를 준비합니다. 초기에는 자기 자신으로 가는 dist[i][i] 꼴은 다 0이고, 나머지는 ∞으로 설..

> 벨만포드 알고리즘 이어서 소개해드릴 것은 또다른 최단경로 알고리즘입니다. 벨만 포드 알고리즘(Bellman-Ford algorithm)인데요, 알고리즘을 개발한 두 학자의 성을 따서 붙인 이름이라고 합니다. 동시에 독자적으로 알고리즘을 개발했던 또다른 학자의 이름까지 붙여서 벨만 포드 무어 알고리즘이라 명명할 때도 있다는군요. 다익스트라 알고리즘과 마찬가지로 시작점을 정해 주면 다른 모든 정점으로의 최단 경로를 구하는데, 다익스트라 알고리즘보다는 시간이 오래 걸려서 O(VE)의 시간이 걸리지만 이 알고리즘은 간선 cost가 음수일 때도 사용할 수가 있습니다!! 아니 도대체 거리가 음수라니 무슨 소리냐, 뭐 그런 거 다 떼어놓고 그냥 최단거리가 정말 작으면 작을수록 좋다고 친다면, 설령 그게 음수가 되..