Computer Science/자료구조 (3) 썸네일형 리스트형 [자료구조] Heap이란? 오늘은 Heap 이라는 자료구조에 대해 알아보자 Heap이란? 힙이란 완전 이진트리의 일종으로 반정렬 상태에 있다! 우선순위가 높은 노드가 위쪽에 있는 형태이고 이를 통해 최대값과 최소값을 빠르게 찾아낼 수 있도록 설계된 구조이다 그러면 Heap은 어디에 쓰이는가? 바로 우선순위 큐를 구현할 때 쓰인다. 사실상 힙이라는 구조는 우선순위 큐를 위해 존재한다고 봐도 무방하다! 우선순위 큐 구현에도 여러가지 방법(Array,LinkedList,Heap)이 존재하는데 Heap으로 구현하는 것이 가장 효율적이기 때문에 보통 우선순위큐는 heap으로 구현되어있다. 힙은 어떤 종류가 있을까? 힙은 최대힙과 최소힙 두가지 종류가 있다. 그림으로 보면 왼쪽이 최대힙으로 큰 값이 우선순위가 높아 제일 위에 있다. 오른쪽은.. [자료구조] Stack과 Queue 오늘은 선형 자료구조인 Stack과 Queue에 대해 알아보자 Stack 이란? 입력과 출력이 한 곳으로만 이루어지는 자료구조의 형태이다. LIFO정책을 따르고 있다.(Last In First Out) 따라서 나중에 들어온 것이 먼저 나간다. 뷔페의 접시가 쌓여있는 것을 생각하면 쉽다!! 그렇다면 Stack은 언제 사용될까? 1. 함수의 콜스택에 사용된다. 2. 문자열을 역순 출력할때에도 하나하나씩 넣고 빼면 역순으로 출력된다. 3. 후위 표기법을 연산할때 ex) 234*+ = 14 5. 브라우저 방문기록 6. 실행 취소(undo) Stack은 배열과 달리 index로 접근할 수 없다. 또한 삽입과 삭제는 O(1)의 시간 복잡도 이다.(값을 넣고 빼기만 하면 되므로) 하지만 탐색시에는 O(n)이 걸린다... [자료구조] Array와 List CS스터디를 시작하면서 한동안 못썼던 블로그를 자주 써볼려고 합니다!! 예전 개발자들이 개발을 시작하면서 데이터를 다룰때 하나의 데이터만 다루는 것은 아니겠죠? 여러가지 데이터가 모인 집합을 형성하게 되는데 먼저 Array라는 녀석부터 살펴봅시다. Array란? 순차적으로 데이터를 저장하는 형태로 물리적주소도 순차적으로 저장된다.(크기를 미리 지정해줘야 한다.) index라는 것이 존재해 빠르게 값을 찾아낼때 유용하다.(원하는 데이터 한번에 접근가능O(1)) 하지만 삽입과 삭제에는 취약하다. (해당 위치에 접근하고O(1), shift O(n)해주는 작업까지 걸려 O(n)이 걸린다.) 예를 들어 중간녀석을 삭제하려면 배열의 연속성이 깨져 이후 뒤에것들을 모두 앞으로 땡겨줘야 한다. 그렇다면 어떻게 저런 시.. 이전 1 다음
