[자구, 알고] Array, List, LinkedList, heap 질문답변

 

 

 

 

● Array vs List 차이점

 - Array

    - 메모리 상에 데이터가 연속적으로 저장
    - 사용할 크기를 미리 할당하기 때문에 고정된 크기를 갖는다. 그래서 메모리 낭비가 생길 수도 있다. 10을 할당했는데 데이터를 5개만 넣으면 5가 낭비된다.
    - 인덱스로 접근할 수 있다.
    - int[] numArray = {1, 2, 3}; -> numArray[0] 인덱스 접근 가능

 

 - List

    - 메모리 상에 데이터가 비연속적으로 저장
    - 사용할 크기를 미리 할당하지 않아도 된다. 때문에 메모리 낭비가 없다.
    - 인덱스로 접근할 수 없다.
    - List<Integer> numList = List.of(1, 2, 3); -> numList.get(0) 인덱스 접근 불가능
    - List는 인터페이스이다. 
    - LinkedList, ArrayList 등의 선형 자료 구조를 구현할 때 사용되는 추상 자료형
    - 자바에서 List 인터페이스를 구현한 클래스 : ArrayList, LinkedList, Vector, Stack, CopyOnWriteArrayList, mmutableList 

 

https://ongveloper.tistory.com/403#:~:text=%EA%B2%B0%EB%A1%A0%EB%B6%80%ED%84%B0%20%EB%A7%90%ED%95%98%EC%9E%90%EB%A9%B4%20Array%EB%8A%94,%EB%A5%BC%20%EB%AC%BB%EB%8A%94%20%EA%B2%83%EC%9D%B4%20%EC%9D%BC%EB%B0%98%EC%A0%81%EC%9D%B4%EB%8B%A4.)

 

 

● ArrayList와 LinkedList를 설명하세요.

 - ArrayList

    - List의 특징과 Array의 장점을 가진 자료 구조 -> 크기가 가변적인 배열
    - 내부적으로 Array(배열)로 이루어져 있다.
    - 인덱스를 가진다.

    - 리스트 특성그대로 크기를 동적으로 사용

    - 인덱스를 쓸 수 있는 리스트

 

 - LinkedList

    - 자료의 주소 값으로 서로 연결되어 있는 구조
    - 내부에서 array 사용하지 않음
    - 인덱스 접근 불가

 

ArrayList는 중간에 데이터를 추가하려면 추가하려는 자리의 뒤쪽 데이터를 모두 한칸씩 미루고 추가하는데 LinkedList는 바로 추가하고 링크만 바꾸면 되서 개발하다가 데이터의 추가, 삭제가 많이 발생한다면 LinkedList를 사용하는 것이 효율적이다.

 

https://caileb.tistory.com/190

 

● 힙에 대해 설명하고, Heap Sort에 대해 설명해 주세요.

 - 큐 안에 데이터 들에 우선순위를 주고 그 우선순위가 높은 데이터가 먼저 처리되도록 하는 자료구조를 우선순위 큐(Priority Queue)라고 한다. 원소를 꺼내는 데는 O(n)의 시간이 걸리는데 데이터가 많아지고 꺼내는 횟수가 늘어날 수록 시간이 너무 지연되서 조금 더 빠르게 데이터를 꺼내기 위해 만든것이 힙(heap)이다. 힙은 결국 우선순위 큐를 구현하기 위한 자료구조이다.

 - 힙은 완전 이진 트리(Complete binary tree)의 형태를 띄고 있다.
 - 힙에는 두 가지 종류가 있다. 최대 힙(max heap)과 최소 힙(min heap)
    - 최대 힙 : '부모의 값이 자식의 값보다 항상 큰' 조건을 만족하는 완전이진트리
    - 최소 힙 : '부모의 값이 자식 값보다 항상 작은' 조건을 만족하는 완전이진트리
 - 이 최대힙 혹은 최소힙을 이용하면 항상 첫번째 노드의 키 값을 최대, 혹은 최소값으로 유지

 

 - 힙정렬은 최 상위 노드 값을 하나씩 뽑아내면서 정렬을 하는 것
 - 먼저 트리를 힙 생성 알고리즘(heapify)을 통해 힘 구조로 만들어준다.
 - 이후 최상위에 있는 root값과 맨 마지막 값을 바꾼다.
 - 그리고 맨 뒤로 보낸 root 값을 제외하고 다시 힙 생성 알고리즘을 수행하여 힘 구조를 만든다.
 - 마지막으로 보내진 값을 제외하고 다시 최상위 root 값과 마지막 값을 바꾼다. 다시 힙 생성 알고리즘을 수행하여 힘 구조를 만든다.
 - 반복.

 

https://webfirewood.tistory.com/107

https://velog.io/@jimmy48/%ED%9E%99Heap-Sort

https://m.blog.naver.com/ndb796/221228342808

 

● 힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?

 - 배열의 인덱스로 접근할 수 있다. 
 - 각 노드는 인덱스를 기준으로 다음과 같은 관계식을 갖게 된다.
 - 부모 노드 : i번째 노드의 부모 노드 인덱스는 (i-1)/2
 - 왼쪽 자식 노드 : i번째 노드의 왼쪽 자식 노드 인덱스는 2i+1
 - 오른쪽 자식 노드 : i번째 노드의 오른쪽 자식 노드 인덱스는 2i+2
 - 이러한 관계로 특정 인덱스의 노드에 대한 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드를 찾을 수 있다.

 

● 힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.

 - 삽입
    - 새 data를 마지막 Node에 삽입.
    - 삽입된 노드로부터 계속해서 부모노드와 비교
    - 최대힙, 최소힙 여부에 따라 부모보다 큰지, 작인지 비교하고 swap 함.
 - 삭제
    - 힙에서 Data 의 삭제는 항상 루트 노드를 삭제한다.
    - 최대힙의 경우엔 최대값이 삭제가 되고 최소힙의 경우엔 최소값이 삭제 된다.
    - root 제거 후 가장 마지막 Node가 root 가 된다.
    - 이동 후 최대힙/최소힙 조건을 갖춰야 하므로 계속해서 자식 Node 와 비교하면서 필요시 Swap 한다.
 - 편향이 발생하지 않는 이유
    - 이진탐색트리가 편향이 발생하는 이유는 삽입 방식에 있다.
    - 삽입되는 노드의 값이 이전에 삽입된 노드들보다 작은 경우에는 왼쪽 자식 노드로 삽입되고, 큰 경우에는 오른쪽 자식 노드로 삽입된다.
    - 삽입 순서가 1, 2, 3, 4, 5, 6, 7일 때 이진 탐색 트리를 구성하면 높이가 7이 되고
    - 4, 2, 6, 1, 3, 5, 7 이면 완전이진탐색트리와 같은 3의 높이를 같는다.
    - 이처럼 이진탐색트리는 삽입순서에 따라 편향이 발생한다.
    - 반면에 힙은 무조건 삽입은 마지막에, 삭제는 첫번째것 이라고 정해져 있기 때문에 편향 없이 일정하게 구성된다.

 

https://johoonday.tistory.com/129

 

 

● Heap Sort 공간복잡도

 - Heap Sort는 주어진 배열 안에서 정렬을 수행하므로, 추가적인 배열이나 데이터 구조가 필요하지 않기 때문에 공간 복잡도는 O(1) 이다.

 

● 힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?

 - O(NlogN)
 - 입력 배열을 힙으로 만드는데 O(n)의 시간이 걸리고, 원소를 삭제하면서 정렬하는데 O(n log n)의 시간이 걸리기 때문에 시간복잡도는 O(n log n) 이다.
 - 불안정 정렬(unstable sort)
 - 안정 정렬(stable sort) : 비교하는 원소의 값이 같을 때, input 순서대로 정렬
 - 힙정렬은 Stable 하지 않은, 즉 불안정한 정렬이다. Stable 하다, 안정적이다 라는 것은 같은 값을 가지는 원소들의 순서가 정렬 이전과 이후에도 유지되는 것을 말한다. 예를 들면 [2, 1, 3, 2, 3] 과 같은 배열에서 정렬 후에도 두개의 2와 두개의 3이 들어온 순서가 유지된다는 의미인데 힙정렬은 유지 되지 않을 수 있기 때문에 Stable 하지 않다.