CS/자료구조 (4) 썸네일형 리스트형 Hash 가능한 한 빨리 데이터를 저장하고 검색하기 위해 Hash라는 자료구조를 많이 활용한다. 해시 테이블은 데이터를 저장하는 테이블로 Key와 Value가 한 쌍으로 존재한다. Key 값은 해시 테이블에서 인덱스로 사용되며, 데이터를 찾기 위해 해시 함수를 거쳐 키 값을 얻고 검색하는 데 평균적으로 O(1)의 시간 복잡도가 걸린다. Hash에 대해 알아보자 Hash Hash Function 해시 함수는 임의의 길이를 갖는 데이터를 고정된 길이의 키 값(인덱스 값)으로 변환하여 해시 테이블에 저장하는 기능을 한다. 그림의 우측 테이블은 해시 테이블로, Index는 해시 함수를 통해 생성된 키 값으로 해시 테이블에 저장될 공간을 의미하고 Data는 hash 값, Value라고도 하며 입력받은 데이터를 저장한다. .. 우선순위 큐 Priority Queue 큐(Queue)는 우선순위와 상관없이 먼저 들어간 데이터가 먼저 나오는 FIFO 방식의 자료구조이다. 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 우선적으로 나오는 자료구조이다. 그렇다면 우선순위 큐는 어떻게 구현할 수 있을까? 1. 배열로 우선순위 큐 구현하기 우선순위대로 데이터들이 들어온다고 가정했을 때, 우선순위대로 앞의 인덱스부터 채워나가면 되기 때문에 문제가 되지 않는다.(데이터가 모두 들어오고 난 뒤에는 정렬된 상태) 하지만 연속적인 우선 순위 데이터의 입력이 보장되지 않을 경우에는 우선 순위에 맞춰 데이터를 이동시켜야 한다. 이렇게 할 경우 처음 인덱스부터 우선순위를 비교해야 하기 때문에 데이터 삽입의 최악의 시간 복잡도는 O(n)이 걸리게 된다. Enqueue : O(n).. 스택과 큐 스택과 큐는 선형의 자료구조로 순서를 가지고 있고, 메모리에 연속적으로 저장된다. 스택과 큐 모두 배열과 연결리스트로 구현 가능하다. 배열로 구현할 경우 확실한 메모리의 사용크기를 알 수 없어 연결리스트로 구현하는 편이 좀 더 쉽다. STACK 스택의 사전적 의미 "쌓이다" 처럼 데이터들이 차곡차곡 쌓이는 자료구조의 모습이다. LIFO(Last In First Out, 후입선출) 구조로 가장 마지막에 저장된 데이터가 가장 먼저 출력된다. 스택은 한 곳으로만 접근할 수 있으며 이 곳을 탑(또는 SP, 스택포인터)이라고 부른다. 스택의 주요 연산으로는 push(삽입)와 pop(삭제)이 있다.위의 그림에서 최초의 탑은 0번 인덱스를 가리키고 있고 데이터가 들어갈 때마다 탑이 가리키는 포인터는 다음 인덱스의 위.. Array VS Linked List 리스트 : 어떤 순서가 있는 데이터의 집합을 의미한다. Array(배열) 특징 Array는 배열로 연속적인 공간에 순차적으로 데이터를 저장할 수 있는 자료구조이다. 데이터를 입력할 때 인덱스 순서대로 입력이 되고, 메모리의 저장 위치도 인접한 위치에 저장이 된다. 데이터에 접근할 때는 인덱스 번호를 통해 접근하기 때문에 데이터의 양이 얼마나 많든 O(1)의 시간 복잡도로 탐색이 가능하다. 특정 인덱스의 데이터 삽입과 삭제에 있어서는 반드시 기존 데이터들의 이동을 필요로 하기에 O(n)의 시간이 소요된다. 배열을 정적으로 할당한 경우 배열의 크기는 Compile time에 할당되기 때문에 한번 사이즈가 정해지면 변경이 불가능하다. 배열은 메모리의 Stack 영역에 저장된다. 배열을 동적으로 할당한 경우 r.. 이전 1 다음
