CS/자료구조 (7) 썸네일형 리스트형 [자료구조] Graph ※ 2022년 1월 27일에 작성된 글입니다.🖇 Graph연결되어 있는 객체 간의 관계를 표현하는 자료구조Graph의 구조vertices(정점)= node여러 가지 특성을 가질 수 있는 객체 V(G): 그래프 G의 정점들의 집합 edge(간선)= link정점들 간의 관계 E(G): 그래프 G의 간선들의 집합 Graph vs Tree GraphTree방향성방향, 무방향방향순환가능불가능루트 노드루트 노드의 개념이 없음한 개의 루트 노드만 존재부모-자식부모-자식의 개념이 없음부모-자식 관계모델네트워크 모델계층 모델순회DFS, BFSDFS, BFS 안의 Pre-, In-, Post-order간선의 수그래프의 따라 다름노드가 N인 트리는 항상 N-1의 간선을 가짐Graph의 종류무방향 그래프방향 그래프Graph.. [자료구조] Heap ※ 2022년 1월 10일에 작성된 글입니다.🌳 Heap부모 노드의 키가 자식 노드의 키보다 크거나 같은 완전 이진 트리Heap의 종류max heap부모 노드의 키 ≥ 자식 노드의 키min heap부모 노드의 키 ≤ 자식 노드의 키Heap의 높이n개의 노드를 가지고 있는 힙의 높이는 O(log n)마지막 레벨 h 외에는 각 레벨 i에 2i-1개의 노드 존재Heap의 구현 방법배열완전 이진 트리이므로 각 노드에 번호(배열의 인덱스)를 붙일 수 있다.012345678910 9765432213부모 노드와 자식 노드를 찾기가 쉽다.왼쪽 자식의 인덱스 = 부모의 인덱스 * 2오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1부모의 인덱스 = 자식의 인덱스 / 2Heap의 연산upheap삽입downheap삭제u.. [자료구조] Priority Queue ※ 2022년 1월 4일에 작성된 글입니다.🚦 Priority Queue우선순위를 가진 항목들을 저장하는 큐FIFO가 아니라 우선 순위가 높은 데이터가 먼저 나간다.Priority Queue의 연산insert우선순위 큐에 요소를 추가한다.delete우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.find우선순위가 가장 높은 요소를 반환한다.isEmpty우선순위 큐가 비어있는지 확인한다.Priority Queue의 구분최소 우선순위 큐최대 우선순위 큐Priority Queue의 응용 분야시뮬레이션 시스템네트워크 트래픽 제어운영 체제에서의 작업 스케쥴링Priority Queue의 구현 방법배열(array)연결리스트(linked list)힙(heap)구현 방법삽입삭제순서 없는 배열O.. [자료구조] Tree ※ 2022년 1월 2일에 작성된 글입니다.🌲 Tree계층적인 구조를 나타내는 자료구조Tree의 구성노드(node)트리를 구성하고 있는 각각의 요소루트(root)트리에서 최상위에 있는 노드서브트리(subtree)하나의 노드와 그 노드들의 자손들로 이루어진 트리단말 노드(terminal node)하위 노드가 없는 노드비단말 노드(internal node)적어도 하나의 하위 노드를 가지는 노드Tree의 용어레벨(level)트리의 각 층의 번호높이(height)트리의 최대 레벨차수(degree)노드가 가지고 있는 하위 노드의 개수Tree의 응용 분야계층적인 조직 표현파일 시스템인공지능에서의 결정 트리Binary Tree모든 노드가 2개의 서브 트리를 가지고 있는 트리서브 트리는 공집합일 수 있다.이진 트리의.. [자료구조] Queue ※ 2021년 12월 31일에 작성된 글입니다.🚥 Queue먼저 들어온 데이터가 먼저 나가는 자료구조FIFO(First-In First-Out, 선입선출)Queue의 구조0123456789 ABC front rear * front 첫번째 요소 하나 앞의 인덱스 * rear 마지막 요소의 인덱스 Queue의 연산add= enQueue큐의 뒤에 요소를 추가 한다.remove= deQueue큐의 앞에 있는 요소를 반환한 다음 삭제한다.peekisEmptyQueue의 용도버퍼시뮬레이션BFSLinearQueue배열을 선형으로 사용하여 큐를 구현한다.0123456789 ABC ⬇ 0123456789ABC .. [자료구조] Stack ※ 2021년 12월 30일에 작성된 글입니다.📚 Stack쌓아놓은 더미Stack의 특징LIFO(Last-In First-Out, 후입선출)가장 최근에 들어온 데이터가 가장 먼저 나간다.Stack의 구조|||-|| || ||C||B||A|요소(element)A, B, C상단(top)C하단(bottom)AStack의 연산push스택 상단에 요소를 삽입한다.pop스택 상단 요소를 삭제하고 반환한다.empty스택이 비어있는지 확인한다.peek스택 상단 요소를 스택에서 삭제하지 않고 보기만 한다.Stack의 용도입력과 역순의 출력이 필요한 경우에디터에서 실행 취소(undo) 기능함수 호출에서 복귀 주소 기억웹 브라우저 방문 기록(뒤로 가기)수식의 괄호 검사후위 표기식 계산미로 찾기DFS [자료구조] List ※ 2021년 12월 29일에 작성된 글입니다.📋 List순서를 가진 요소들의 모임Array vs List ArrayList물리적 순서와 논리적 순서일치일치하지 않아도 됨크기고정가변메모리 할당정적동적List의 연산add새로운 요소를 리스트의 끝, 처음, 중간에 추가한다.remove기존의 요소를 리스트의 임의의 위치에서 삭제한다.clear모든* 요소를 삭제한다.replace기존의 요소를 대치한다.contains리스트가 특정한 요소를 가지고 있는지 확인한다.get리스트의 특정 위치의 요소를 반환한다.size리스트 안의 요소의 개수를 센다.isEmpty리스트가 비었는지 확인한다.ArrayList= Dynamic Array0123456789ABCDE 1차원 배열에 요소들을 순서대로 저장구현이 간단삽입,.. 이전 1 다음
