반응형 자료구조23 [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 List를 구현하는 방법에는 순차 리스트(배열), 연결 리스트 존재한다. ※ 관련 연산: 삽입(insert), 접근(access) 및 탐색(search), 삭제(delete) 각각의 구현방식마다 장/단점이 존재하며, 주어진 상황에 따라 적합한 방식을 선택해야 한다. ex) PS와 같이 제한조건이 명시되어 있다면 정적할당 방식이 유리 순차 리스트 (정적 배열) - 배열로 구현되어 있기 때문에 순차 및 임의 접근 (random access)이 가능하다. - 크기가 고정 : 공간이 낭비되거나 재할당(reallocation)이 필요할 수 있다 - 배열의 중간에 데이터를 삽입 및 삭제하는 경우 다수의 원소를 이동하므로 이로 인한 오버헤드가 크다 → 시간 복.. 2021. 5. 2. [스택] Stack (동적할당, 연결리스트 구현) Stack (동적할당, 연결리스트 구현) [스택] Stack 이란? 에서 배열(정적할당 방식)로 Stack을 구현하였다. 동적할당 방식은 초기에 메모리 공간을 정해두지 않고, 필요할 때마다 할당하는 방식이다. - 데이터 삽입, 삭제하는 경우 O(1)에 가능하다. - (최대 메모리 공간 내에서) 리스트 크기 제한이 없다. - 인덱스를 통한 임의 접근(random access)이 어렵다 따라서 특정한 원소를 탐색하는 경우 최대 O(N) 의 시간이 필요할 수 있다 - 일반적으로 자기 참조 구조체를 이용하여 구현한다. ▶ 자세한 내용 [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 참고 [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 순차 리스트(정적 배열) & 연결 .. 2021. 5. 2. [해시] Hash Open Address 기법 구현 [해시] Hash란?에 작성한 Hash를 구현하는 방식 중 하나인 체이닝(Chaining) 기법을 구현하였습니다. Hash 개념이 필요하신 분은 먼저 [해시] Hash란?을 참고해주세요 Open Address 기법 Hash Function이나 주어지는 Input Data에 따라 key간 Hash Index 충돌이 일어날 수 있다. 아래 그림과 같이 ▶ Hash Function = key mod 11 일 때, data = {8, 19, 30}은 동일한 Hash Index = "8" 을 가진다. - 동일한 Hash Index를 가질 때, Hash Table의 비어있는 곳을 찾아서 해결할 수 있다. - Chaining 기법과 달리 추가 메모리 할당이 없다. (Input Data 개수는 초기 Hash Table.. 2021. 5. 1. [해시] Hash Chaining 기법 구현 [해시] Hash란?에 작성한 Hash를 구현하는 방식 중 하나인 체이닝(Chaining) 기법을 구현하였습니다. Hash 개념이 필요하신 분은 먼저 [해시] Hash란?을 참고해주세요 Chaining 기법 Hash Function이나 주어지는 Input Data에 따라 key간 Hash Index 충돌이 일어날 수 있다. 아래 그림과 같이 ▶ Hash Function = key mod 11 일 때, data = {8, 19, 30}은 동일한 Hash Index = "8" 을 가진다. - 동일한 Hash Index를 가질 때, 연결리스트(Linked List)를 구현해서 처리할 수 있다. - Hash Index마다 연결리스트를 지닌 형태 Hash Index가 연결리스트에서 Header 역할을 한다고 보면.. 2021. 5. 1. [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것과 같은 작업은 지원하지 않는다.) ※ Java의 HashMap / C++의 map / Python의 dictionary로 보다 쉽게 이용할 수 있다. 해싱(Hashing) 과정 - 해싱(Hashing) 매핑하는 전체 과정 - 키(key) 매핑 전 원래 데이터의 값 - 해시함수(hash function) 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑 - 해시 값(hash value) 매핑 후 데이터의 값 (Hash Code라고도 부름) Hash 성능과 필요성 - H.. 2021. 4. 30. [큐] 원형 큐 (Circular Queue) 원형 큐 (Circular Queue) 기본적인 Queue 구조는 push와 pop을 반복하다보면 Index (Rear)는 오른쪽으로 이동하게 된다. ▶ [큐] Queue란? [큐] Queue란? Queue란? 선입선출(First In First Out, FIFO)의 자료 구조 ▶ 큐(Queue)는 한쪽에서 삽입(Push, Enqueue) 하며, 다른 한쪽에서 빠져나오는(Pop, Dequeue) 구조 두 지점을 와 로 표현한다. (Front, Rear) ▶ C++.. zoosso.tistory.com 그러다보면 Queue 배열 크기에 제한될 수 밖에 없다. 이를 위해 Queue Index가 순환하는 구조인 원형 큐가 존재한다. → 앞에 비어있는 공간을 재활용하는 구조로 들어오는 Input Data가 적절.. 2021. 4. 24. [큐] Queue란? Queue란? 선입선출(First In First Out, FIFO)의 자료 구조 ▶ 큐(Queue)는 한쪽에서 삽입(Push, Enqueue) 하며, 다른 한쪽에서 빠져나오는(Pop, Dequeue) 구조 두 지점을 와 로 표현한다. (Front, Rear) ▶ C++ STL로 구현한 Queue [C++] [STL] Queue Queue 기본 연산 - FIFO 구조 (First In First Out) - push(element) : 큐 (뒤에) 원소 추가 - pop() : 큐에 (앞쪽에) 있는 원소 삭제 - front() : 큐 제일 앞에 있는 원소 반환 - back() : 큐 제일 뒤에 있는.. zoosso.tistory.com 예제 - 티켓 구매를 위해서 대기표를 뽑아서 번호순 대로 처리 - 대중.. 2021. 4. 23. [스택] Stack 이란? Stack 이란? 스택 (Stack) 특징을 가장 잘 나타내는 표현은 후입선출(Last In First Out, LIFO) 이다. ▶ 스택(Stack)은 삽입(push)과 삭제(pop)이 한쪽 끝에서만 일어나는 구조 가장 상단에 위치한 원소를 가리키는 용어로 "top" 이라고 사용하기도 한다. 예제 - 재귀(Recursive) 함수 - 상자에 물건을 놓으면 맨 밑부터 쌓고, 위에서 부터 차례대로 꺼내는 형태이다. - 웹 서핑에 있어서 뒤로가기를 하면 가장 최근에 방문한 페이지부터 보여준다. - 역순 문자열 만들기 - 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) ex) 올바른 괄호 문자열 (VPS, Valid Parenthesis String) - 후위 표기법 Stack 구현은 "자료구조".. 2021. 4. 22. 우선순위 큐 (Priority Queue) 우선순위 큐 큐는 선입선출(First In First Out) 자료구조이지만 우선순위 큐는 들어온 순서가 아닌 정의된 우선순위에 따라 먼저 처리되는 구조이다. ex) 수행할 작업이 여러개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행 ※ 여러 자료구조들로 구현할 수 있으나 heap 특성과 많이 닮아 heap으로 구현하는 경우가 많다. ex) 연결 리스트나 배열에 원소들을 집어넣고, 원소를 꺼낼 때마다 모든 원소를 순회하며 우선순위가 가장 높은 원소를 찾는 방법 ▶ [그래프] 힙(Heap) 자료구조란? ▶ [큐] Queue란? ▶ [STL] Priority_queue 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료.. 2021. 3. 21. 힙(Heap) 시뮬레이션 ※ [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 배열 인덱스를 통해 쉽게 부모-자식 노드를 알 수 있습니다. if) 시작 인덱스를 1로 두면 다음과 같이 parent와 child 노드 번호 관계식을 갖습니다. → k의 left child 번호 → k × 2 → k의 right child 번호 → k × 2 + 1 → k의 parent 번호 → k / 2 시뮬레이션 (최대 Heap 구성) 부모 노드 < 자식 노드인 관계가 존재하므로 원소 위치를 바꾸어야 합.. 2021. 2. 27. 이전 1 2 3 다음 반응형
