자료구조 면접질문

자료구조

자료구조는 데이터를 / 원하는 규칙이나 목적에 맞게/ 저장한 구조이고,

 

알고리즘이란

자료구조에 쌓인 데이터를 활용해 / 어떠한 문제를 해결하기 위한 / 여러 동작들의 모임입니다.

 

 

 

* 선형 구조 : 리스트, 스택, 큐 - 자료를 표현 및 저장하는 방식이 선형(linear)이다. 즉 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이다.

* 비선형 구조 : 트리, 그래프 - 비선형 구조는 데이터를 나란히 저장하지 않는 구조 이다.

 

 

리스트

* 순서를 가진 데이터의 집합을 가리키는 추상자료형

 

순차 리스트

: 배열을 기반으로 구현된 리스트 , 원소 물리적 저장 순서 == 원소 논리적 순서

 

장점

* 데이터의 참조가 쉽다.(인덱스 값을 기준으로 어디든 한번에 참조 가능하다)

단점

* 배열의 길이가 초기에 결정되어야 한다. (변경 불가능)

* 실제로 사용될 메모리보다 크게 할당하여 메모리의 낭비를 초래할 수 있으며, 반대로 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어야 하는 일이 발생할 수 있다.

* 자료의 삽입/삭제 과정에서 데이터들의 이동(복사)가 빈번하게 일어난다.

* 원소의 개수가 많고 삽입/삭제가 빈번하게 일어날수록 작업에 소요되는 시간 증가함.

 

 

연결 리스트

: 메모리의 동적할당(객체 생성, 동적: heap)을 기반으로 구현된 리스트 , 삽입과 삭제가 빈번한 가변적인 리스트를 구현할 때 사용.  

노드는 데이터를 저장할 부분과 한 노드에 연결될 노드의 포인터 위치를 가리키는 부분링크로 구성되어 있다.

 

 

ArrayList와 LinkedList의 차이가 무엇인가요?

* ArrayList : 새로운 요소를 추가할 때, 여유 공간이 있는 경우엔 O(1)이지만, 여유공간이 없는 경우엔 O(n)이므로 O(n)입니다.

* LinkedList : 새로운 요소를 추가할 때, 항상 O(1)입니다. 왜냐하면, 그냥 마지막 요소에서 다음 참조값을 가지게만 하면 되기 때문입니다.

 

1.삽입과 삭제

배열에서 삽입과 삭제는 O(N)이 소요되지만, Linkedlist에서 삽입과 삭제는 O(1)이 소요된다.

 

 2.임의 접근과 순차 접근

* 임의 접근(Random Access) : 어떤 요소에 바로 접근하는 것.

* 순차 접근(Sequential Access) : 어떤 요소에 접근할 때, 차례차례 접근하는 것.

* ArrayList :임의 접근, 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간복잡도는 O(1)이다.

* LinkedList : 순차 접근만 가능, O(n)이 걸리게 됩니다.

 

3.메모리 할당

* Array : 크기 고정

* LinkedList : 크기 동적

배열에서 메모리는 선언 시 컴파일 타임에 할당이 된다.(정적 메모리 할당) 반면 Linkedlist에서는 새로운 요소가 추가될 때 런타임에 메모리를 할당한다.(동적 메모리 할당)

배열은 Stack 섹션에 메모리 할당이 이루어 진다. 반면 Linkedlist는 Heap 섹션에 메모리 할당이 이루어진다.

 

 

스택과 큐

 

스택

특징

* 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조다.

* 선형 구조

* 후입선출구조(LIFO : Last-In-First-Out) : 마지막에 삽입한 자료를 가장 먼저 꺼낸다.

* 자료가 없을 때 pop하는 오류를 stack underflow, 스택의 크기 이상의 자료를 push 하려고 할 때의 오류를 stack overflow라고 함.

 

큐

특징

* 큐의 뒤(rear)에서만 삽입 하고, 큐의 앞(front)에서는 삭제만 이루어진다.

선형구조

선입선출구조(FIFO : First-In-First-Out) : 가장 먼저 삽입된 원소가 가장 먼저 삭제된다.

 

스택은  세로로 된 바구니와 같은 구조로 먼저 넣게 되는 자료가 마지막으로 나오게 되는 First-In Last-Out(FILO) 구조이다. top을 통해서 push, pop을 하면서 삽입과 삭제가 일어난다. DFS나 재귀에서 사용된다.

 

큐는 원소의 줄을 세우는 자료구조이다. 가로로 된 통과 같은 구조로 먼저 넣게 되는 자료가 가장 먼저 나오는 First-In First-Out(FIFO) 구조이다. 큐는 한 쪽 끝에서 삽입 작업을, 다른 쪽 끝에서 삭제 작업을 진행한다. 선입선출 구조이다. 주로 데이터가 입력된 시간 순서대로 처리되어야 하는 경우 사용한다. BFS나 캐시를 구현할 때 사용한다.

 

트리(Tree)

 

* 비선형 구조 ⇒ 1:n 관계를 가지는 자료구조

* 다:다 ⇒ 그래프, 1:다 + 계층 ⇒ 트리

 

이진트리  각 노드가 자식노드를 최대한 2개까지만 가질 수 있다.

 

이진 탐색 트리(Binary Search Tree)

모든 부모 노드들의 left child는 부모 노드의 데이터보다 값이 작아야 하고, right child는 부모 노드의 값보다 커야한다. 

 

정 이진 트리(Full Binary Tree)

자식 노드가 아예 없거나, 최대 둘뿐인 tree.

 

완전 이진 트리(Complete Binary Tree)

마지막 레빌을 제외한 모든 레벨에 노드가 채워져 있으며 , 마지막 레벨은 왼쪽부터 채워져 있어야한다. 마지막 레벨은 꽉 차있을 필요는 없다.

 

 

 

힙(Heap)

 

* 최대값과 최소값을 O(1)의 속도로 구할 수 있다.

* 보통 배열을 이용하여 구현한다.

* 구현을 쉽게 하기 위해서 인덱스 1부터 시작한다.

 

 

 

Table

키(key)와 값(value)이 하나의 쌍을 이루는 자료구조를 테이블이라고 한다

 

Hash Table

 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.

 

충돌만 아니라면 해시 테이블은 삽입,삭제,탐색 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있는 효율적인 자료구조이다.

 

해시 충돌 해결 방법

Chaining

닫힌 어드레싱 방법(closed addressing method)이다. 닫힌 어드레싱 방법은 무슨일이 있어도(충돌이 발생해도) 자신의 자리에 저장한다는 뜻이다.

이것이 가능하게 하려면 값을 저장할 자리를 여러개 마련하는 수밖에 없다. 여러 개의 자리를 마련하는 방법으로는 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다.

하지만 배열은 충돌이 발생하지 않을 경우 메모리 낭비가 심하고 충돌의 최대 횟수를 결정해야 하는 부담이 있으므로 연결 리스트를 이용하여 슬롯을 연결하는 방법이 닫힌 어드레싱 방법을 대표한다.

 

상대적으로 적은 메모리를 사용한다는 장점이 있지만 한 해시에 자료들이 계속 연결된다면(쏠림현상이 생긴다면) 검색 효율이 낮아진다는 단점이 있다.

 

 

PriorityQueue의 동작 원리가 어떻게 되나요? 

우선순위큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해서 일반적으로 힙을 사용합니다. 힙은 완전이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(logn)입니다.

우선순위 큐는 힙이라는 자료구조를 가지고 구현한다. top이 최대면 최대힙, top이 최소면 최소힙으로 표현한다. 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있다. 이 성질을 통해 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있다.

 

 

BST와 Binary Tree에 대해서 설명하세요. 

이진탐색트리(Binary Search Tree)는 이진 탐색과 연결 리스트를 결합한 자료구조이다. 이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있다. 이진 탐색 트리는 왼쪽 트리의 모든 값이 반드시 부모 노드보다 작아야 하고, 반대로 오른쪽 트리의 모든 값이 부모 노드보다 커야 하는 특징을 가지고 있어야 한다. 이진 탐색 트리의 탐색, 삽입, 삭제의 시간복잡도는 O(h)이다. 트리의 높이에 영향을 받는데, 트리가 균형이 맞지 않으면 워스트 케이스가 나올 수 있다. 그래서 이 균형을 맞춘 구조가 AVL Tree이다.

 

 

해시 테이블와 해시 테이블의 시간 복잡도에 대해 설명하시오.

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용합니다. 해시 테이블은 Key값에 해시함수를 적용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조입니다.

해시 테이블은 고유한 index로 값을 조회하기 때문에 평균적으로 O(1)의 시간복잡도를 갖습니다. 하지만 해시의 index값이 충돌이 발생한 경우 충돌된 index값에 대해 연결된 데이터들을 조회하여 원하는 값을 조회하기 때문에 O(N)까지 증가할 수 있습니다.