자료구조 Flashcards
Q1) 알고리즘의 시간 복잡도를 표현하는 세 가지 방법에 대해 설명해보세요.★
- 최단시간은 주어진 알고리즘이 문제를 해결하는 데 “최소한 얼마만큼은 걸린다”는 필요한 연산의 하한을 설명합니다, 점근식 표기법으로는 빅 오메가를 사용합니다.
+)예: 선형 탐색의 최악의 경우 시간 복잡도는 O(1)입니다. - 최장시간은 문제를 해결하는 데 얼마나 많은 연산이 필요한지의 상한을 설명합니다, 점근식 표기법으로는 빅 오를 사용합니다.
+)예: 선형 탐색의 최악의 경우 시간 복잡도는 O(n)입니다. - 마지막으로 평균 시간은 알고리즘이 문제를 해결하는 데 얼마나 많은 연산이 필요한지의 평균 케이스를 설명합니다. 일반적으로 최단시간과 최장시간이 같을 때 표기 할 수 있습니다. 빅 세타 표기법으로 나타냅니다. +)예: 버블 정렬은 최선, 최악, 평균 시간 복잡도 모두 Θ(n2) 입니다.
이 세가지 표기법들은 알고리즘이 다양한 상황에서 얼마나 효과적인지를 분석하고 비교하는 데 사용되고, 개발자들이 문제에 따른 알고리즘의 효율을 예측할 수 있게 해줍니다.
Q2) 일반적으로 알려져 있는 형태의 시간 복잡도를 가장 낮은 복잡도부터 오름차순으로 나열해보세요.★
O(1) > O(logn) > O(n) >O(n logn)> O(n²) > O(n³) > … > O(2ⁿ) > O(n!)
Q3) 분할 정복에 기반한 이진 탐색 알고리즘의 시간 복잡도를 설명해보세요.
이진 탐색 알고리즘의 시간 복잡도는 O(logn)입니다.
주어진 문제를 두개 이상의 작은 문제로 분할하여 값이 있는 위치가 아닌 배열은 다음 연산에서 버리는 방식입니다. 때문에 각 단계마다 탐색 대상의 범위가 절반으로 줄어듭니다.
Q4) 선형자료구조와 비선형자료구조의 차이점을 설명해보세요.
선형 자료 구조는 메모리에서 연속적으로 또는 순차적으로 배치됩니다. 각 요소는 이전 요소와 다음 요소와의 관계를 가지고 있습니다. 인덱스 또는 포인터를 통해 각 요소에 쉽게 접근할 수 있습니다.
+) 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue) 등이 선형 자료 구조에 해당합니다.
비선형 자료 구조는 메모리에서 부모와 자식, 또는 이웃 관계와 같이 계층적인 구조를 형성합니다. 즉, 그래프 형태로 데이터가 구성되며, 연속적이지 않을 수 있습니다. 특정 요소에 접근하기 위해서는 트리나 그래프 등의 특정 경로를 따라가야 합니다.
+) 트리(Tree), 그래프(Graph) 등이 비선형 자료 구조의 대표적인 예시입니다.
Q5) 일반적인 상황에서 배열이 다른 자료 구조에 비해 가지는 장점을 설명해보세요
- O(1)의 시간 복잡도로 빠른 액세스 속도를 가집니다.
배열의 인덱스로 요소에 직접 접근할 수 있기 때문입니다. - 데이터를 저장하는 메모리 효율성이 좋습니다.
연속적으로 데이터를 저장하며, 포인터나 노드와 같은 추가적인 메모리를 사용하지 않기 때문에 다른 자료구조에 비해 메모리의 낭비가 적고, 메모리 사용이 효율적입니다.
+) 캐시 효율성: 메모리의 연속적인 구조로 캐시 메모리 작동 측면에서도 효율적 입니다. 순차적인 액세스가 매우 빠르게 이루어집니다.
+) 간단한 구현: 다른 자료 구조에 비해 배열의 구현은 간단하며, 이를 이용한 기본적인 연산들 또한 직관적입니다.
Q6) 가변형 배열(동적 배열) 사용 시 일어날 수 있는 문제점을 설명해보세요. ★
- 메모리 사용의 비효율성이 일어날 수 있습니다
- 메모리 오버헤드 : 용량 관리, 사이즈 관리 등을 위해추가적인 메모리를 사용합니다. 추가 정보를 저장하고 관리하기 위해, 동적 배열은 그 자체로 일정량의 메모리 오버헤드를 가집니다.
- 메모리 단편화: 메모리에 여러 개의 작은 빈 공간들이 분산되어 위치하는 현상으로, 메모리를 동적으로 할당하고 해제하는 작업으로 인해 메모리 단편화가 발생할 수 있습니다. - 중간 요소의 추가 및 제거 시간 복잡도O(N) 입니다
뒷 요소들을 이동 시켜야 하므로 for문을 사용하게 됩니다. - 메모리 재할당과 복사 비용이 듭니다
내부 배열이 가득 찬 상황에서 새로운 요소를 추가하면, 보통 더 큰 크기의 배열을 새로 할당하고, 기존의 모든 요소를 새 배열로 복사합니다. 이에 따른 비용이 발생하게 되는 것입니다. - 예측하기 어려운 성능으로 작동 할 수 있습니다
요소의 추가나 삭제로 인해 재할당 및 복사가 발생하면, 일반적인 연산의 성능이 예측하기 어렵게 됩니다. 따라서, 성능을 중요시하는 시스템이나 모든 연산이 예측 가능한 시간 내에 완료되기를 요구하는 실시간 시스템 등 에서는 예측할 수 없는 지연이 문제가 될 수 있습니다. 예를 들어 게임 엔진, 실시간 통신 시스템, 고성능 계산 등이 있습니다.
Q7) 슬랙(slack) 에 대해 알고 있는 것을 설명해보세요. ★
프로그래밍에서 슬랙이란 배열이 가지고 있는 여유 공간을 의미합니다. capacity에서 사용된 size를 뺀 값으로 알 수 있고, 언리얼의 TArray 경우 slack을 확인 할 수 있는 함수를 가지고 있습니다.
slack 관리를 통해 동적 배열에서 일어날 수 있는 메모리 오버헤드나 재할당과 복사 비용을 줄일 수 있습니다. 다만, 일반적으로 클라이언트 개발자는 직접 slack 관리를 하며 개발 하지는 않습니다.
Q8) (STL) push_back(), emplace_back() 의 차이점을 설명해보세요. ★
push_back()과 emplace_back()은 모두 C++의 STL에서 제공하는 메서드입니다. 특히 vector와 같은 시퀀스 컨테이너에서 사용됩니다. 두 메서드는 요소를 컨테이너의 끝에 추가하는 기능을 수행하지만, 그 방법과 효율성에서 차이점이 있습니다.
push_back():
1. 인자로 주어진 객체의 복사 생성자를 호출하여 복사본을 컨테이너에 추가합니다.
2. 만약 인자로 임시 객체인 r-value가 주어지면 이동 생성자가 호출될 수 있습니다.
3. 복사하거나 이동하는 과정이 필요하므로, 특정 경우에서는 오버헤드가 발생할 수 있습니다.
emplace_back():
1. “emplace”라는 이름처럼, 인자를 직접 사용하여, 복사나 이동 과정 없이 컨테이너 내부에서 객체를 효율적으로 생성합니다.
2. 다만, 예기치 않은 타입 변환이 발생할 수 있고, 때로는 버그를 발생시킬 수 있습니다. 객체 타입이 확실한 상황일 때 사용하기 좋은 메서드 입니다.
