트리 (Tree) 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조 노드들을 간선으로 연결한 계층형(Hierarchical) 자료구조 트리를 구성하고 있는 구성요소들(용어) Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다. Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다. Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다. Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다. Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다. 이진트리 (Binary Tree) 각 노드가 최대 두개의 자식을 갖..
"힙에서 할 수 있는건 어차피 균형 이진 트리에서도 할 수 있지 않나요? 그러면 균형 이진 트리가 더 제공해주는 기능이 많은데 힙을 쓸 이유가 있나요?" 라고 물었을 때 뭐라고 답을 하면 깔끔한 답이 될까요? 답은 이렇습니다. 힙에서 할 수 있는걸 균형 이진 트리에서 할 수 있는 것이 맞고, 자가 균형 트리라는 가정하에 시간복잡도가 O(lg N)O(lgN)으로 동일한 것도 맞습니다. 그러나 힙은 균형 이진 트리보다 수행 속도도 빠르고, 구현도 쉽고, 공간도 적게 차지하기에 최소 혹은 최댓값의 확인/삭제만 필요할 떄에는 힙을 쓰는 것이 더 좋습니다. 힙은 삽입, 최솟(혹은 최댓)값 삭제가 O(lg N), 최솟(혹은 최댓)값 확인이 O(1)입니다. 즉, 최소 최대값 확인은 힙이 더 유리하다. from htt..
TCP/UDP 전송계층(데이터의 전달을 담당하며 통신 서비스를 제공하는 계층)에서 사용하는 프로토콜 데이터를 보내기 위해 사용하는 프로토콜 패킷을 한 컴퓨터에서 다른 컴퓨터로 전달해주는 IP 프로토콜을 기반으로 구현 TCP TCP는 신뢰성을 보장하는 연결형 서비스 안정적으로, 순서대로, 에러없이 데이터 전송 제어 흐름 제어 (Flow Control) 수신자가 감당할 수 있도록 데이터 처리 속도 조절 혼잡 제어(Congestion Control) 네트워크 내 패킷 수가 넘치게 증가하는 것 방지 연결형 서비스 (Connection-oriented) 3-way handshaking으로 연결 설정 목적지와 수신지를 확실히 하여 정확한 전송 보장 4-way handshaking으로 연결 해제 신뢰성 보장 (Rel..
Array 1. 물리적 저장순서와 논리적 저장순서가 일치한다. 2. 메모리상에 연속적으로 위치하므로, cache locality에 유리하다. 3. Index를 통해 해당 원소에 접근이 가능하다. 즉, Random Access가 가능하다. 4. 삽입, 삭제시 1번의 특징을 지키기위해 데이터들의 shifting이 필요하고, O(n)의 시간복잡도를 갖는다. 5. compile-time에 크기가 결정되고 메모리의 stack 영역에 할당된다. Linked List 1. 각 원소들이 다음 원소의 위치(주소)를 저장하고 있는 자료구조. 종류에 따라 이전 원소의 위치도 저장하고 있기도 함. 2. 다음원소의 주소를 저장하는 공간 즉, overhead가 존재 3. 메모상에 연속적으로 저장 되지 않는다. 4. 어떤 원소에 ..
OSI layer 7 https://pinelover.tistory.com/180?category=0 네트워크 면접 대비 3편 - DNS,네트워크 7계층 찾다 보니, 이전에 학교에서 공부했던 개념들인게 기억이 났다. 전체적인 메커니즘도 알아야 겠지만, 각 용어나 개념들에 대해서도 자세히 아는게 좋겠다. n사에서 crc같은게 이차 면접으로 전에 pinelover.tistory.com OSI layer vs TCP/IP layer https://goitgo.tistory.com/25 OSI 7 Layer 과 TCP/IP 4 Layer(TCP/IP Protocol suite) 비교 OSI 7 Layer vs TCP/IP Protocol Suite 1. OSI 7 Layer 개요 ➀ 네트워크 통신을 체계적으로 ..