자료구조 기본

자료구조란 무엇인가요

자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 구조입니다. 데이터의 접근, 탐색, 삽입, 삭제 등의 연산을 목적에 맞게 효율적으로 수행하기 위해 사용합니다.

선형 자료구조와 비선형 자료구조의 차이는 무엇인가요

선형 자료구조는 데이터가 순차적으로 연결된 구조이고, 비선형 자료구조는 데이터가 계층적이거나 복잡한 관계로 연결된 구조입니다. 배열, 리스트는 선형이고 트리, 그래프는 비선형 자료구조입니다.

시간 복잡도와 공간 복잡도란 무엇인가요

시간 복잡도는 입력 크기에 따라 연산 시간이 얼마나 증가하는지, 공간 복잡도는 필요한 메모리 사용량이 얼마나 증가하는지를 나타냅니다.

Big-O 표기법이란 무엇인가요

입력 크기가 증가할 때 알고리즘의 시간이나 공간 사용량이 얼마나 증가하는지 연산량을 나타내는 표기법입니다.

자료구조를 선택할 때 어떤 점을 고려해야 하나요

데이터의 크기와 특성, 그리고 접근·탐색·삽입·삭제 중 어떤 연산이 자주 발생하는지를 고려하여 시간과 메모리 효율이 적합한 자료구조를 선택해야 합니다.

배열 / 동적 배열

배열(Array)이란 무엇인가요

배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조입니다. 인덱스를 이용해 원하는 요소에 빠르게 접근할 수 있습니다.

배열의 장점과 단점은 무엇인가요

연속된 메모리를 사용하기 때문에 인덱스를 통한 접근이 빠르고 캐시 효율이 좋다는 장점이 있습니다. 반면 크기가 고정되어 있고 중간 삽입이나 삭제 시 요소 이동이 필요하다는 단점이 있습니다.

배열에서 인덱스를 통한 접근이 O(1)인 이유는 무엇인가요

배열은 메모리에 연속적으로 저장되기 때문에 원하는 요소의 주소를 바로 계산할 수 있어 O(1)에 접근할 수 있습니다.

배열 중간에 데이터를 삽입하거나 삭제하면 왜 O(N)인가요

중간에 데이터를 삽입하거나 삭제하면 그 뒤에 있는 요소들을 한 칸씩 이동시켜야 하기 때문입니다. 최악의 경우 N개에 가까운 요소를 이동해야 하므로 O(N)입니다.

정적 배열과 동적 배열의 차이는 무엇인가요

정적 배열은 생성할 때 크기가 결정되고 이후 변경할 수 없지만, 동적 배열은 데이터가 증가하면 내부 배열을 더 큰 공간으로 교체하여 크기를 확장할 수 있습니다. C#의 List가 대표적인 동적 배열입니다.

동적 배열은 크기가 부족해지면 어떻게 확장되나요

현재 배열보다 더 큰 새로운 배열을 할당하고 기존 데이터를 복사한 뒤 새 배열을 사용합니다. 따라서 확장되는 순간에는 데이터 복사 비용이 발생합니다.

C#의 Array와 List의 차이는 무엇인가요

Array는 생성 후 크기가 고정되지만 List는 내부적으로 배열을 사용하면서 필요할 때 Capacity를 확장하여 동적으로 크기를 조절할 수 있습니다.

List의 Count와 Capacity의 차이는 무엇인가요?

Count는 현재 실제로 저장된 요소의 개수이고, Capacity는 내부 배열에 재할당 없이 저장할 수 있는 요소의 수입니다.

List의 Capacity가 부족하면 내부적으로 어떤 일이 발생하나요

더 큰 내부 배열을 새로 할당하고 기존 요소를 새로운 배열로 복사합니다. 이 과정에서 메모리 할당과 복사 비용이 발생하므로 많은 데이터가 들어올 것을 알고 있다면 Capacity를 미리 설정할 수도 있습니다.

연결 리스트

연결 리스트(Linked List)란 무엇인가요

연결 리스트는 각 노드가 데이터와 다음 노드에 대한 참조를 가지고 서로 연결되는 자료구조입니다. 배열과 달리 데이터가 메모리에 연속적으로 저장될 필요가 없습니다.

배열과 연결 리스트의 차이는 무엇인가요

배열은 메모리에 연속적으로 저장되어 인덱스 접근이 빠르지만 중간 삽입·삭제가 느리고, 연결 리스트는 노드가 참조로 연결되어 있어 접근은 느리지만 노드 위치를 알고 있다면 삽입·삭제가 빠릅니다.

단일 연결 리스트와 이중 연결 리스트의 차이는 무엇인가요

단일 연결 리스트는 각 노드가 다음 노드만 참조하고, 이중 연결 리스트는 이전 노드와 다음 노드를 모두 참조합니다. 따라서 이중 연결 리스트는 양방향 탐색이 가능하지만 추가 메모리가 필요합니다.

연결 리스트에서 특정 원소 접근이 O(N)인 이유는 무엇인가요

배열처럼 인덱스로 주소를 계산할 수 없기 때문에 첫 번째 노드부터 참조를 따라 순차적으로 탐색해야 합니다. 따라서 최악의 경우 모든 노드를 확인해야 해서 O(N)입니다.

연결 리스트의 삽입과 삭제가 O(1)이 될 수 있는 이유는 무엇인가요

삽입하거나 삭제할 노드의 위치를 이미 알고 있다면 주변 노드의 참조만 변경하면 되기 때문입니다. 다만 해당 노드를 먼저 탐색해야 한다면 탐색 자체에는 O(N)이 필요할 수 있습니다.

연결 리스트가 배열보다 유리한 상황은 언제인가요

데이터의 중간 삽입과 삭제가 자주 발생하고 해당 노드의 위치를 이미 알고 있는 경우 연결 리스트가 유리할 수 있습니다. 요소를 이동할 필요 없이 노드 간 연결만 변경하면 되기 때문입니다.

연결 리스트가 메모리 측면에서 배열보다 불리할 수 있는 이유는 무엇인가요

각 노드가 데이터 외에도 다음 또는 이전 노드를 가리키는 참조를 추가로 저장해야 하기 때문입니다. 또한 메모리가 연속적이지 않아 배열보다 캐시 효율이 떨어질 수 있습니다.