자료구조6 [자료구조] 힙 (Heap) C/C++ 구현 - 알고리즘 // 최소 힙, 최대 힙 요즘 heap (min heap, max heap) 관련 과제 요청이 많이 들어와서 힙 자료구조에 대해 글을 써봅니다. 힙은 이진트리 (Binary Tree)로 구성할 수 있으며 트리 구조체로 구현하거나 또는 1차원 배열로 쉽게 구현할 수 있습니다. 구현 시 하나의 규칙만 지켜주면 되는데 최소 힙은(min heap) 부모가 자식보다 값이 작아야 하며 최대 힙은 (max heap) 그 반대입니다. 이진트리의 형태를 띄고있어 루트 노드를 1번 정점이라고 한다면, 자식 노드는 각각 2, 3 번 노드가 됩니다. 여기서 알 수 있는건 부모 정점의 번호가 n이라면 왼쪽 자식의 번호는 2*n, 오른쪽 자식의 번호는 2*n + 1 의 규칙을 띄고있습니다. 노드 번호를 배열의 인덱스로 한다면 아래와 같이 1차원 배열로 .. 2021. 6. 3. [자료구조] 이중 연결 리스트 (Double Linked List) C/C++ 구현 - 알고리즘 2020/10/30 - [자료구조] - [자료구조] 연결 리스트 (Linked List) C/C++ 구현 - 알고리즘 [자료구조] 연결 리스트 (Linked List) C/C++ 구현 - 알고리즘 2020/10/30 - [자료구조] - [자료구조] 큐 (Queue) C/C++ 구현 - 알고리즘 2020/10/30 - [자료구조] - [자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘 연결리스트란 연결리스트는 기차와 같습니다. 연결리스트는.. seongjuk.tistory.com 이전에는 단방향 연결리스트에 대한 구현하는 방법을 소개했습니다. (다음 노드의 위치만 저장하고 있었죠) 이중연결리스트란 이중 연결 리스트는 연결이 양방향으로 내 앞, 뒤의 노드 위치를 저장하고 있습니다. 아래 그림의 형태.. 2020. 10. 30. [자료구조] 연결 리스트 (Linked List) C/C++ 구현 - 알고리즘 2020/10/30 - [자료구조] - [자료구조] 큐 (Queue) C/C++ 구현 - 알고리즘 2020/10/30 - [자료구조] - [자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘 연결리스트란 연결리스트는 기차와 같습니다. 연결리스트는 동적으로 크기를 조절하므로 배열을 사용하는것 보다 메모리를 효율적으로 사용할 수 있다는 것이 장점입니다. 연결리스트는 다음 노드에 해당하는 현재 노드를 기준으로 왼쪽 노드, 오른쪽 노드의 연결로 구성됩니다. 편의상 왼쪽에 존재하는 노드가 더 앞선 순서를 갖는다고 가정하겠습니다. 단방향 연결리스트의 경우 다음 노드를 의미하는 next와 마지막 노드를 가리키는 last, 저장할 data 최소 세가지의 요소로 구성됩니다. (마지막 노드를 가리키는 요소를 가지고.. 2020. 10. 30. [자료구조] 큐 (Queue) C/C++ 구현 - 알고리즘 저번 글은 스택 구현에 대해 알아봤습니다. 2020/10/30 - [알고리즘] - [자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘 [자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘 스택이란 스택은 우물과도 같습니다. 가장 마지막에 들어간 데이터가 맨위에 쌓이게 되고, 데이터를 가져올 때 맨 위에 쌓인 (즉, 가장 마지막에 들어간) 데이터를 먼저 빼내야 합니다. 스택 기 seongjuk.tistory.com 큐란 큐는 톨게이트 (고속도로 요금 정산소)와 같습니다. 각 게이트에 먼저 도착한 차가 요금을 정산하고 먼저나가는 것과 같이, 먼저 들어온 데이터가 먼저 큐에서 빠져나가게 됩니다. 큐 기능 큐에는 자주 사용되는 6가지 메소드 (method)가 존재합니다. push(data) 스택.. 2020. 10. 30. 이전 1 2 다음
