본문 바로가기

CS

 (54)
트리(Tree) 1. 트리란? 노드와 엣지로 이루어진 자료구조이다. 사이클이 존재하지 않는다. 사이클이 존재한다면, 이는 그래프이다. 모든 노드는 자료형으로 표현이 가능하다. 루트에서 한 노드로 가는 경로는 유일하다. 노드가 N개라면 간선은 N-1개이다. 계층 구조가 확실한 구조에서 사용한다. 2. 트리 순회 방식 ① 전위순회 부모-왼쪽 자식-오른쪽 자식 순으로 방문 void preOrder(int idx){ if(tree[idx]){ cout
힙(Heap) 우선순위 큐를 위해 만들어진 자료구조이다. 우선순위 큐는, 데이터들의 우선순위 차례대로 데이터가 나가는 자료구조를 말한다. 시뮬레이션, 작업 스케줄링, 수치해석 계산 등에 사용된다. 삽입, 삭제 모두 O(logN)이 걸린다. 1. 힙이란? 완전 이진 트리의 일종 최대, 최소값을 빠르게 찾도록 만들어진 자료구조 반정렬 상태(전체 정렬 상태가 아님!) 중복된 값을 허용한다 탐색에 적합하지 않다 특정 노드로 접근이 불가능하다 ① 최대힙(C++) ② 최소힙(Java) 두 종류가 있다. 2. Heap vs BST(이진 탐색 트리) BST 특정 노드 접근 가능 정렬된 상태 유지 중복 허용 X Heap 특정 노드 접근 불가능 전체 정렬 X 중복 허용 부모 노드와 자식 노드 관계 왼쪽 자식 index = (부모 ind..
스택&큐 1. 스택(Stack) LIFO 후입선출 구조를 갖는다. 함수 콜스택, 문자열 역순 출력, 연산자 후위표기법 등에 사용된다. 삽입, 삭제 시 O(1), 검색 시 O(N) 2. 큐(Queue) FIFO 선입선출 구조를 갖는다. 버퍼, 입력된 것을 처리하지 못하고 있는 상황, BFS 등에 사용된다. 삽입, 삭제 시 O(1), 검색 시 O(N)
Array vs ArrayList vs LinkedList 1. Array index로 접근이 가능하다. 검색이 용이하다. 배열 크기가 정해져있고, 연속된 메모리 공간에 저장된다. 중간에 데이터를 저장, 삭제하는 경우 비효율적이다. int arr[10]; string arr[5]; 와 같이, 선언할 때 크기와 데이터타입을 지정해 주어야 한다. 2. ArrayList 선언할 때 크기를 지정해주지 않아도 된다. C++에서는 벡터를 생각하면 된다. array에서는 배열에 접근하기 위해 index가 중요했지만, list에서는 데이터의 순서가 중요하다. 배열 크기가 동적이라는 장점이 있지만, 중간에 데이터를 삽입, 삭제할 경우 여전히 시간이 많이 걸린다. 3. LinkedList 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 구현된다. index로 접근하지 못..
BigO(시간복잡도) 1. 알고리즘이란? 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들 여러가지 상황에 따른 알고리즘은 모두 다르다. 시간 복잡도가 가장 낮은 알고리즘을 선택하여 사용한다. 알고리즘 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 2. 점근적 표기법 최상의 경우: 오메가 표기법 (Big-Ω Notation) 평균의 경우: 세타 표기법 (Big-θ Notation) 최악의 경우: 빅오 표기법 (Big-O Notation) 보통은 최악의 경우를 기준으로 알고리즘 성능을 판단한다. 3. 빅오 표기법 시간 복잡도와 공간 복잡도가 있다. 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다. 공간복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다. 오..
HTTPS의 동작원리 1. HTTPS란? 인터넷 상에서 정보를 암호화하는 SSL 프로토콜을 사용해 클라이언트와 서버가 자원을 주고받을 때 사용하는 통신 규약 2. HTTPS 통신흐름 ① 서버(A)는 HTTPS를 적용하기 위해 공개키와 개인키를 만든다. ② 신뢰할 수 있는 CA 기업을 선택하고, 그 기업에게 공개키 관리를 부탁하며 계약을 한다. CA란? Certificate Authority로, 공개키를 저장해주는 신뢰성이 검증된 민간기업 ③ 계약 완료된 CA 기업은 해당 기업의 이름, A서버 공개키, 공개키 암호화 방법을 담은 인증서를 만들고, 해당 인증서를 CA기업의 개인키로 암호화하여 A서버에게 제공한다. ④ A서버는 암호화된 인증서를 갖게 되었다. 이제 A서버는 A서버의 공개키로 암호화되지 않은 HTTPS 요청이 오면,..
대칭키 vs 공개키 1. 대칭키(Symmetric Key) 암호화, 복호화 시에 같은 암호키를 사용한다. 동일한 키를 주고받기 때문에 매우 빠르다는 장점이 있지만 대칭키 전달 과정에서 해킹 위험에 노출된다. 키 하나만 알면 해커가 암호화, 복호화 모두 가능하다. 2. 공개키(Public Key) 암호화, 복호화 시에 사용하는 키가 다르다. B의 공개키로 A가 자신의 데이터를 암호화하여 B에게 전송한다. B는 자신의 개인키로 A의 데이터를 복호화한다. 이에 따른 응답을 A의 공개키로 암호화하여 A에게 전송한다. A는 자신의 개인키로 B의 데이터를 복호화한다. 하지만 속도가 느릴 수 있고 암호화/복호화가 매우 복잡하다. 3. 공개키+대칭키 SSL 탄생의 시초 1. A가 B의 공개키로 암호화 통신에 사용할 대칭키를 암호화하여 B..
CAP이론 1. CAP 이론이란? 시스템은 Consistency, Availability, Partition tolerance 중 두 가지만 만족할 수 있다는 것이다. 2. CAP ① Consistency(일관성) ACID 와 같이, 항상 동일한 데이터를 보여주어야 한다. ② Availability(가용성) 모든 요청에 대해서 정상적인 응답을 해야한다. DB가 다운되어도 read, write 등의 동작은 항상 성공적으로 리턴되어야 한다. ③ Partition tolerance(분단 허용성) 클러스터가 여러 대 동작하고 있을 때 통신 장애가 발생해도 시스템이 정상적으로 동작해야 한다. 관계형 데이터베이스는 CA 시스템이다.
JOIN 1. JOIN 이란? 두 개 이상의 테이블이나 데이터베이스를 연결하여 데이터를 검색하는 방법 2. JOIN의 종류 ① INNER JOIN 교집합으로, 기준 테이블과 JOIN 테이블의 공통 부분을 보여준다. SELECT A.NAME, B.AGE FROM EX_TABLE A INNER JOIN JOIN_TABLE B ON A.NO_EMP = B.NO_EMP ② LEFT (OUTER) JOIN 왼쪽테이블 기준으로 모든 컬럼에 대해 JOIN 연산을 수행한다. NULL값이 표시될 수도 있다. RIGHT (OUTER) JOIN은 생략 SELECT A.NAME, B.AGE FROM EX_TABLE A LEFT OUTER JOIN JOIN_TABLE B ON A.NO_EMP = B.NO_EMP ③ FULL OUTER ..
DB 역정규화 1. 역정규화란? 정규화를 하면 JOIN 연산 시 시간이 많이 걸릴 수 있다. 이러한 과부하를 방지하기 위해 정규화를 통해 분리되었던 릴레이션의 중복을 허용하고 다시 통합하거나 분할하여 구조를 재조정하는 과정이다. 2. 역정규화 종류 ① 릴레이션 역정규화 릴레이션 병합: 두 릴레이션 간의 잦은 참조로 성능이 저하될 경우 이를 해결하기 위해 두 릴레이션을 병합한다. 릴레이션 분할: 자주 사용하지 않는 속성이나 튜플이 릴레이션에 있을 경우 검색 성능이 저하된다. 이 때에는 자주 사용하는 속성이나 튜플을 분해하여 성능을 향상시킨다. 수직/수평 분할이 있다. ② 속성 역정규화 릴레이션의 성능을 향상시키기 위해 속성 또는 파생속성을 추가한다. 파생 속성: 현재 릴레이션에는 없는 속성이지만 작업의 효율을 위해 한 ..

티스토리툴바