[CS] Computer Science 기본 지식

[Data Structure]

[Stack]

FILO(First Input Last Out): 첫번째 들어온놈이 나중에 나간다는 뜻 - 동전지갑

함수호출시 함수 콜이 쌓일 때 사용한다. (함수의 지역변수)

함수는 기본적으로 특정 값들을 인자로 받아, 연산을 하고 결과 값을 return 하는데,

자신을 호출한 곳으로 결과를 돌려준다.

Process를 이루는 Stack 메모리는 제한된 크기의 메모리를 사용하므로 

너무 많은 함수 호출이 발생하여 메모리를 넘어갈 경우 StackOverflow가 발생한다.

재귀함수를 사용하면 함수가 쌓이는 것을 쉽게 확인할 수 있다.

높은 주소에서 낮은 주소로 쌓아나간다.

[Heap]

FIFO(First Input First Out): 첫번째 들어온놈이 첫번째로 나간다. - Queue와 비슷

낮은 주소에서 높은 주소로 쌓아나간다.

프로그래머가 관리하는 영역으로, 동적으로 메모리를 할당할때 이용하는 영역이다.

프로그램 컴파일시 특정크기를 판단할 수 없거나, 메모리를 효율적으로 관리하기 위해서 사용한다.

제대로 사용하지 않으면, BufferOverflow가 발생하니까, 사용이 완료된 메모리는 해제시켜주어야 한다.

C에서는 malloc(memory allocation) & free 를 사용해서 직접해제시킨다.

Java의 경우에는 가비지컬렉터 메모리 해제를 도와준다.

[Tree]

시간 복잡도: O(logN)

공간 복잡도: O(N)

이진트리: 포화, 완전, 편향

전위순회(중왼오) / 중위순회(왼중오) / 후위순회(왼오중)

사이클이 없는 그래프

삽입 / 삭제이 빈번 경우, 탐색도 필요한 경우.

[HashMap]

시간 복잡도: O(1), (최악의 경우 O(N))

공간 복잡도: O(NM)

Hash는 one-way function 이므로 모든 input에 대해서 고유의 output을 만들어준다.

크기가 크던 작던 결과로 나오는 값은 항상 같은 길이이므로 input이 다르더라도 같은 결과가 나올 수 있다.

이것을 Collision이라고 한다. 주로 Collision을 담을 수 있도록 Map bucket을 List로 만드는데,

모두 같은 값들이 하나의 버킷에 담길 경우 탐색하는데 O(N)의 시간복잡도가 걸릴 수 있다.

빈번하게 삭제 / 삽입이 일어나지 않으며, 검색이 주를 이룰 경우

[DB]

INSERT INTO table_name (column1, column2, column3, ...) VALUES (value1, value2, value3, ...);

SELECT column1, column2, ... FROM table_name;

UPDATE table_name SET column1 = value1, column2 = value2, ... WHERE condition;

DELETE FROM table_name WHERE condition;

join: inner / outer left / outer right / full

groupBy + having

orderBy: asc, desc

[정규화]

삭제이상, 삽입이상, 수정이상

이상현상을 줄이기위해, 테이블을 쪼개는 것

쪼개면 쪼갤 수록 join을 통해 하나로 묶어줘야 하므로 장단점을 따져서 수행해야한다.

뷰만 필요한 경우, 테이블을 쪼개는게 독이될 수 있다.

[transaction]

단위 작업; 묶음 작업; 여러개의 쿼리를 한꺼번에 수행하도록 한다. 

은행계좌에서 돈을 차감하고 다른 계좌에 돈을 더해주는 일이 한꺼번에 이루어져야 하는데

이런 함께 처리되어야 될 로직들을 묶어서 처리하는 작업이다.

장애가 발생하여 차감만 하고 더해주지 못하는 경우 기존 차감작업을 롤백한다.

[OS]

[process]

실행중인 프로그램; 자원을 할당 받는 단위

[thread]

실제 작업을 할당 받아 일을 수행하는 단위; 할당된 자원을 가지고 사용하는 단위

[multi-tasking]

여러 개의 프로그램을 사용하는 것?

[multi-process]

하나의 작업에 여러개의 process를 할당하는 것?

[multi-thread]

하나의 프로세스에 여러개의 스레드가 있는것; 사용자랑 대화, 특정작업처리를 각각의 스레드에서 나눠서 할 수 있으므로 응답성이 좋아진다.

여러개의 스레드는 프로세스의 stack을 제외한 code, data, heap 자원을 공유하므로 context switching의 비용이 줄어든다.

자원을 공유해서 사용하므로, 하나의 스레드가 사용중인 자원을 다른 스레드가 사용하면 안될 때가 있다. 

이런 경우를 critical section으로 만들고 작업이 끝날때까지 lock을 걸어서 다른 스레드가 사용하지 못하도록 한다.

IPC(Inter Process Communication)을 위한 리소스를 아낄 수 있다.

스레드하나에 문제가 발생하면 다른 스레드까지 영향을 준다.

스레드가 너무 많아지면 성능상 영향을 준다.