HJW's IT Blog

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..

GCD(Greates Common Divisor) 알고리즘 이란? GCD는 두개 이상의 정수의 최대공약수를 찾는데 사용되는 알고리즘이다. 원리 두 정수 a 와 b가 있다. a를 b로 나눈 나머지를 구한다 (n = a%b) if (n == 0): GCD = b else: a = b, b = n 반복한다. ex) a = 20, b = 30 20%30 = 20, n = 20 a = 30, b = 20 30%20 = 10, n = 10 a = 20, b = 10 20%10 = 0, n = 0 GCD = 10 유한체(Finite Field) 유한체란 유한한 개수의 원소를 갖는 필드이다. 유한체는 더하기, 빼기, 곱하기, 나누기와 같은 연산이 가능하다 유한체는 유한한 개수의 원소를 갖는다. ex) 2진수는 (0,1..

Synchronization Terminology Synchronization(동기화): Use Atomic Operation, 실행순서를 세세하게 조정하여 두 스레드가 상호작용함에 있어서 공유자원에 대한 접근을 조절, 데이터의 일관성을 보장 Mutual Exclusion(상호배제): Only one thread at a time, 동시에 공유자원에 접근하는것을 막기 위한 기법, 한번에 하나의 스레드만 공유자원에 접근하는것을 허용 Critical Section(임계영역): Part of code that modifies shared data, 공유자원에 접근하는 코드의 영역으로 한번에 한 스레드만 실행 Lock(락): Prevent other thread from doing something, 상호배제를..

프로세스란 OS 로 부터 자원을 할당받아 실행되는 독립적인 실행단위이다. 각각의 프로세스는 독립적인 메모리 영역을 가지며, 프로세스 간에는 메모리를 공유하지 않는다. 스레드는 프로세스 내에서 실행되는 실행단위이다. 각각의 스레드는 프로세스 내의 메모리를 공유한다. 즉, 프로세스는 독립적인 실행 단위, 스레드는 하나의 프로세스 내에서 실행되는 단위 이다. 프로세스는 다음으로 구성된다. Address Space Program Code Global variable, heap, stack OS resources 쓰레드는 다음을 공유한다. Address Space, Program Code Global variables, heap OS resources 각각의 쓰레드는 다음을 가지고 있다 Register, Prog..