HJW's IT Blog

Semaphore --> 큰 개념 두가지: lock, 통신(동기화) --> 공유 자원을 여러 스레드에서 사용할 때 충돌을 방지하기 위함 --> 여러 스레드가 공유자원을 서로 액세스 할 때 문제 발생 위 코드는 자판기를 producer-consumer 문제로 모델링 한 것이다. --> 자판기에는 emptySlot 이 100개 있다. (콜라를 담을 수 있는 슬롯) --> DeliveryPerson() 은 자판기에 콜라를 넣는다.(emptySlot이 가득 차지 않았을 경우) --> DeliveryPerson() 은 콜라를 하나 넣을때 마다 semaphore를 하나 감소. (emptySlot 감소) --> ThirstyPerson() 은 콜라를 뽑아 마시는 사람. --> ThirstyPerson() 은 자판기가..

TCP Flow Control sender 가 rcv 에게 자신이 수용할 수 있는 데이터 양을 알려주어, sender 특이 데이터를 조절하는 기능 즉, 강제로 송신측의 데이터 전송을 줄이는것 rwnd: Rcv가 sender에게 전송 가능한 윈도우의 크기를 나타내는 변수 rcv가 rwnd를 계산하여 sender에게 알리면 sender는 rwnd 이상의 데이터 전송 x Sender: Last-Byte-Sent - Last-Byte-Acked = "In-Flight Data" Rcv: Last-Byte-Rcvd - Last-Byte-Read = Data in Receiver Buffer RcvBuffer - (Last-Byte-Rcvd - Last-Byte-Read) = rwnd Sender 는 ("In-Fl..

크루스칼 알고리즘이란 최소 신장 트리를 찾는 그래프 알고리즘 중 하나이다. 이때, 그래프는 무방향이다. 최소 신장트리(Minimum Spanning Tree: MST)란 모든 정점을 포함하면서 그래프의 모든 간선의 가중치 합이 최소인 트리를 의미. --> 사이클 없이 모든 노드가 연결되어야 한다. 동작원리 --> 그래프의 모든 간선을 오름차순 정렬 --> 가중치가 가장 작은 간선 선택 --> 이 간선이 최소 신장 트리에 이미 포함되어 있는지 확인 --> 포함되어 있지 않다면 해당 간선을 MST에 추가 풀이 1: --> 각 질의마다 크루스컬 알고리즘을 돌리며 연결 되는 순간 에지의 가중치 값이 질의의 답 c --> 이때 크루스컬 알고리즘에 O(|E|log|V|) 시간, 총 Q의 질의 가 있으므로 O(Q|E..

Binary Search 란 정렬된 배열에서 원하는 값을 빠르게 찾기 위한 알고리즘이다 Binary Search는 반으로 나누어 검색하는 방법으로 시간 복잡도는 O(log n) 이다. 동작과정 1. 배열의 중간값을 선택한다 2. 중간값과 찾고자 하는 값을 비교 --> 중간값이 찾고자 하는 값과 같으면 검색을 종료 --> 찾고자 하는 값이 중간값보다 작으면 배열의 왼쪽으로 다시검색 --> 찾고자 하는 값이 중간값보다 크다면 배열의 오른쪽으로 다시 검색 --> 위 방법 반복 경비실 문제 무식한 방법 M이 가장 왼쪽에 있는 집부터 가장 오른쪽에 있는 집까지의 거리. 모든 (M,k) 에 대해 다 조합해본다: O(M^k) 시간 착안점 --> 경비실이 k개 있다면 집에서 경비실 까지의 거리는 M/(2k) 보다 멀 ..

Segment Tree는 배열과 같은 자료구조에서 주어진 구간의 질의를 빠르게 처리하기 위해 사용되는 자료구조 이다. Segment Tree는 트리구조를 사용하여 구간을 나누어 저장하며 각 노드는 자식노드들의 정보를 이용하여 자신의 정보를 계산한다. 다음은 segment tree 의 예제인데, 노드 내부의 숫자는 어디서부터 어디까지의 합을 나타내는지를 보여준다 Segment Tree 에서 - 리프노드: 배열의 수 그 자체 - 다른 노드: 왼쪽, 오른쪽 자식의 합 Segment Tree로 특정구간 [a,b] 의 합을 구하려면 다음을 점검한다. [a,b] 와 [left, right] 이 겹치지 않는다 do nothing [a,b] 가 [left, right] 을 포함 미리 구해둔 [left, right]의 ..

욕심쟁이 기법은 최적해를 구하는데에 사용되는 알고리즘중 하나로, 매 단계에서 가장 최선의 선택을 하여 최종 결과물이 최적해에 가까워 지도록 하는것이다. 욕심쟁이 기법은 매우 직관적이며 구현하기 쉽지만 최적해를 보장하지는 않는다. 예시) 회의실 배정 문제 한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다. 각 회의 i에 대해 시작시간 Si 와 끝시간 Fi 가 주어진다. 각 회의가 겹치지 않으면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하라. 해법: 가장 빨리 끝나는 회의부터 넣는다. 증명: 회의들이 끝나는 시간에 따라 {1,...,n} 이라고 하자. 정답은 1을 포함하거나 포함하지 않는다. 1을 포함하지 않는다면... 정답의 첫번째 답이 1과 겹치지 않는다면 1을 ..

Brute Force Method 자신보다 뒤에 나오는 수 가 자신과 같다면 카운팅 해가며 찾는방법 O(n^2) O(n log n) 방법 원소들을 정렬한다 (O(n log n) 의 시간) 정렬전: 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 정렬후: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 등장 횟수를 검사하는데에 O(n)의 시간 전체 시간: O(n log n) O(n) 방법: Boyer-Moore 다음과 같이 작동한다: 같은 수라면 skip, 다른 수라면 상쇄 다음 숫자열에 대해 작동 과정을 살펴보자 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 (상쇄) 2 2 1 1 1 1 2 1 3 2 1 1 1 2 (..

트리의 지름이란 트리의 두 정점 u 와 v 를 잇는 거리의 최대값이다. 즉, 트리 내에서 가장 먼 두 정점 사이의 거리를 의미한다. Brute-Force Method 모든 가능한 u, v 의 조합을 다 해본다 이 때 걸리는 시간은 O(n^3) --> 비효율적 O(n) 알고리즘 트리에서 임의의 정점 x를 선택한다 x에서 가장 먼 정점 y를 BFS 를 통해 찾는다 y 에서 가장 먼 정점 z를 찾는다 y 와 z 가 가장 멀리 떨어져 있는 정점이다. 위 방법의 증명은 다음과 같다 원하는 답이 u 와 v 라고 하자. 이때, x를 정한 뒤 가장 먼 점이 y라고 한다면 3가지 가능성이 존재한다 x = u (or v) y = u (or v) x,y,u,v 는 모두 다른 경우 x = u (or v) 나 y = u(or ..

부분합이란? 부분합은 배열의 각원소까지의 누적합을 계산한 배열을 말한다. 부분합 배열의 i 번째 원소는 원래 배열 의 1번째부터 i 번째 원소까지의 합을 나타낸다. Square Root Decomposition(전처리: O(n), 질의: O(sqrt(n)) 이 방법은 배열을 sqrt(n) 개의 블록으로 나누고 각 블록에 대한 누적합을 계산하여 저장한다. 예를 들어 배열 A = [1,2,3,4,5,6,7,8,9,10] 의 배열이 있다. 배열을 sqrt(n), 즉, 3개의 블록으로 나눈다면 다음과 같다 B[0] = A[0] + A[1] + A[2] -> 6 B[1] = A[3] + A[4] + A[5] ->15 B[2] = A[6] + A[7] + A[8] ->24 B[3] = A[9] -> 10 B = [..

RMQ란 배열에서 일부 구간을 선택하여 그 구간에서의 최소값을 찾는 알고리즘이다. RMQ를 해결함에 있어서 여러 방법이 존제하는데 살펴보자. Brute-force Method 이 방법은 가장 단순한 방법으로 해당 구간 내에 모든 원소를 비교하는 방법이다. 각 쿼리가 주어질때마다 해당 구간에서 최소값을 찾기 위해 O(n) 시간이 소요된다 이 방법은 구현이 간단하고 쿼리가 적은 경우에는 유용할 수 있지만 보통은 그렇지 않다 전처리: O(n^2), 질의: O(1) 가능한 a, b 모두에 대해 미리 답을 다른 배열 B[a][b]에 미리 답을 저장해 두는 방법이다. 값이 변하지만 않는다면 유용하지만 그렇지 못할경우 비효율적 전처리: O(n), 질의 O(sqrt(n)) 이 방법은 square root decompo..