목록공부기록/알고리즘 (3)

iamjooon2님의 블로그

[자료구조] 우선순위 큐(Priority Que, Heap)

우선순위 큐 큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조이나, 우선순위 큐는 먼저 들어오는 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나간다. 또한, 내부적으로 이진 트리(Binary Tree) 형태의 힙(Heap)이라는 형태로 돌아가게 된다 그림을 보면 우선순위 큐를 이진 트리가 있고, 가장 최상단의 root node가 모든 노드를 통틀어 가장 큰 값을 가지고 있다는 것을 알 수 있다. 이와 같이 루트 노드에 큰 값이 들어가있으면 max-heap으로, 루트 노드에 가장 작은 값이 들어가 있으면 min-heap이라 한다 각 트리의 노드에 번호를 붙이고, 이 번호를 배열의 인덱스로 생각하면 효과적으로 힙을 구현할 수 있다 삽입/삭제를 한 번 할때 시간 복잡도는 O(logN)을 가지..
공부기록/알고리즘 2022. 7. 6. 16:17
[자료구조] 스택(Stack), 큐(Queue)

스택 삽입/삭제시 시간복잡도는 O(1) 선입후출의 성질을 갖고 있다 -> FILO : First Input Last Out(선입후출) 맨 처음 들어온 데이터가 가장 마지막에 나오게 되는 추상 데이터타입이다 과자 프링글스를 생각하면 딱이다 브라우저의 뒤로가기 기능 등에 사용된다 구현 스택에 데이터를 집어넣을 때는 push 스택에서 데이터를 추출할 때는 pop을 사용한다 코드 // C++ stack s; s.push(123); s.push(456); s.push(789); printf("size: %d\n", s.size()); while (!s.empty()) { printf("%d\n", s.top()); s.pop(); } # python s = [] s.append(123) s.append(456) ..
공부기록/알고리즘 2022. 7. 2. 23:19
[자료구조] 배열(Array), 연결리스트(Linked List)

배열 가장 기본적인 자료구조이다 삽입 / 삭제의 시간복잡도 : O(N) 탐색 시간복잡도 : O(1) C++에서는 size 변경이 불가하며, python은 리스트를 사용하여 구현한다 // C++ int arr[4] = {10, 11, 12, 13}; arr[2] = 5; # python arr = [10, 11, 12, 13] arr[2] = 5 배열을 생성할 땐, 메모리에 연속된 공간이 생긴다. 탐색시, 임의접근(random access)하기 때문에 탐색속도가 빠르다 O(1) 삽입시 해당하는 위치 뒤에 있는 친구들을 하나씩 다 밀어줘야 하고 삭제시 해당하는 위치 뒤에 있는 친구들을 하나씩 다 땡겨줘야 하기 때문에 시간복잡도는 O(N)이 된다 삽입/삭제를 많이 하는 경우에는 배열이 불리하고, 탐색을 많이 ..
공부기록/알고리즘 2022. 7. 1. 18:40
이전 Prev 1 Next 다음