CS(Computer Science) 정리

시간복잡도

재귀함수 return 함수(n-1)+(n-2)일 때 : O(2의 n제곱)

log(N) : 효율이 좋은 검색 알고리즘. ex)이진탐색
N : 입력자료 각각에 일정량이 할당되는 경우
NlogN : 효율 좋은 정렬 알고리즘 ex)quick sorting, heap sorting
N제곱 : 이중 루프
N세제곱 : 삼중 루프

피보나치
재귀호출 : 2의 N제곱, 스택오버플로우 문제 야기
동적계획법(DP) : N
이진탐색(binary search) : log(N)
다익스트라 알고리즘 : V의 제곱
해시테이블 : 1
정렬 알고리즘
선택정렬 : N의 제곱 / 공간복잡도(N)
삽입정렬 : N의 제곱 / 공간복잡도(N)
버블정렬 : N의 제곱 / 공간복잡도(N)
합병정렬 : NlogN / 공간복잡도(2N)
퀵 정렬 : NlogN -> 최악의 경우 N의 제곱 / 공간복잡도 : N
pivot(기준점)을 정하고, pivot을 기준으로 작으면 왼쪽, 크면 오른쪽으로 swap, 정렬 될 때가지 구별한 왼쪽과 오른쪽을 나눠서 분할 처리. 최악의 경우 때문에 중간이나 랜덤값으로 pivot point를 정하기도 한다.
힙 정렬 : heapify 시간복잡도 N / 총 소요시간 NlogN
최대 힙의 경우 각 노드는 자식노드보다 크거나 같다, 모양은 완전이진트리이다. 즉, 마지막 레벨의 모든 노드는 왼쪽에 쏠려있다.

다익스트라 알고리즘

우선순위 큐를 이용한 다익스트라 알고리즘
다익스트라 알고리즘(Dijkstra Algorithm) :: 화투의 개발 블로그

1의 보수, 2의 보수

1의 보수는 0은 1로 1은 0으로 바꾸는 방식이다.
0000 0100 -> 1111 1011

2의 보수는 1의 보수에 1을 더하는 것이다.
0000 0100 -> 1111 1011 +1 -> 1111 1100
컴퓨터에서 음수 양수를 구별 하기위해 최상위 비트=MSB를 부호비트로 쓰는것이다.
최상위 비트가 0이면 양수, 1이면 음수로 표현 한다.
-> 1의 보수 방식에서 -0과 캐리 처리하는 문제점이 사라진다.

커널영역 유저영역

OS와 어플리케이션간 메모리를 보호하기 위해 커널영역, 유저영역을 구분한다.
이유는, 유저가 시스템영역을 침범하지 못하게 보안성과 안전성 확보하기 위해서 이다.

커널영역 : OS가 구동되는 영역
유저영역 : 어플리케이션이 구동되는 영역

멜트다운(MELTDOWN)

멜트다운을 이용하면 보안을 위해 응용 프로그램이 CPU의 캐시 메모리에 접근하지 못했던 기존 하드웨어 보안 구조가 통째로 무너진다.

자바스크립트

비동기 처리

자바스크립트의 비동기 처리란 특정 코드의 연산이 끝날 때까지 코드의 실행을 멈추지 않고 다음 코드를 먼저 실행하는 자바스크립트의 특성을 의미한다.

해시

key, value로된 쌍을 갖는 구조
해시 계산비용은 데이터 양과 무관하게 O(1)이다.
범위질의, 정렬 등에서는 적합하지 않음.
Collision(충돌) : 다른 키값인데 해시값이 동일하게 사용되는 경우
Cluster(클러스터) : 일부 지역의 주소들을 집중적으로 반환 하는 결과로 데이터들이 한 곳에 모이는 문제
참고사이트: Luyin : 자료구조 Hash Table (해시 테이블)

해시 함수의 알고리즘 종류

나눗셈 법

입력값을 테이블의 크기로 나누고, 그 ‘나머지’를 테이블의 주소로 사용한다.
어떤 값이든 테이블의 크기로 나누면 그 나머지는 절대 테이블의 크기를 넘지 않는다.
테이블의 크기 n을 소수로 정하는 것이 좋다고 알려져 있다.
자릿수 접기

숫자의 각 자릿수를 더해 해시 값을 만드는 것.
문자열을 키로 사용하는 해시 테이블에 잘 어울림.
문자열의 각 요소를 아스키 코드로 바꾸고 이 값을 각각 더한다.

충돌 해결 방법

체이닝

충돌 발생한 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제 해결.
새 데이터를 링크드 리스트의 맨 앞에 삽입.
순차탐색 해야하는 링크드 리스트의 단점.
해시테이블 + 이진탐색트리 결합은 최고!
선형탐사

충돌하면 현재 주소에서 고정폭만큼 다음으로 이동.
클러스터 현상이 잘 발생함.
제곱탐사

이동 폭이 제곱수로 늘어난다.
다른 해시값은 효과 있지만, 같은 해시값을 갖는 데이터에 대해 2차 클러스터 발생
이중해싱

클러스터 방지를 위해, 2개의 해시 함수를 준해서 하나는 최초의 주소를 얻을 때 또 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용.
재해싱

해시테이블의 크기를 늘리고, 늘어난 해시테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱하는 것.

교착상태(데드락) 4가지 조건

한정된 자원을 여러 곳에서 사용하려고 할 때 발생할 수 있다.

상호배제

자원은 한 번에 한 프로세스만이 사용할 수 있다.
점유대기

프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
비선점

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.
순환대기

각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

데드락 처리

교착상태 예방
- 상호배제 부정
  
  여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
- 점유대기 부정
  
  프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
- 비선점 부정
  
  자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
- 순환대기 부정
  
  자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.
교착상태 회피

은행원 알고리즘 - 안정상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기함
교착상태 탐지

자원할당 그래프를 통해 탐지할 수 있다.
교착상태로부터 회복

프로세스를 종료하는 방법과 자원을 선점하는 방법이 있다.

대칭형 / 비대칭형

대칭형 암호 알고리즘

암호화할 때 사용되는 Key값과 복호화 할 때 사용되는 Key값이 동일한 알고리즘
비대칭형보다 속도가 빠르다
A에서 만든 키를 B에게 전달할때 중간에 key를 가로챌 수 있는 문제

문제해결방법

비대칭형 암호 알고리즘을 이용하여 암호화 시킨 후 전송
전송하지 않고 동일한 key 생성하는 알고리즘

비대칭형 암호 알고리즘

암호화할 때 사용되는 Key값과 복호화 할 때 사용되는 Key값이 서로 다른 알고리즘
공개키와 개인키를 생성한다.
암호화된 공개키는 개인키를 가지고 있는 자신만 해독할 수 있기 때문에 공개키는 공개되더라도 안전하게 통신할 수 있다.

사용목적

대칭형 암호 알고리즘의 key를 암호화
인증

인증서 : Bank가 공개키를 인증할 수 있는 방법
인증서는 타겟의 공개키와 인증서에 기록된 공개키가 맞다는 사실을 인증기관이 보장한다는 내용을 담고 있다.
참고사이트: Jeremy’s Blog : 대칭형/비대칭형 암호 알고리즘

B 트리, B+트리

B+트리의 Data node는 연결리스트로 형성되어있고, Index node 하나의 크기와 똑같지 않아도 된다.
B+트리의 높이는 B트리보다 낮게 구성되므로 검색시간과 디스트에 접근하는 횟수가 줄어든다.
참고사이트: DB/자료구조 B-Tree(B트리), B+ 트리

네트워크

패킷(Packet)이란

인터넷 내에서 데이터를 보내기 위한 경로배정(라우팅)을 효율적으로 하기 위해서 데이터를 여러 개의 조각들로 나누어 전송을 하는데, 이 조각을 패킷이라고 한다.

TCP

인터넷상에서 데이터를 메세지의 형태로 보내기 위해 IP와 함께 사용되는 프로토콜

높은 신뢰정 보장
3-way handshaking 과정을 통해 연결하고 4-way handshaking을 통해 해제한다.
UDP보다 느리다
흐름제어 및 혼잡제어

UDP

데이터를 데이터그램 단위로 처리하는 프로토콜

신뢰성이 낮다
TCP보다 속도가 빠르다
비연결형 서비스로 데이터그램 방식을 제공한다
정보를 주고 받을 때, 정보를 보내거나 받는다는 신호 절차를 거치지 않는다
UDP헤더의 CheckSum 필드를 통해 최소한의 오류만 검출한다
신뢰성보다는 연속성이 중요한 서비스인 실시간서비스(streaming)에 자주 사용된다

참고사이트: TCP/UDP TCP와 UDP의 특징과 차이 - MangKyu’s Diary

HTTP 상태 코드

1xx (조건부 응답)
2xx (성공)
3xx (리다이렉션 완료)
4xx (요청 오류)
5xx (서버 오류)