[과제] 설명 준비해오기1

알고스터디

배열 vs 연결리스트

스택 vs 큐
힙

 

남팀

1. 배열 과 연결리스트의 개념과 차이점
2. 자바관련질문
3. 네트워크 1.5강의(보고 정리한 내용

 

 

1.배열과 연결리스트이 개념과 차이점 

배열:

-배열이란 특정 자료형(Data Type)들이 메모리 공간상에서 연속적으로 이루어져 있는 자료구조를 의미함

-0(1)의 시간복잡도를 가짐  

-단점: 배열의 크기를 변경할 수 없다. 

-N개의 데이터를 추가한다면, O(N^2)의 시간복잡도

**데이터의 접근(검색과 정렬)은 빠르지만, 메모리 공간활용에 제약이 있으며 데이터의 추가와 삭제가 비효율 적이다

 

연결리스트:

-연결리스트란 여러개의 노드(Node)들이 연결된 형태의 자료구조 

-메모리 공간상에서 각 노드들이 연속적으로 이루어져 있지 않고 흩어져, 각각의 노드가 자신의 다음 노드 위치를 알고 있는 형태로 구현됨

-노드(Node)? 배열에서의 한칸과 같다고 생각할 수 있고, 각각의 노드들은 내부적으로 자신 안에 포함할 데이터(Data)와 다음 노드의 위치정보(Link)를 갖고 있다. 

 

-이중연결리스트(Doubly Linked List): 노드가 자신의 다음 노드 뿐만 아니라, 자신의 이전 노드의 위치를 알게해서 두개 의 노드가 서로의 위치를 알게 할 수 도 있다,

-원형 연결리스트(Circulalr Linked List): 마지막 노드가 맨 처음 노드(Head Node)의 위치를 알게 되면, 머리와 꼬리가 연결된 형태가 되는 것 

-O(N)의 시간복잡도: 자료에 대한 접근이 작은 자료구조에서는 연결리스트 사용을 지양해야함

-배열과 다리 노드를 추가하고 제거하는 과정을 통해 최대 노드의 수를 언제든지 변경할 수 있기 때문에, 메모리 공간을 유동적으로 사용할 수 있다. 

**데이터의 접근이 다소 느리지만, 메모리 공간활용 및 데이터의 추가와 삭제가 효율적이다. 

 

 

참조:

http://arkainoh.blogspot.com/2018/06/array.linkedlist.html

 

2. 스택 vs 큐 

스택:

-스택이란? 객체들의 집합소로서 데이터를 기록하는 구조, 접근 방법은 후입선출(LIFO:Last Input First Out)

-아래가 막혀있고 위가 open형태, 차곡차곡 쌓는 구조 

-삽입: PUSH, 삭제: POP

 

큐?

-FIFO(First Input First Out)의 구조, 먼저 들어간 데이터가 먼저 나오는 구조 

-자료의 입력과 출력을 한 쪽 끝(Front, rear)으로 제한한 자료구조

-put(), get()

-컴퓨터 버퍼에서 주로 사용됨, 마구 입력되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다. 

-단점? 큐에 빈 메모리가 남아 있어도 rear가 배열의 끝에 도달했을 경우, 꽉찬 거으로 판단할 수 있음 >> 개선판이 원형큐

-원형큐? 메모리 공간은 잘 활용하나 배열로 구현되어 있기 때문에 큐의 크기가 제한되는 단점이 존재 >> 링크드 리스트 큐 

-링크드리스트? 큐의 크기가 제한이 없고, 삽입과 삭제가 편리하다. 

 

덱(deque)?

자료의 입력과 출력을 양 쪽 긑에서 가능하게 하는 자료구조 

-scroll: 입력이 한쪽 끝으로만 가능하도록 제한한 덱

-shelf: 출력이 한쪽 끝으로만 가능하도록 제한한 덱  

 

 

 

 

 

-마지막에 삽입한 요소를 삭제하기 위해서는 앞에 요소들이 전부 삭제 되어야 한다. 

-주로 순서를 보장하기 위한 처리가 필요할 때 사용함 

 

 

참조:

https://mygumi.tistory.com/357 

 

 

3.힙(heap)?

-완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 

-여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 

-힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.

-종류?

-최대 힙(max heap)

--부모의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 

-최소힙(min heap)

-부모 노드이 키 값이 자식 노드의 키 값보다 작거나 같은 와전 이진트리 

 

 

-힙에서의 부모 노드와 자식 노드의 관계
--왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
--오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
--부모의 인덱스 = (자식의 인덱스) / 2

 

-힙의 삭제 

-힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.

-새로운 노드를 부모의 노드들과 교환해서 힙의 성질을 만족시킨다. 

ex)max heap에서 새로운 요소 8을 삽입 

 

 

 

--java언어를 이용한 최대 힙 삽입 연산

/* 최대힙 삽입 */
void insert_max_heap(int x){
maxHeap[++heapSize] = x; // 힙 크기를 하나 증가하고 마지막 노드에 x를 넣는다.

for (int i=heapSize; i>1; i/=2) {
  // 마지막 노드가 자신의 부모 노드보다 크면 swap
  if (maxHeap[i/2] < maxHeap[i]) {
    swap(i/2, i);
  } else {
    break;
  }
}
}
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

-힙삭제

-최대 힙에서 최댓값은 루트 노드들이므로 루트 노드가 삭제된다. 

--최대 힙(Max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다. 

--삭제된 루트 노드에는 힙의 마지막 노드를 가져온다. 

--힙을 재구성한다. 

--java 언어를 이용한 최대힙(max heap) 연산 

/* 최대힙 삭제 */
int delete_max_heap(){
if (heapSize == 0) // 배열이 빈 경우
  return 0;

int item = maxHeap[1]; // 루트 노드의 값을 저장한다.
maxHeap[1] = maxHeap[heapSize]; // 마지막 노드의 값을 루트 노드에 둔다.
maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드를 0으로 초기화한다.

for (int i=1; i*2<=heapSize;) {
  // 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 반복문을 나간다.
  if (maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
    break;
  }
  // 왼쪽 노드가 더 큰 경우, 왼쪽 노드와 마지막 노드를 swap
  else if (maxHeap[i*2] > maxHeap[i*2+1]) {
    swap(i, i*2);
    i = i*2;
  }
  // 오른쪽 노드가 더 큰 경우, 오른쪽 노드와 마지막 노드를 swap
  else {
    swap(i, i*2+1);
    i = i*2+1;
  }
}
return item;
}
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

참조

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html