본문 바로가기
반응형

코딩테스트 및 개인공부/자료구조10

[자료구조] [10] 우선순위 큐 우선순위 큐 우선순위 큐(priority queue)는 모든 데이터가 우선순위를 갖고 있고, 들어온 순서와 상관 없이 우선순위가 높은 데이터가 먼저 출력되는 구조. (보통의 큐는 FIFO 구조) 우선순위 큐는 컴퓨터의 네트워크 트래픽 제어, 운영체제에서의 작업 스케줄링 등에서 활용. 우선순위 큐를 구현하는 가장 효율적인 구조는 힙(heap). - 우선순위 큐의 연산 우선순위 큐에서도 가장 중요한 연산은 삽입, 삭제. 삭제연산에서 어떤 요소가 먼저 삭제되는가에 따라 최소 우선순위 큐 / 최대 우선순위 큐 로 나눈다. 최대 우선순위 큐 : 우선순위가 가장 높은 요소가 먼저 삭제. 최소 우선순위 큐 : 우선순위 가장 낮은 요소를 먼저 삭제. -> 최대 우선순위 큐의 delete() : 가장 우선순위가 높은 요.. 2022. 1. 8.
[자료구조] [9] 이진탐색트리 이진탐색트리 *이진탐색트리의 가장 큰 용도는 map 자료구조 구현하는 것. - 탐색이란? 레코드의 집합에서 특정한 레코드를 찾아내는 작업. 레코드는 하나 이상의 필드로 구성. 예) 학생정보 구조체 = 레코드 / 구조체의 멤버 변수인 학번,이름,주소,주민번호 = 필드 - 키(Key) : 레코드를 서로 구별하기 위해 필드 중에 서로 중복되지 않는 고유한 값을 갖는 필드. 예) 주민번호, 학번이 해당. 탐색은 주어진 키를 가진 레코드를 찾는 작업. 레코드가 노드에 저장되는 이진탐색트리에서는 주어진 키를 가진 노드를 찾아야 한다. - 이진탐색트리(Binary Search Tree)의 정의 효율적인 탐색을 위한 이진트리 기반의 자료구조. 모든 노드는 유일한 키를 갖는다. 왼쪽 서브 트리 키들은 루트 키보다 작다... 2021. 12. 30.
[자료구조] [8] 트리 트리 -트리의 개념 선형 자료 구조: 스택, 큐, 리스트 -> 자료들이 일렬로 나열된 형태 트리는 계층적인 자료를 표현하는데 이용되는 자료구조. 예) 회사 조직도, 컴퓨터 폴더 구조, 인공지능의 결정 트리.. A,B,C,D,E,F,G,H,I,J는 노드(node) 트리는 한 개 이상의 노드로 이루어지고, 계층적 구조에서 가장 높은 곳에 있는 노드는 루트(root) 노드 나머지 노드들은 서브 트리(subtree). -> 루트의 다음 레벨에 있는 노드들은 서브 트리들의 루트가 된다. 루트와 서브트리를 연결하는 선은 간선/에지 A는 B의 부모 노드. B는 A의 자식 노드. B,C,D는 형제. 자손 노드 : 임의의 노드 하위에 연결된 모든 노드들. 즉 어떤 노드의 서브 트리에 속하는 모든 노드들은 자손노드. 단말.. 2021. 12. 29.
[자료구조] [7] 순환 순환, 또는 재귀 호출이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법. 트리 구조에서 많이 사용된다. 순환 호출의 내부적인 구현 -시스템 스택과 활성 레코드 A라는 함수에서 함수 B가 호출되면, (B가 자기자신, 즉 A라도 전혀 문제가 없다) B가 끝나고 A의 처리 상황을 복원할 수 있도록 A의 복귀 주소, 사용하던 지역 변수 등의 자료를 모아 활성 레코드를 준비. 이를 시스템 스택에 저장. B의 코드 시작 위치로 이동하여 처리를 시작(B가 자기자신, 즉 A라면 A의 시작위치로 이동) 호출된 함수 B가 끝나면 스택에서 복귀주소를 꺼내 자신을 호출한 함수 A로 되돌아간다. 순환호출이 중첩될수록 스택에 활성 레코드들이 쌓인다. 함수호출마다 새로운 지역변수를 만들 수 있기에.. 2021. 12. 29.
[자료구조] [6] 리스트 리스트 리스트의 항목들은 순서 또는 위치를 가진다. 리스트도 앞서 공부한 스택,큐,덱 과 같이 항목들이 일렬로 순서대로 들어있는 선형 자료구조. - 스택,큐,덱 과 리스트의 차이? 스택이나 큐에서 자료의 접근은 전단(front)과 후단(rear)로 제한. -> 즉 새로운 항목을 중간에 삽입 / 중간에 있는 항목 삭제 허용하지 않음 리스트는 임의의 위치에 있는 항목에 대한 연산을 허용. 임의의 위치에서도 요소의 삽입/삭제 가능. -> 선형 자료구조들 중에서 가장 활용이 자유롭다. - "연결 리스트"와 "리스트" 용어의 차이 리스트 : 특정한 자료구조. 스택,큐에 대응되는 용어 연결 리스트 : 어떤 자료구조를 구현하는 "프로그래밍 기법". 배열에 대응되는 용어 - 리스트의 연산 & 추상자료형 insert(p.. 2021. 12. 9.
반응형

티스토리툴바