[ Basic ](30)
-
<추천>[OS] Context Switching, Cache Pollution / TLB, MMU
PCB(Process Control Block) 운영체제가 프로세스들을 관리하기 위해 사용하는 자료구조이다. 운영체제는 PCB 자료구조를 통해 프로세스 제어 및 관리(스케줄링, 종료, fork 등)를 한다. 아래 사진은 PCB가 갖는 데이터 구조이다. - process state : 프로세스의 상태(new ready waiting, running, terminated) - process number : PID - program counter : PC 레지스터 값(다음에 실행시킬 Instruction의 주소) - registers : 프로세스가 스케줄링되어 있던 CPU의 레지스터의 값(Context Switching시 사용됨) - memory-limits : 프로세스에 할당된 메모리 제한 정보(페이지 테이..
2022.05.28 -
<추천티비>OSI 7계층을 기반으로 네트워크 흐름 이해하기
이번 포스팅의 목적은 네트워크 흐름의 overview를 그려보고는 것이다. 대략적인 흐름을 이해하는 것에 중점을 두었고 너무 자세한 내용은 생략했다. 1 계층 Physical Layer 컴퓨터가 다루는 / 주고받는 모든 데이터는 0과 1의 나열이다. Physical Layer에서는 0과 1의 나열로 구성된 데이터를 지정된 주파수에 맞게 흘려보내고 수신자는 이를 받아 디지털 신호로 디코딩한다. 주로 신호를 주고받는 역할을 담당하기 때문에 하드웨어 레벨에서 처리된다. 2 계층 Data-Link Layer 같은 네트워크 상에 존재하는 다양한 단말 중에 목적지로 보내기 위한 역할을 담당한다.(목적지를 연산한다는 것은 아님) 주로 Framing 작업을 수행하는데, 원본 데이터를 frame이라는 단위로 묶어 다음 ..
2022.04.17 -
[백준] 2206 : DFS와 BFS차이
보호되어 있는 글입니다.
2022.02.13 -
크루스칼(MST) vs 다익스트라 비교
보호되어 있는 글입니다.
2022.02.03 -
[백준] 이중 우선순위 큐 (TreeMap)
TreeMap - Key-Value로 이루어진 entry를 Tree에 저장하는 자료구조 - Key를 기준으로 '정렬'한 형태의 Tree임 (~이진탐색트리) - Tree중에서도 레드블랙트리를 기반으로 함(이진탐색트리에서 balanced tree) - 즉, 모든 노드에서 왼쪽 서브트리의 값은 오른쪽 서브트리의 값보다 작음 - HashMap보다 성능이 떨어짐 - 하지만 정렬된 상태로 Map을 유지하거나 Key에 대해 범위 탐색을 할 경우 HashMap보다 유리함 cf. Heap과 구분해야 하는데, Heap은 루트 노드가 가장 우선순위를 큰 값을 갖는 형태지만 정렬되어 있지는 않음 - 최소 힙에서 최대값을 삭제하는 연산은 O(logN) 이라고 착각하기 쉬우나, O(N) 이 소요됨 - 이유는 힙은 정렬되어 있지 ..
2022.01.17 -
[DS] 레드블랙트리
이진탐색트리(Binary Search Tree) - 최대 자식노드를 2개 갖는 이진트리 - 정렬된 상태로 유지되기 때문에 탐색 효율이 좋음 (중위순회시 정렬된 상태로 출력됨) - Balanced Tree가 아니기 때문에 극단적으로 모든 노드가 자식노드를 1개씩만 갖게 되면 O(n) 성능을 보임 Red-Black Tree - 이진탐색트리의 일종이지만 Balanced Tree이기 때문에 성능을 O(logN)으로 보장함 - 이진탐색트리의 일종이므로 왼쪽 서브트리의 모든 값은 오른쪽 서브트리의 모든 값보다 작아야 함(정렬됨) - Red-Black Tree는 이진탐색트리 중에서 성능이 가장 좋다. - 따라서 리눅스 커널의 프로세스 관리, Java 8이상 HashMap에서 해쉬 블록의 value, 함수형 프로그래밍..
2022.01.11 -
<추천글>[DB] Index 종류와 카디널리티
Type Of Index single level index composite index multilevel index 1. Single Level Index - 인덱싱하는 컬럼이 1개인 경우에 해당함 - primary key에 걸면 Primary Index(기본 인덱스), 다른 컬럼에 걸면 Secondary Index(보조 인덱스) - SQL문에서 where = {key1} = {value1} 가 하나인 경우 equality search가 빠르다. - 메모리에 index table의 데이터 크기가 table보다 작음 - 카디널리티가 매우 낮은 컬럼이라면 인덱스를 지정하지 않는 것이 더 나을 수도 있음 [인덱스 정렬 타입] 1) Dense Index(밀집 인덱스) - 한 인덱스에 원하는 데이터가 바로 매칭..
2022.01.11 -
[백준] 12919 시간복잡도 풀이
코드 /** * https://www.acmicpc.net/problem/12919 */ import java.io.*; public class Main { private static String S, T; private static final char A = 'A'; private static final char B = 'B'; public static void main(String[] args) throws IOException { init(); var result = solve(T); var bw = new BufferedWriter(new OutputStreamWriter(System.out)); bw.write(result ? "1" : "0"); bw.flush(); bw.close(); } ..
2022.01.05 -
<추천글>[DB] DB Index 자료구조 B-Tree 기본개념
Balanced Tree - 한쪽으로 노드가 몰리는 Binary Search Tree의 단점을 보완하고자 등장 - DBMS에서 가장 범용적으로 사용되는 자료구조 - Binary Search Tree와 유사하지만 depth를 자동으로 잡아주기 때문에 탐색 시간복잡도가 O(logN)을 보장함 - 하지만 depth에 영향을 줄 수 있는 insert, delete 경우에 대해서는 성능이 좋지 않을 수 있음 - 결론적으로, 데이터를 얼마나 자주 삽입, 삭제할 것인가에 따라서 B-Tree Index를 활용할지 말지를 결정 - 즉, 갱신 빈도가 높은 테이블에 인덱스를 지정할 경우, 인덱스 재구성 발생 빈도가 높아진다는 점을 고려해야 함 B-Tree - 하나의 노드에 여러개의 값이 배치되는 구조의 트리 - 차수 M의 ..
2022.01.03 -
[OS] 데몬(daemon) 프로세스, nohup, &
데몬이란 - 사용자와 직접적으로 대화하지 않고, 백그라운드에서 오랫동안 돌면서 여러 작업을 하는 프로세스 - 데몬은 대개 부모 프로세스를 갖지 않으며, 즉 PPID(부모 프로세스 ID)가 1이며, 따라서 프로세스 트리에서 init 바로 아래에 위치함 - 데몬이 되는 방법은 일반적으로 자식 프로세스를 포크하고 자신을 죽이면서 init(PID=1)이 고아가 된 자식 프로세스를 자기 밑으로 데려가도록 하는 방식(fork off and die 방식) - 부모 프로세스는 fork호출 후 exit호출함으로써 자식 프로세스가 백그라운드에 남게 함 - 데몬 프로세스는 보통 네트워크 요청, 하드웨어 동작을 위한 용도로 사용되며 시스템이 시작될 때 데몬을 생성하는 경우가 많음 - 보통 프로세스 이름에 d가 붙는다 (htt..
2022.01.03