CS 지식 정리 - 자료구조 (1)

 

참고사이트

Array, ArrayList, LinkedList

1. Array와 ArrayList의 차이?
2. ArrayList와 LinkedList 중 삽입/삭제와 검색이 더 효율적인 자료구조는 무엇? 이유?
3. LinkedList에서 특정 인덱스에 접근할 때 시간 복잡도는 어떻게?
4. 배열을 사용해 ArrayList를 구현하는 방법을 설명
   
   

 

1. Array는 고정된 크기와 간단한 데이터 구조를 제공하며 성능이 중요한 경우 유리하고, Array List는 크기가 동적으로 변경 가능한 데이터 구조이다.
   크기가 고정되어 있어 선언 후 크기를 변경할 수 없다. 데이터를 더 추가하려면 새 배열을 생성하고 복사해야 한다. ArrayList 크기가 자동으로 조정, 데이터가 추가되거나 삭제될 때 내부적으로 크기를 관리하므로 더 유연하다.
2. 삽입과 삭제가 자주 일어나는 경우는 LinkedList가 더 효율적이고, 특정 요소를 검색하거나 데이터 접근이 빈번한 경우는 ArrayList가 더 효율적이다. 자료구조를 선택할 때는 작업의 유형과 데이터 크기를 고려하는 것이 중요
   LinkedList는 중간 삽입/삭제가 효율적이나, 끝에서 삽입/삭제만 필요한 경우에는 ArrayList도 효율적이다.(O(1))
3. LinkedList는 특정 인덱스에 접근할 때 순차 탐색이 필요하므로 시간 복잡도가 O(n)이다. 이는 ArrayList의 O(1) 접근 시간에 비해 비효율적이다. 따라서 검색 작업이 빈번한 경우에는 LinkedList보다 ArrayList가 더 적합
4. ArrayList는 내부적으로 고정 크기 배열을 사용해 데이터를 저장하며, 배열의 크기가 부족하면 요소를 복사해 크기를 동적으로 확장하는 방식으로 구현된다.

Stack과 Queue

 

1. 스택과 큐는 어디에서 주로 사용?
2. Deque(Double-Ended Queue)란 무엇? 어디에 사용?
3. 스택을 단일 배열로 구현할 때 주의해야 할 점?
4. Queue를 LinkedList로 구현하려면 어떤 메서드가 필요?

 

 

1. 스택과 큐는 다양한 알고리즘과 문제를 해결되는 데 사용되는 기본 자료구조이며, 스택은 삽입과 삭제가 한 쪽 끝에서만 이루어지는 데이터 구조로 후입 선출(LIFO, Last In First Out) 방식으로 웹 브라우저 뒤로 가기 (가장 나중에 열린 페이지부터 뒤로 가기를 실행), 문서작업에서 Ctrl+Z (가장 나중에 수정한 내역부터 되돌림) 으로 활용가능하며, 큐는 한 쪽에서 삽입이, 다른 한쪽에서는 삭제가 이루어지는데 선입 선출(FIFO, First In First Out) 방식으로 주로 데이터가 입력된 순서대로 처리하는 상황에 사용된다. ( 우선순위 예약, 프로세스 관리 )
2. Deque는 양방향에서 데이터를 처리할 수 있는 queue형 자료구조로, 양쪽 끝에서 삽입과 삭제가 가능한 유연한 자료구조로, 슬라이딩 윈도우, 캐싱, 이중 방향탐색 등 다양한 상황에 사용된다.
3. 스택을 단일 배열로 구현할 때 주의해야 할 점은 LIFO (Last In, First Out) 배열은 선언 시 크기가 고정되므로, 스택에 너무 많은 데이터를 삽입하면 오버플로우가 발생, 스택에 데이터가 없는 상태에서 꺼내려고하면 언더플로우가 발생할 수 있다.
4. Queue를 LinkedList로 구현하려면 요소를 끝에 추가하는 enqueue, 앞에서 제거하는 dequeue, 가장 앞 요소를 조회하는 peek, 비어있는지 확인하는 isEmpty와 같은 메서드가 필요하다.

 

Tree와 Heap

 

1. 이진 트리(Binary Tree)와 이진 탐색 트리(BST, Binary Search Tree)의 차이?
2. Heap과 Priority Queue의 차이
3. 트리의 균형을 유지해야 하는 이유

 

 

1. 이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리 구조로, 값의 크기와 관련된 규칙은 없다. 반면, 이진 탐색 트리(BST)는 이진 트리의 일종으로, 왼쪽 자식 노드의 값은 부모보다 작고, 오른쪽 자식 노드의 값은 부모보다 큰 규칙을 따른다. 이 차이로 인해 이진 탐색 트리는 데이터 탐색, 삽입, 삭제가 더 효율적이며, 정렬된 데이터를 관리하는 데 적합하다.
2. Heap은 완전 이진 트리 형태로 구성된 자료구조로, 각 노드의 값이 특정 규칙(최대값 또는 최소값 우선)에 따라 정렬된다. 반면, Priority Queue는 내부적으로 Heap을 사용해 구현되는 경우가 많지만, Heap 외에도 배열이나 링크드 리스트로도 구현할 수 있다. 즉, Heap은 자료를 저장하는 구조 자체를 의미하고, Priority Queue는 우선순위에 따라 자료를 처리하는 개념을 포함한 자료구조이다.
3. 트리의 균형을 유지하지 않으면 트리가 한쪽으로 치우친 형태가 되어, 최악의 경우 선형 구조처럼 작동하게 된다. 이로 인해 탐색, 삽입, 삭제와 같은 주요 연산의 시간 복잡도가 O(log n)에서 O(n)으로 증가해 효율성이 떨어진다. 균형 잡힌 트리는 높이를 최소화하여 이러한 연산을 평균적으로 빠르게 수행할 수 있도록 보장하므로, 균형 유지가 중요하다.

 

트리 순회

 

1. 트리의 전위, 중위, 후위 순회를 차례대로 설명, 순서의 차이가 왜 중요한지
2. 트리의 레벨 순회(Level Order Traversal)는 어떤 방식으로 구현?
3. 재귀를 사용하지 않고 트리 순회를 구현하려면 어떻게?

 

1. 트리의 순회 방식은 데이터를 탐색하거나 처리하는 순서를 결정하는 방법이다. 전위, 중위, 후위 순회는 각기 다른 순서를 따르며, 목적에 따라 적합한 순회 방식을 선택한다. 예를들어, 전위는 트리 구조를 복사하거나 루트 중심 처리가 필요할 때, 중위는 이진 탐색 트리에서 정렬된 데이터를 얻고자 할 때, 후위는 자식을 모두 처리한 후 루트를 방문해야할 때 사용된다.
2. 레벨 순회는 트리의 노드들을 루트 노드부터 시작해, 각 레벨별로 왼쪽에서 오르쪽 순서로 하는 탐색 방식이다. 즉, 트리의 계층 구조를 따라서 노드를 하나씩 처리한다. 레벨 순회는 큐 자료구조를 사용해 구현한다. 큐는 FIFO(First In, First Out) 특성을 가지며, 노드를 방문한 순서대로 다음 레벨의 노드를 처리할 수 있게 한다.

레벨 순회는 트리의 각 레벨을 차례로 처리해야 하기 때문에 선입선출(FIFO) 방식인 큐가 적합하다. 큐는 먼저 들어온 노드를 먼저 처리하므로, 트리의 레벨별 순서를 자연스럽게 유지할 수 있다.

 

3. 트리 순회를 재귀 없이 구현하려면 스택이나 큐를 사용해 함수 호출을 수동으로 관리해야 한다. 전위, 중위, 후위 순회는 스택으로, 레벨 순회는 큐를 이용해 간단히 구현할 수 있다. 이는 재귀 호출 없이 순회를 효율적으로 수행할 수 있는 방법이다.