CS/DataStructure (2) 썸네일형 리스트형 [DataStructure] Heap 이란? heap은 우선 순위 큐를 위해 만들어진 자료구조로서 완전이진트리를 기반으로 하고 있다. 우선 순위 큐는 우선순위를 가진 큐로서 입력 순서에 따라 출력되는 기존의 큐와 다르게 입력 순서가 늦어도 우선순위가 높으면 먼저 출력되는 큐를 의미합니다. 이 우선 순위 큐는 배열, 리스트 ,heap으로 구현이 가능한데 여기서 heap으로 구현하는것이 제일 효율적이다. 그 이유는 heap의 삽입,삭제 연산의 시간 복잡도가 모두 log n 이기 때문입니다. heap은 배열로 구현이 가능합니다. heap의 삽입 : 맨마지막에 삽입 후 heap을 만드는 과정 (log n)으로 끝 -> heap 만드는 과정 : 인덱스/2 를 한 값과 비교해가면서 (부모보다 크다, 부모모다 작다 등의 조건 만족할 때 까지 반복) heap의 .. [DataStructure] Stack vs Queue Stack 데이터의 입력과 출력이 한곳에서만 이루어지고, 마지막에 들어간 것이 제일 먼저 나오는 Last In First Out 구조를 가진 자료구조입니다. 스택에서 사용하는 연산은 아래와 같습니다. 스택의 최상위에 데이터를 추가하는 연산인 push() 스택의 최상위에 있는 데이터를 빼는 pop() 스택의 최상위에 있는 데이터 값을 하는 peek() 스택이 비어있는지 확인하는 isEmpty() 스택의 사용 예시는 다음과 같습니다. 함수의 콜 스택 Ctrl + z(실행취소) undo 웹 브라우저의 뒤로가기 후위 표기법 계산등에 이용할 수 있습니다. Queue 먼저 넣은 데이터가 먼저나오는 First In First Out 구조를 가진 자료구조입니다. 큐에서 사용하는 연산은 아래와 같습니다. 큐의 끝 부분에.. 이전 1 다음