반응형 CS4 [ 자료구조 ] 트리란?(이진 트리, 파이썬 트리 순회 방법, 이진 탐색 트리) 트리(Tree) 스택, 큐와 같은 선형 구조가 아닌 비선형 자료구조 계층적 관계를 표현한다. 일반적인 틀에서 삽입, 삭제 연산의 시간 복잡도 : O(logN) 트리의 구성 노드(Node) : 트리를 구성하는 각각의 요소 간선(Edge) : 각각의 노드를 연결하는 선 루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드 단말 노드(Terminal Node = Leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 최하위 노드 내부 노드, 비단말 노드(Internal Node) : 단말 노드를 제외한 모든 노드로 루트 노드도 포함 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 갖는다. 방향성이 있는 비순환 그래프로 Loop나 Circuit이 없다. 루트에서 어떤 노드로 가는 .. 2021. 3. 16. [ 자료구조 ] 선형 자료구조 - 스택, 큐, 덱 스택(Stack) LIFO(Last in First Out) 나중에 들어간 원소가 먼저 나온다. 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 구조 push : 데이터를 top 위치에 넣기 pop : 가장 최근에 푸시한 데이터가 나옴 stack underflow : 자료가 없을 때 pop 하면 발생하는 오류 stack overflow : 스택의 크기 이상 자료를 push 하면 발생하는 오류 삽입, 삭제의 시간 복잡도 : O(1) → 장점 큐(Queue) FIFO(First in First Out) 먼저 들어간 원소가 먼저 나온다. front : 데이터가 삽입(push)되는 곳 back : 제거(pop)되는 곳 삽입, 삭제의 시간 복잡도 : O(1) → 장점 덱(Deque) 양쪽 끝에서 입출력이 가능한 자료구조.. 2021. 3. 16. [ 자료구조 ] 배열(Array) vs 리스트(List) - 특징, 차이 배열(Array) 데이터가 많아지고 그룹 관리의 필요에 따라 배열을 사용한다. 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인(논리적 저장 순서와 물리적 저장 순서가 일치) 형태로 구성된 자료구조 인덱스에 따라 값을 유지하므로 원소가 삭제되어도 빈자리가 남게되어 메모리가 낭비된다. 처음 크기를 10으로 지정한다면 5개의 데이터만 저장하더라도 실제 배열의 크기는 10이다. 인덱스(index) : 각 원소의 번호로 0번부터 시작하며, 해당 원소에 접근한다. 데이터 갯수가 확실하게 정해져 있고, 접근이 빈번한 경우 배열이 효율적이다. cache hit 가능성이 커져 성능에 큰 도움이 된다. cache hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우 고정이고 연속적인 만큼 인덱스로 r.. 2021. 3. 15. [ Network ] TCP/IP 동작 과정(데이터 송수신 과정) TCP/IP를 통해 송신자와 수신자 간 데이터를 주고 받을 때의 동작 과정입니다. 1. Client : Application (HTTP, SMTP, POP3, FTP) 클라이언트로부터 특정 주소로 요청이 들어오면 DNS 상에서 IP주소를 받아온다. 애플리케이션간 데이터를 주고받기 위해 필요한 정보를 HTTP 계층에서 HTTP 메시지를 작성 2. Client : Transport (TCP) HTTP 메시지를 패킷으로 나누고 애플리케이션을 나타내는 번호와 데이터 조합하기 위한 정보를 작성 3. Client : Network (IP) 전송 위치를 확인하며 송수신할 컴퓨터 주소와 불명인 경우 데이터를 파기하는 표시 등을 작성 4. Client : Data Link (Ethernet) 네트워크 종류에 맞춘 형식으.. 2021. 3. 15. 이전 1 다음 반응형