자료구조5 [자료구조] 힙 (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. [자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘 스택이란 스택은 우물과도 같습니다. 가장 마지막에 들어간 데이터가 맨위에 쌓이게 되고, 데이터를 가져올 때 맨 위에 쌓인 (즉, 가장 마지막에 들어간) 데이터를 먼저 빼내야 합니다. 스택 기능 스택에는 자주 사용되는 5가지 메소드 (method)가 존재합니다. push(data) 스택에 데이터를 넣습니다. 들어간 데이터는 스택의 맨 위 (top)에 위치합니다. top() 스택의 맨 위에 위치한 데이터에 접근합니다. 만약 스택이 비어있는 경우 런타임 에러를 발생시킵니다. pop() 스택의 맨 위에 위치한 데이터를 빼냅니다. top과 마찬가지로 스택이 빈 경우 런타임 에러를 발생시킵니다. size() 스택에 현재 저장되어있는 데이터의 개수를 반환합니다. empty() 스택이 비어있는지 확인합니다. 비어있다면.. 2020. 10. 30. 이전 1 2 다음
