🧸자료구조
다른 분들의 블로그를 보고 총 정리한 글입니다.
https://dev-coco.tistory.com/159
https://velog.io/@humblechoi
🍀 자료구조와 알고리즘
자료구조와 알고리즘에 대해 설명해주세요.
자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이고, 알고리즘이란 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임입니다.
🍀 Array, Linked List
Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명해주세요.
Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다.
데이터의 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 Array의 장점입니다.
순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들을 한 칸씩 뒤로 밀거나 당겨줘야 하는 단점도 있습니다.
이러한 이유로 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않습니다.
Array를 적용시키면 좋을 데이터의 예를 구체적으로 들어주세요. 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 설명해주세요.
Array를 적용시키면 좋은 예로 주식 차트가 있습니다.
주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다.
즉, 순서가 중요한 데이터이므로 Array 같이 순서를 보장해주는 자료구조를 사용하는게 좋습니다.
Array를 사용하지 않고 순서가 없는 자료 구조를 사용할 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.
Array와 ArrayList의 차이점에 대해 설명해주세요.
Array는 크기가 고정적이고, ArrayList는 크기가 가변적입니다.
Array는 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르고, ArrayList는 데이터 추가 및 삭제 시 메모리를 재할당하기 때문에 속도가 Array보다 느립니다.
Array와 LinkedList의 장/단점에 대해 설명해주세요.
Array는 인덱스(index)로 해당 원소(element)에 접근할 수 있어 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있습니다. 즉 random access가 가능해 속도가 빠르다는 장점이 있습니다.
하지만 삽입 또는 삭제의 과정에서 각 원소들을 shift 해줘야 하는 비용이 생겨 이 경우 시간 복잡도는 O(n)이 된다는 단점이 있습니다.
이 문제점을 해결하기 위한 자료구조가 Linked List 입니다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있기 때문에 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1)로 해결할 수 있습니다.
하지만 Linked List는 원하는 위치에 한번에 접근할 수 없다는 단점이 있습니다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 하는 과정에 있어서 첫번째 원소부터 확인해봐야 합니다.
정리하자면, Array는 검색이 빠르지만 삽입, 삭제가 느리며 Linked List는 삽입, 삭제가 빠르지만 검색이 느립니다.
Array와 LinkedList의 차이를 설명해주세요.
1. 접근
Array는 random access를 지원합니다. 요소들을 인덱스를 통해 직접 접근할 수 있습니다. 따라서 특정 요소에 접근하는 시간복잡도는 O(1)입니다.
LinkList는 sequential access를 지원합니다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야합니다. 따라서 특정 요소에 접근할 때 시간복잡도는 O(n)입니다.
저장방식도 Array에서 요소들은 인접한 메모리 위치에 연이어 저장됩니다. 반면 LinkedList는 새로운 요소에 할당된 메모리 위치 주소가 LinkedList의 이전 요소에 저장됩니다.
2. 삽입과 삭제
Array에서 삽입과 삭제는 각 원소들을 shift 해줘야 하기 때문에 O(n)이 소요됩니다.
LinkedList는 각각의 원소들마다 자기 자신 다음에 어떤 원소인지만을 기억하고 있기 때문에 이 부분만 다른 값으로 바꿔주면 삽입과 삭제가 O(1)로 해결할 수 있습니다.
하지만, LinkedList는 원하는 위치에 한번에 접근할 수 없다는 단점이 있습니다. 따라서 원하는 위치를 찾기 위한 search 과정에 있어서 첫번째 원소부터 확인해야 합니다. 따라서 O(n) 시간이 추가적으로 발생하게 됩니다.
3. 메모리 할당
Array에서 메모리는 선언시 컴파일 타임에 할당이 됩니다.(정적 메모리 할당) 반면 LinkedList는 새로운 요소가 추가될 때 런타임에 메모리를 할당합니다.(동적 메모리 할당)
Array는 Stack 섹션에 메모리 할당이 이루어지는 반면, LinkedList는 Heap 섹션에 메모리 할당이 이루어집니다.
List와 Set의 차이점
List에는 중복되게 들어갈 수 있지만 Set은 중복이 허용되지 않습니다. List에 있는 데이터를 Set에 넣으면 중복이 제거됩니다.
데이터를 수집, 처리할 때 중복된 자료들이 수집이 될 수 있습니다. 하지만 결과는 중복되지 않아야 합니다. 그러면 중복된 데이터들을 set에 넣으면 중복이 된 데이터가 있더라도 set 안에 들어가면 중복이 없어지기 때문에 중복이 없다는 것이 보장이 될 수 있습니다.
🍀 Stack, Queue
Stack과 queue, Tree와 Heap의 구조에 대해 설명해주세요.
Stack과 Queue는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있습니다.
Stack은 후입선출(LIFO)방식, 즉 나중에 들어간 원소가 먼저 나오는 구조이고 Queue는 선입선출(FIFO)방식, 즉 먼저 들어간 원소가 먼저 나오는 구조를 갖습니다.
Tree는 스택과 큐와 같은 선형 구조가 아닌 비선형 자료구조이며, 계층적 관계를 표현하기에 적합합니다.
Heap은 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 각 노드의 키 값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키 값보다 크지 않은(최소힙) 완전 이진 트리입니다.
Stack과 Queue의 차이점은 무엇인가요?
Stack은 먼저 넣게 되는 자료가 마지막으로 나오게 되는 LIFO(Last In First Out) 구조입니다. top을 통해서 push, pop을 하면서 삽입, 삭제가 일어나고 DFS나 재귀에서 사용됩니다.
Queue는 먼저 넣게 되는 자료가 먼저 나오게 되는 FIFO(First In First Out) 구조입니다. 한 쪽 끝에서 삽입 작업을, 다른 쪽 끝에서 삭제 작업을 진행합니다. 주로 데이터가 입력된 시간 순서대로 처리해야하는 경우 사용하며 BFS나 캐시를 구현할 때 사용됩니다.
Stack과 Queue의 실사용 예를 들어 간단히 설명해주세요.
Stack - 자바의 Stack 영역
지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출시 메모리에 할당되고 종료되면 메모리가 해제되며, LIFO(Last In First Out) 구조를 가집니다.
Queue - OS의 스케쥴러
자원의 할당과 회수를 하는 스케쥴러 역할을 Queue가 할수 있습니다.
메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 그 순서를 결정하는 것이 자원의 효율적인 사용에 있고,
가장 단순한 형태의 스케쥴링 정책이 선입선처리(First In First Out) 즉, 큐라고 볼 수 있습니다.
Priority Queue(우선순위 큐)에 대해 설명해주세요.
우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조 입니다.
우선순위 큐 구현 방식에는 Array, Linked List, Heap이 있고, 그 중 힙 방식이 worst case라도 시간 복잡도 O(log N)을 보장하기 때문에 일반적으로 완전 이진 트리 형태의 힙을 이용해 구현합니다.
Priority Queue의 동작 원리가 어떻게 되나요?
우선순위 큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해 일반적으로 힙을 사용합니다. 힙은 완전 이진 트리를 통해 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(log n) 입니다.
우선순위 큐는 힙이라는 자료를 가지고 구현합니다. top이 최대면 최대 힙, 최소면 최소힙으로 표현합니다. 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있습니다. 이 성질을 통해 삽입과 삭제 연산을 모두 O(log n)으로 수행할 수 있습니다.
🍀 Tree
BST(Binary Search Tree)와 Binary Tree에 대해 설명해주세요.
이진 트리(Binary Tree)는 자식 노드가 최대 두개인 노드들로 구성된 트리이고, 이진 탐색 트리(BST)는 이진 탐색과 연결 리스트를 결합한 자료 구조입니다.
이진탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있습니다. 이진 탐색 트리는 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 값은 부모 노드보다 커야한다는 특징이 있습니다.
이진 탐색 트리의 탐색 연산은 트리의 높이에 영향을 받아 높이가 h 일때 시간 복잡도는 O(h) 이며, 트리의 균형이 한쪽으로 치우쳐진 경우 worst case가 되고 O(n)의 시간 복잡도를 가집니다. 이런 worst case를 막기 위해 나온 기법이 RBT(Red-Black Tree) 입니다.
RBT(Red-Black Tree)에 대해 설명해주세요.
RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식 자료구조이며, RBT는 BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어졌습니다.
BST를 기반으로 하기 때문에 당연히 BST 특징을 모두 갖습니다.
노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장합니다. 이러한 NIL 들을 leaf node로 간주합니다. 모든 노드를 빨간색 또는 검정색으로 색칠하며, 연결된 노드들은 색이 중복되지 않습니다.
🍀 Hash
해시 테이블(Hash Table)과 시간 복잡도에 대해 설명해주세요.
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.
빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다.
각 Key 값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회합니다. 하지만 index 값이 충돌한 경우 Chanining에 연결된 리스트까지 검색해야 하므로 O(n)까지 증가할 수 있습니다.
Hash Map과 Hash Table의 차이점에 대해 설명해주세요.
동기화 지원 여부와 null 값 허용 여부의 차이가 있습니다.
병렬처리를 하면서 자원의 동기화를 고려해야 하는 상황이면 해시 테이블을 사용해야하며 (Thread-safe), 해시 테이블은 null 값을 허용하지 않습니다.
병렬처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시 맵을 사용할 수 있고 (Thread-safe하지 않는다), null 값을 허용합니다.
