전체 글
-
[Data Structure] Minimum Spanning TreeCS/Data Structure 2021. 10. 8. 09:03
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 n-1개이고, n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. 이것이 Spanning Tree이다. Minimum Spanning Tree Spnning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 MST 구현 방법 Kruskal Algorithm 각 단계에서 사이클을 이루지 않는 최소 비용 ..
-
[Data Structure] HashCS/Data Structure 2021. 10. 8. 08:39
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Hash Table hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가진다. hash function을 사용하여 저장할 데이터과 연관된 고유한 숫자(hashcode)를 만들어 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입, 삭제 연산 시 shift 연산의 추가적인 비용이 없도록 만들어진 구조이다. Hash Function 저장되는 값들의 key 값을 hash function을 통해 작은 범위의 값들로 바꿔준다. ..
-
[Data Structure] Red-Black TreeCS/Data Structure 2021. 10. 8. 08:00
Red-Black Tree Red-Black Tree는 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조이다. 이진 탐색 트리는 저장, 삭제, 탐색 시 O(logN)의 시간 복잡도를 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다. 👉 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 Red-Black Tree가 고안됨. 특징 탐색, 삽입, 삭제에 대해 Binary Search Tree의 특성을 사용한다. 각 노드는 Red or Black 색상이 할당된다. Rotation과 Recoloring을 통해 균형을 유지한다. 탐색, 삽입, 삭제 시 O(logn)의 시간복잡도를 가진다. 삽입, 삭제 시 Red-Black Tree의 5가지 조건을..
-
[Data Structure] AVL TreeCS/Data Structure 2021. 10. 7. 14:16
AVL Tree 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조 이진 탐색 트리가 평균 저장, 삭제, 탐색 시간 복잡도가 평균 O(logN)을 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다. 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 AVL 트리가 고안됨. 특징 AVL 트리는 이진 탐색 트리의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이 차이(Banlance Factor)가 최대 1이다. Balance Factor가 1보다 커지면 회전(rotation)을 통해 균형을 잡는다. AVL 트리의 높이(h)는 logN을 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다. 회전(Rotation) 삽입, 삭제 시..
-
[Data Structure] HeapCS/Data Structure 2021. 10. 7. 13:20
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Heap 완전 이진 트리(Complete Binary Tree) 기반 자료구조로 반정렬 상태(느슨한 정렬 상태)를 유지한다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 형제 또는 사촌 노드 간의 우선순위는 정해진 것이 없음 힙은 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않음) 종류 최대 힙(Max Heap) key(부모 노드) ≥ key(자식 노드) 최소 힙(Min Heap) key(부모 노드) ≤ key(자식 노드) 시간 복잡도 Max(Mi..
-
[Data Structure] Binary Search TreeCS/Data Structure 2021. 10. 7. 12:52
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Tree 비선형, 계층적 재귀적 자료구조 정점의 갯수가 N이면 간선의 수는 N-1 종류 편향 트리(Skew Tree): 한쪽으로 기울어진 트리 이진 트리(Binary Tree): 트리의 차수가 2 이하인 트리, 레벨 N의 노드의 수는 최대 2^(n-1)개이다. 포화 이진 트리(Perfect Binary Tree): 모든 레벨이 꽉찬 이진 트리 완전 이진 트리(Complete Binary Tree): 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리 정 이진 트리(Full Binary ..
-
[Network] DNS 동작 원리CS/Network 2021. 9. 29. 12:51
DNS (Domain Name System) DNS는 호스트의 도메인 이름을 호스트의 네트워크 주소(IP)로 바꾸거나 그 반대의 변환을 수행하는 시스템이다. 분산 데이터베이스를 사용한다. 계층 구조를 가지고 있다. DNS 서버는 네 가지 카테고리, 즉 Local DNS name server, Root dns server, Top-level domain(TLD) server, Authoritative DNS server로 분류된다. 캐싱이 없는 일반적인 DNS 조회에서는 이 네 가지 DNS 서버가 함께 작동하여 지정된 도메인의 IP주소를 클라이언트에게 전달하는 작업을 완료한다. Root DNS server Root DNS server는 요청받은 쿼리의 도메인의 확장자(.com, .net, .org ...)..
-
[Network] HTTP vs HTTPSCS/Network 2021. 9. 29. 11:49
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Network를 참고하여 작성하였습니다. HTTP(Hypertext Transfer Protocol) 텍스트 기반의 통신 규약으로 인터넷에서 데이터를 주고받을 수 있는 프로토콜이다. HTTP 동작 클라이언트가 브라우저를 통해서 어떠한 서비스를 URL을 통하거나 다른 것을 통해서 요청(request)을 하면 서버에서는 해당 요청사항에 맞는 결과를 찾아서 사용자에게 응답(response)하는 형태로 동작한다. HTTP 특징 TCP를 사용한다. stateless 서버는 클라이언트의 요청(request)에 대한 정보를 유지하지 않는다. → 서버에는 수많은..