728x90 반응형 Baekjoon181 [자료구조] 04 우선순위 큐, 힙 ▶ 우선순위 큐 (Priority Queue) : 산입 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. : ex) 응급상황 ▶ 배열 기반 우선순위 큐 (단점) : 데이터 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다. : 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다. ▶ 연결 리스트 기반 우선순위 큐 (단점) : 삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 시작해서 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있다. ▶힙 (Heap)을 이용하는 우선순위 큐 구현 : 위와 같은 단점들로 인해 힙을 이용한다 ▶ 힙 (Heap) : '이진 트리'이되 '완전 이진 트리'이다.. 2021. 3. 15. [자료구조] 03 트리 ▶ 트리 (Tree) : 계층적 관계를 표현하는 자료구조 ▶ 용어 노드 (Node) 트리의 구성요소 간선 (Edge) 노드와 노드를 연결하는 연결선 루트 노드 (Root Node) 트리 구조에서 최상위에 존재하는 노드 단말 노드 (Terminal Node) 아래로 또는 다른 노드가 연결되어 있지 않는 노드 내부 노드 (Internal Node) 단말 노드를 제외한 모든 노드 부모 노드 (Parent Node) 특정 노드의 상위 노드 자식 노드 (Child Node) 특정 노드의 하위 노드 형제 노드 (Sibling Node) 같은 부모 노드를 둔 노드 조상 노드 (Ancestor) 특정 노드 기준 위로 모든 노드 후손 노드 (Descendant) 특정 노드 기준 아래로 모든 노드 레벨 (Level) 트리.. 2021. 3. 15. [자료구조] 02 스택, 큐 ▶ 스택 (Stack) : LIFO (후입선출) 구조의 자료구조 : ex) 접시 쌓기 ▶ push : 삽입 (마지막 요소 위에) pop : 삭제 (마지막 요소를) ▶ 구현 종류 배열 기반 스택 / (단순) 연결 리스트 기반 스택 ▶ 구현할 만한 예시 : 계산기 (중위 표기법 → 후위 표기법) 전위 표기법 + 5 / 2 7 중위 표기법 5 + 2 / 7 후위 표기법 5 2 7 / + ▶ 큐 (Queue) : FIFO (선입선출) 구조의 자료구조 : ex) 선착순 줄 서기 ▶ enqueue : 큐에 데이터를 삽입 연산 dequeue : 큐에서 데이터를 꺼내는 연산 ▶ 배열 기반 큐 : 원형 큐 (Circular Queue) : 배열의 끝에 도달하면 처음으로 순환할 수 있게 논리적 원형으로 구현한 큐 : 하지.. 2021. 3. 15. [자료구조] 01 자료구조와 알고리즘 이해 정리 ▶ 선형구조 비선형구조 리스트 트리 스택 그래프 큐 단순구조 파일구조 정수 순차파일 실수 색인파일 문자 직접파일 문자열 ▶성능분석 방법 기준1. 시간 복잡도 : 속도 기준2. 공간 복잡도 : 메모리의 사용량 -> 검증이 끝난 알고리즘의 적용을 고려하는 경우 : 속도 기준 -> 특정 알고리즘에 대해서 상대적인 우월성을 입증해야 하는 경우 : 메모리의 사용량 기준 ▶ 데이터의 수 n에 대한 연산횟수의 함수 (T(n) = 핵심연산 횟수) ▶ 순차 탐색(Linear Search) : O( n ) : 탐색할 대상을 순서대로 하나씩 핵심연산으로 탐색한다. 이진 탐색(Binary Search) : O( log n ) : 탐색할 대상을 반으로 줄여가면서 핵심연산으로 탐색한다. (가정이 필요하다 예 : 데이터가 정렬되어.. 2021. 3. 15. 이전 1 ··· 39 40 41 42 43 44 45 46 다음 728x90 반응형
