KNOU/요약정리57 [자료구조] 힙 우선순위 큐 대기 리스트에서 우선순위가 높은 사람이 먼저 서비스를 받는 구조 우선순위 큐의 작동방식 삭제 명령이 실행되면 저장된 데이터 중에서 가장 작은 값(가장 큰 값) 이 삭제 된다. 나머지 데이터들은 어떤 순서로 저장되든 문제가 되지 않는다. 힙 추상 자료형 힙의 정의 피라미드 모양으로 쌓아올린 더미 무엇인가 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조 부모- 자식 노드 사이에서 (부분적) 정렬된 완전 이진트리로 부모 노드는 자식 노드보다 우선 순위가 높음 힙 객체의 정의 부분적으로 정렬된 완전 이진 트리로 부모노드는 자식노드보다 우선순위가 높다 연산 연산 내용 insert(element) 힙에 데이터 삽입 delete() 힙(루트) 에서 데이터 삭제 peek() 힙(루트) 에서 .. 2023. 11. 29. [자료구조] 스레드 트리 스레드트리 이진트리의 노드 순회 : 전위, 중위, 후위 순회 이진트리의 노드를 순환 함수를 사용하지 않고, 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리 해야 하는 번거로움이 발생. → 스레드라는 포인터를 추가하여 트리 순회를 편리하게 한 것 스레드 순회 방법에 따라 방문 순서를 유지하는 포인터 스레드 트리 구현 스레드의 구현 방법 : 포인트 필드의 추가 포인터 필드의 추가 : 스레드를 저장하는 포인터를 추가 하는 것 → 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의 함 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킨다. 왼쪽 스레드 : 그 노드의 선행 노드를 가리킨다. 스택을 운영하지 .. 2023. 11. 29. [자료구조] 트리 트리의 개념 트리의 정의 검색의 편리함 논리적 계층 계급적 특성 트리의 표현방법 트리의 구성 노드 : 트리의 항목/트리 에 저장되는 데이터의 묶음 부모노드 - 자식노드 : 상하 계층구조가 있고 직접적으로 연결된 노드들로서 상위계층의 부모노드와 하위계층의 자식노드를 의미함 루트노드 트리의 최상위 노드 (부모가 없는 노드) 서브트리 부모노드를 삭제하면 생기는 트리들 잎 노드 트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드 진입 / 진출 차수 루트노드 : 진입차수 = 0 루트를 제외한 모든 노드의 진입차수 = 1 잎노드 : 진출차수 = 0 내부 노드와 형제 내부 노드 : 루트, 잎 노드가 아닌 나머지 노드 형제 : 같은 부모를 갖는 노드들 트리의 레벨 노드의 레벨 : 루트로부터 그 노드까지.. 2023. 11. 29. [자료구조] 연결 리스트의 응용 연결 리스트의 변형 단순 연결 리스트 단순 연결 리스트의 문제점 하나의 링크 만 있고, 각각의 노드의 링크는 후행 노드만을 가리키는 구조. → 특정 노드의 후행 노드는 쉽게 접근 가능 하지만 , 선행 노드를 찾으려면 헤드 노드 부터 다시 검색 해야 함. (비 효율적) 이중 연결 리스트 선행과 후행을 가리키는 두개의 링크를 가진다. → 특정 노드에서 선행 노드와 후행 노드에 직접적으로(간단한 코드를 통해) 접근이 가능 원형 연결 리스트 연결 리스트를 살펴보면, 가장 마지막 노드의 링크 필드는 언제나 NULL → 리스트의 마지막 원소 뒤에는 아무 원소도 없기 때문에 연결 리스트의 마지막 노드의 링크 필드는 언제나 null → 마지막 노드의 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해 원형 연.. 2023. 11. 28. [자료구조] 연결리스트 리스트의 개념 리스트의 의미 일정한 순서 의 나열 어떤 정의에 의해 결정된 논리적인 순서 의 나열 배열의 정의 원소의 메모리 공간(메인 메모리, DDR) 의 물리적인 위치를 순서 적으로 결정하는 특징 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서 → 리스트의 순서는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 논리적인 순서 혹은 리스트에 나타나는 원소들 간의 의미적인 순서를 의미함 리스트의 구현 방법 포인터를 이용한 리스트의 구현 방법 → 원소 값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법 배열을 이용한 리스트의 구현 방법 배열을 이용한 리스트의 구현 배열을 이용한 리스트의 구현 구현해야 할 리스트가 3.1 운동(1919.. 2023. 11. 28. [자료구조] 큐 큐의 개념 큐의 의미 추상자료형 → 택시를 타기 위해 서 있는 행렬 → 병원 접수대 → 예금 인출기 → 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케쥴 (First - In - First - Service) 한쪽에서는 삽입연산만 발생 , 다른쪽에서는 삭제 연산만 발생 가능한 구조 삽입연산 → 서비스를 받기 위한 기다림 삭제연산 → 서비스를 받는 중 선입 선출 ( First - In - First - Out, FIFO) 알고리즘이 사용 됨 큐의 정의 삽입 구조 D 입력 시 rear 포인터가 한칸 이동 삭제 구조 front 값 삭제 포인터 활용 front : 삭제 rear : 삽입 큐의 추상 자료형 큐의 객체 정의 큐 객체 → 0개 이상의 원소를 갖는 유한 순서 리스트 큐의 삽입(Add_q) 연산.. 2023. 11. 28. [자료구조] 스택 스택의 개념 스택의 정의 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 자료 구조 → 먼저 입력된 자료가 가장 나중에 출력되는 관계 → 관계를 표현하기 위해서 연산이 필요하며, 객체에 대한 정의와 연산이 모여 순서가 기억되는 스택의 추상 자료형이 완성 됨 0개 이상의 원소를 갖는 유한 순서 리스트 push(add) 와 pop(delete) 연산이 한곳에서 발생되는 자료구조 스택의 추상자료형 스택 객체 → 0개 이상의 원소를 갖는 유한 순서 리스트 push 연산 Stack Push(stack , item) ::= if(StackIsFull(stack)) then{'stackFull' 출력;} else{스택의 가장 위에 item 을 삽입하고, 스택을 반환한다;} pop 연산 Element Pop(s.. 2023. 11. 28. [자료구조] 배열 배열의 정의 배열의 정의 일정한 차례나 간격에 따라 벌여놓음(사전적 정의) “차례” (순서) 와 관련된 기본적인 자료구조 → 원소의 메모리 공간(메인 메모리, DDR) 의 물리적인 위치를 “순서”적으로 결정하는 특징 → 배열의 순서는 메모리 공간에서 저장되는 “원소값의 물리적 순서” 배열의 의미 인덱스와 원소값(index, value) 의 쌍으로 구성된 집합 → 원소들이 모두 같은 자료형과 같은 크기의 기억공간을 가짐 → 배열의 인덱스 값을 이용해 원소 값에 접근하기 때문에 직접 접근이 가능 배열의 인덱스 값 : 추상화된 값 = 컴퓨터의 내부구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의 됨 → 메모리 주소값은 실제 메모리의 물리적인 위치 값 배열의 (추상화된) 인덱스 값은 프로그래밍 언어와 컴.. 2023. 11. 28. [HTML5 웹 프로그래밍] HTML5 API 웹 스토리지 클라이언트에 데이터를 저장하기 위한 영역 쿠키 웹 스토리지 저장 용량 4KB 도메인당 5MB (사실상 용량의 제한이 없음) 네트워크 전송 부하 및 보안 웹 서버에 요청을 보낼 때마다 HTTP 헤더에 담아서 전송 → 많은 트래픽의 발생 및 보안의 취약성 존재 웹 서버로 요청을 하더라도 HTTP 메시지에는 포함되지 않음 → 네트워크 부하 감소 유효 기간 유효 기간이 존재 → 기간 만료 시 자동 삭제 로컬 스토리지는 유효 기간이 없음→ 사용자에 의한 명시적인 삭제에 의해서만 삭제 가능 세션 문제 브라우저의 모든 윈도우가 고유하며, 독립적인 데이터의 저장 X 각 윈도우마다 독립적으로 데이터 저장 O 저장되는 데이터의 구성 (key , value) 키를 통해서만 원하는 데이터의 값에 대한 접근이 가능.. 2023. 6. 13. 이전 1 2 3 4 5 6 7 다음 728x90
