728x90 반응형 BASE/Structure17 자료구조 - 배열(Array) 1. 배열이란? 배열(Array)은 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조로 연속된 메모리 공간에 순차적으로 저장한다. 배열의 크기는 고정되어 있고, 선언할 때 크기를 정하고 후에 변경할 수는 없다. 2. 시간 복잡도 1) 삽입 / 삭제 - 배열의 맨 앞에 삽입 / 삭제하는 경우 : O(n) - 배열의 맨 뒤에 삽입 / 삭제하는 경우 : O(1) - 배열의 중간에 삽입 / 삭제하는 경우 : O(n) 2) 탐색 - O(n) 3. 장단점 1) 장점 - 인덱스를 가지고 있어 바로 접근 가능하다. (자료의 크기가 클수록 매우 유리) - 연속된 메모리 공간에 존재하기 때문에 관리가 편리하다. - 구조가 간단하여 프로그램 작성이 쉽다. 2) 단점 - 데이터 삽입 / 삭제가 어렵다... 2021. 1. 26. 자료구조 - 해싱(Hashing) 1. 해싱이란? 해시(Hash)란 데이터를 다루는 기법 중 하나이며, 해시 함수(Hash function)는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑 전 원래 데이터의 값을 Key, 매핑 후 데이터의 값을 Hash Value 또는 해시 코드라고 하며 키와 값으로 매핑되는 과정 자체를 해싱이라고 한다. 탐색, 삽입, 삭제 연산 모두 해시 함수를 거치는 시간만 소요되기 때문에 일반적으로 O(1)의 시간복잡도를 가진다. 2. 해시 테이블이란? 해시 테이블(Hash table)은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. Hash table은 Hash 함수를 사용하여 색인(index, Key)을 버킷(bucke.. 2021. 1. 8. 자료구조 - 우선 순위 큐(Priority Queue) 1. 우선순위 큐란? 우선순위 큐(Priority Queue)는 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료구조이다. 큐는 선형 자료구조이고, 우선순위 큐는 비 선형 자료구조이다. 우선순위 큐는 자료가 들어온 순서와 상관 없이 미리 정한 우선순위대로 나간다. 주로 정의된 우선 순위를 heap condition으로 가지는 heap을 이용해 구현된다. 그 이유는 시간 복잡도와 관련이 있는데, 배열 기반 데이터 삽입의 시간 복잡도는 O(n) 이고 배열 기반 데이터 삭제의 시간 복잡도는 O(1)이다. 또 연결 리스트 기반 데이터 삽입과 삭제의 시간 복잡도도 위와 같다. 하지만 힙 기반 데이터 삽입과 삭제의 시간 복잡도는 각각 O(logn)이다. 따라서 힙을 먼저 공부해야 한다... 2021. 1. 7. 자료구조 - 큐 (Queue) 1. 큐란? 큐(Queue)는 데이터를 일시적으로 쌓아두기 위한 자료구조로, 먼저 들어온 데이터가 가장 먼저 나가는 First In First Out인 구조를 말한다. 위 Reference Code처럼 배열로 큐를 구현해도 되지만, 표준 라이브러리에 정의되어 있기 때문에 include하여 사용하면 편리하다. enqueue란 큐 맨 뒤에 데이터를 추가하는 것을 의미하며 dequeue란 큐 맨 앞쪽의 데이터를 삭제하는 것을 의미한다. 데이터가 삽입되는 곳을 front, 제거되는 곳을 back이라고 한다. 선언 queue 큐 이름; 형태로 선언한다. #include queue s1; queue s2; queue s3; 기본 메소드 1. push() : 큐 맨 뒤에 데이터 추가 = enequeue 2. pop(.. 2021. 1. 6. 자료구조 - 스택 (Stack) 1. 스택이란? Stack의 사전적 정의는 '쌓다', '더미'로 나중에 들어간 것이 먼저 나오는 Last In First Out 형태이다. 아래 Reference Code처럼 배열로 스택을 구현해도 되지만, 표준 라이브러리에 정의되어 있기 때문에 include하여 사용하면 편리하다. 맨 위 요소는 top이라고 하며, 이 요소만 접근할 수 있다. 자료가 없을 때 pop을 하는 오류를 stack underflow, 스택의 크기 이상의 자료를 push하려고 할 때의 오류를 stack overflow라고 한다. 선언 stack 스택 이름; 형태로 선언한다. #include stack s1; stack s2; stack s3; 기본 메소드 1. push() : 현재 스택 최상위에 데이터 추가 2. pop() : .. 2021. 1. 6. 이전 1 2 3 다음 728x90 반응형