728x90 자료구조5 [백준] 11279번 최대 힙 문제 풀이/히프(Heap)(2) https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 히프 자료구조에 대한 설명글은 다음과 같습니다. >>이전 글 : https://nomadsjh.tistory.com/41 비선형 자료구조 - 히프(Heap)와 삽입 및 삭제 연산 히프(Heap)란? 히프는 완전 이진트리의 한 종류입니다. 이때 완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 n.. 2023. 10. 24. 비선형 자료구조 - 히프(Heap)와 삽입 및 삭제 연산 히프(Heap)란? 히프는 완전 이진트리의 한 종류입니다. 이때 완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 구조를 말합니다. 히프는 모든 부모 노드가 그 자식 노드의 값보다 더 큰(혹은 작은) 값을 가지는 구조로 여러 값들 중 최댓값이나 최솟값을 빠르게 찾을 수 있도록 만들어졌습니다. 이러한 히프는 최대 히프와 최소 히프로 나뉩니다. 여기서 최대 히프냐 최소 히프냐에 따라 루트 노드만 탐색하면 최댓값 혹은 최솟값을 O(1)의 시간복잡도로 얻어낼 수 있습니다. 또한, 이 히프 구조는 우선순위 큐를 구현할 때 많이 사용되기도 합니다. 최대 히프 최대 히프란 부모 노드가 항상 자식 노드보다 크거나 같은 구조를 말합니다. 이.. 2023. 10. 19. [자료구조] 덱(Deque) - 코딩기록 덱 덱은 앞서 포스팅에서 올렸던 스택과 큐를 합친 버전이라고 할 수 있다. 스택이나 큐는 한쪽에서만 삽입과 삭제가 가능했다면 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하게 만든 큐이다. 터널과 비슷하다고 할 수 있다. 덱은 스택이나 큐처럼 사용할 수 있기 때문에 활용도가 높은 자료구조이다. 덱의 기능 이제 덱STL을 활용해 기능들을 살펴보겠다. push_front(x) : 덱의 앞에 x를 추가 push_back(x) : 덱의 뒤에 x를 추가 pop_front() : 덱의 원소 중 맨 앞 원소를 삭제 pop_back() : 덱의 원소 중 맨 뒤 원소를 삭제 front() : 덱의 맨 앞 원소를 반환 back() : 덱의 맨 뒤 원소를 반환 empty() : 덱이 비어있으면 1(true), 비어있지 않으면 .. 2023. 5. 5. [자료구조] 큐(Queue) - 코딩기록 큐(Queue) 큐는 이전 포스팅에서 설명했던 스택과 약간 다른 점이 있는 자료구조이다. 이전에 설명했던 스택은 LIFO(후입선출)구조였지만 큐는 FIFO(First - In - First - Out) 선입선출 구조이다. 즉, 먼저 집어 넣은 데이터가 먼저 나오는 것이다. 1번, 2번, 3번 데이터가 차례로 들어오고 이 순서대로 나간다고 생각하면 된다. 맨 오른쪽에 있는 화살표에 해당하는 구간이 삽입연산이 수행되는 곳인 리어(rear)이고 맨 왼쪽에 있는 화살표에 해당하는 구간이 삭제연산이 수행되는 곳인 프론트(front)이다. 큐의 기능 이제 큐STL을 활용해 큐의 기능들을 살펴보겠다. push(x) : 원소 x를 큐의 맨 뒤에 추가 pop() : 큐의 맨 앞 원소 삭제 empty() : 큐가 비어있으.. 2023. 5. 4. [자료구조] 스택(Stack) - 코딩기록 자료구조 자료구조에 대해 간단히만 짚고 넘어가겠다. 자료구조의 정의는 컴퓨터과학에서 효율적인 접근과 수정을 가능하게 해주는 자료의 조직, 관리, 저장을 의미한다. 자료구조를 통해 데이터를 효율적으로 저장, 관리할 수 있고 메모리를 절약하거나 시간을 단축할 수 있다. 우리가 흔히 말하는 알고리즘과는 약간의 차이가 있다. 자료구조는 이름처럼 데이터를 저장하기 위한 구조이고 알고리즘은 자료구조에 있는 데이터를 활용해 문제를 해결하는 방법이라고 할 수 있다. 즉, 자료구조를 잘 익혀두면 문제를 더 효율적으로 해결할 수 있을 것이다. 이 포스팅에서 다룰 것은 자료구조에서 선형구조 중 하나인 스택이다. 스택 스택은 '쌓다'라는 뜻을 가지고 있다. 이 말처럼 스택을 이해할 때 탑을 상상하면 편하다. 다음과 같은 탑이.. 2023. 5. 3. 이전 1 다음 728x90
