Segment Tree 배열 A[1], ..., A[N]이 있을 때, 아래 문제를 생각해보자. [문제 1] 순서쌍 (i, j)에 대하여 A[i], ... ,A[j] 중 최솟값을 찾는 경우를 생각해보자. A[i]부터 A[j]까지 순회하면서 찾는 것이 가장 단순한 방법일 것이다. 이 경우 시간 복잡도는 O(N)이 된다. 그러나 이러한 연산이 Q개 주어지고 N과 Q의 범위가 1부터 10만이라면, 시간 복잡도가 O(NQ)이므로 오랜 시간이 걸릴 것이다. [문제 2] 구간 [l, r] (l ≤ r)이 주어진다. (1) A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력한 뒤, (2) i번째 수를 v로 바꾼다. 이 과정을 M번 반복한다. (1)번 과정은 O(N), (2)번 과정은 O(1)..

CPU Scheduling CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업 - 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것 프로세스들에게 자원을 최대한 공평하게 배분하며 처리율과 CPU 이용률을 증가시키고, 오버헤드, 응답시간(Response time / Turnaround time), 대기시간을 최소화하기 위한 기법 선점형 스케줄링(Preemptive Scheduling) 과 비선점형 스케줄링(Non-preemptive / Cooperative Scheduling) 이 있음 메모리에 여러 개의 프로세스를 올려놓고(다중 프로그래밍), CPU의 가동시간을 적절히 나누어(시분할) 각각의 프로세스에게 분배하여 실행 [참고] 스케줄러의 종류와 특징 종류 특징 장기 스케줄러 (L..

Deadlock '교착 상태'라고도 하며, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생 데드락이 발생할 수 있는 경우: Process 1과 Process2가 Resource 1, 2를 둘 다 얻어야 한다고 가정할 때, 서로 원하는 Resource가 상대 Process에게 할당되어 있기 때문에 두 프로세스가 무한정 기다리게 된다. 교착 상태의 조건 한 시스템 내에서 다음의 네 가지 조건이 동시에 성립할 때 발생 따라서, 아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 교착 상태 해결 가능 조건 설명 상호 배제 (Mutual exclusion) - 자원은 한 번에..

Union-find? 그래프 알고리즘의 일종으로써, 상호 배타적 집합(Disjoint Set)이라고도 한다. 여러 노드가 존재할 때, 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 아래의 2가지 연산으로 이루어져 있다. Find: 노드 x가 어떤 집합에 포함되어 있는지 찾는 연산 Union: 노드 x와 노드 y가 포함되어 있는 집합을 합치는 연산 Union-find는 크루스칼 알고리즘에서 원소 간의 연결 여부를 판단하는 데에 사용한다. 구현 구현은 트리를 이용하며, parent[i]를 노드 i의 부모 노드라고 정의하고 초기화를 해준다. 이 때, parent[i] = i일 경우, 루트 노드임을 의미한다. int parent[MAX_SIZE];..

안녕하세요, SSAFYcial 3기 곽은정입니다. 지난 6월 19일, 저는 SSAFY 3기 1학기를 무사히 수료했는데요! 이미 2학기가 시작했지만 짤막하게나마 1학기 회고를 남겨보려고 합니다. ㅎㅎ SSAFY를 시작한 1월부터 1학기가 끝난 6월까지, 가장 큰 사건이나 기억에 남는 순간들을 하나씩만 골라봤어요. # 1월. 입학식 엄청 두근두근했던 입학식! 새로운 환경에서 새로운 공부를 할 생각에 많이 들떠있었어요. 이 때 만난 친구들과는 모두 다 다른 반이 되어도 자주 마주치고 또 일부는 취업도 했지만 가끔 연락도 하는, SSAFY에서 이어진 소중한 인연들이에요 :) #2월. 코로나19로 인한 휴강 2월 말, 대구경북 지역에서 코로나19로 인한 첫 사망자가 발생함과 동시에 SSAFY 측에서는 발빠른 대처..

안녕하세요, SSAFYcial 3기 곽은정입니다. SSAFY에는 총 두 가지의 트랙이 있다는 거, 알고 계시나요? 바로 Web 트랙과 Embedded 트랙인데요- 웹은 많이 익숙하지만 임베디드는 생소하신 분들이 많을 것 같아요. 임베디드 반에 대해 소개를 하기 전에 임베디드 시스템에 대한 정의를 하자면, 임베디드 시스템이란, 기계나 기타 제어가 필요한 시스템에 대해, 제어를 위한 특정 기능을 수행하는 컴퓨터 시스템으로 장치 내에 존재하는 전자 시스템 이라고 하네요. (출처: 위키백과) 이런 점에서 임베디드란, 특정 기능 수행을 위해 칩에 프로그래밍을 하는 것- 정도라고 정의할 수 있을 것 같습니다. 대표적으로 라즈베리파이나 아두이노 등을 통해 경험할 수 있어요. 임베디드에 대한 개념이 조금, 이해가 되셨..