자료구조

 

📚 자료구조

 

 

자료구조

✅  배열(Array) & 링크드 리스트

✏️ Array와 LinkedList의 차이

배열은 연속된 메모리 공간에 데이터를 저장하고 리스트는 비연속적인 공간에 데이터를 저장한 뒤 두 데이터를 노드로 연결한다는 차이점이 있다.

 

✏️ Array와 LinkedList의 탐색시간

배열은 index를 통해 데이터에 접근이 가능하다. 따라서 시간복잡도는 O(1)이다. 반면에 리스트는 처음부터 연결된 노드들을 따라가며 데이터를 찾아야하기 떄문에 최악의 경우에는 첫 노드에서 탐색을 시작하고 탐색할 노드가 마지막에 있는 경우가 된다. 따라서 시간 복잡도는 O(N)이다.

 

✏️ LinkedList에서 삭제연산을 하는 과정

삭제연산을 하기 위해서는 먼저 가장 첫 노드부터 바로 다음 노드가 삭제하고나 하는 노드일때까지 탐색을 진행한다. 삭제할 노드의 이전 노드를 만나면해당 노드의 다음 노드 포인터를 삭제할 노드의 다음 노드로 만들어진다. 이렇게 하면 삭제할 노드로 가는 유일한 연결이 끊어지고 해당 노드는 리스트에서 제외된다.

 

✏️ 그럼 어떤 경우에 LinkedList를 쓰는게 적절한가?

배열은 삽입과 삭제연산이 O(N)인 반면에 링크드 리스트는 O(1)을 가진다. 따라서 삽입과 삭제가 빈번한 상황이라면 링크드 리스트를 사용하는것이 더 유리하다. 

 

📌 정리

1. 메모리 할당 : 배열은 연속적인 메모리 공간에 할당되고, 리스트는 비연속적인 메모리 공간에 할당된다.

2. 크기 : 배열은 크기가 고정되어 있으며, 리스트는 가변적이다.

3. 접근 방법 : 배열은 index를 통한 빠른 접근이 가능하지만, 리스트는 순차적으로 접근해야 한다.

4. 삽입과 삭제 : 배열은 삽입과 삭제가 번거롭고 시간이 오래걸리지만, 리스트는 삽입과 삭제가 빠르다.

 

✅  스택 & 큐

✏️ 스택과 큐의 차이점

스택은 LIFO 성격을 띄는 구조로 가장 마지막에 넣은 원소를 가장 먼저 꺼낸다. 큐는 FIFO 성격의 구조로 먼저 들어간 원소를 가장 먼저 꺼낸다.

 

✏️ 배열과 링크드 리스트중 하나로 스택을 구현한다면 어떤걸 선택할 것인가?

스택은 마지막 원소만 삭제해주면 된다. 만약 단방향 링크드 리스트를 사용한다면 마지막 바로 이전 노드까지 탐색을 진행한 뒤에 연결을 끊어줘야 한다. 따라서 O(N)의 시간복잡도가 요구된다. 배열을 사용하면 배열의 길이만 1 줄여주면 되기 때문에 O(1)이 시간 복잡도가 요구 된다. 따라서 배열을 사용하는 것이 더 효율적이다.

 

✏️ 원형 큐는 시작과 끝 인덱스 관리를 어떻게 하는지 ?

원형 큐는 front와 rear를 가르키는 포인터를 사용한다. 삽입할 때는 항상 rear 포인터의 위치에 값을 넣고 삭제할 때는 front가 가르키는 위치의 다음 값을 삭제한다. 두 포인터 모두 같은 인덱스에서 시작하고 rear는 삽입이 될 때마다 한칸 씩 이동, front는 삭제가 될 때마다 한칸씩 이동한다. 이 때문에 front는 항상 비어있는 인덱스를 가르킨다. 만약 rear의 인덱스가 front의 인덱스와 같다면 원형큐가 가득 찬 것으로 판단한다.

 

✏️ 그럼 front 인덱스의 값은 왜 비워두는지 ?

원형 큐는 rear + 1 을 큐의 전체 크기로 모듈로 연산한 값을 front 값과 비교한다. 이 연산은 큐가 공백상태인지 , 포화상태인지 구분하기 위한 용도로 사용된다. 따라서 rear가 front의 바로 이전 인덱스에 있을 경우 rear == front 가 만족되기 때문에 front에는 값이 채워질 수 없다.

 

✏️ 스택으로 큐를 만드는 방법

스택 두개를 사용하면 큐를 구현할 수 있다. 한 개의 큐는 데이터를 쌓는 용도로 사용하고 다른 하나는 데이터를 삭제하는 용도로 사용한다. push 연산이 들어올 때는 첫번째 큐에 모두 넣는다. 그리고 pop 연산이 수행되면 첫 번째 스택에서 데이터를 순서대로 pop해 모두 다른 한쪽의 스택으로 넣어주고 마지막으로 들어간 데이터를 다시 pop 해주면 가장 첫번째로 넣은 데이터를 꺼낼 수 있다.

 

✏️ 우선순위 큐란 

힙 자료구조를 사용해서 원소들간의 우선순위에 따라 가장 우선순위가 높은 원소를 꺼내는 자료구조이다. 새로운 데이터를 삽입하거나 삭제 할 때마다 힙의 완전 이진트리를 재배열해주어야 하기 때문에 삽입과 삭제에 O(longN)의 시간복잡도가 요구된다.

 

✏️ 힙 말고 다른 방법으로는 우선순위 큐를 만들 수 없는지

링크드 리스트로 우선순위 큐를 만들 수 있다. 이 때 삽입은 O(N), 삭제는 O(1)의 시간복잡도를 가진다. 즉, 데이터의 개수가 많아질 수록 효율이 떨어진다.

 

✅  그래프

✏️ 그래프란 ?

정점과 간선으로 정점 간의 관계를 표현하는 자료구조

 

✏️ 트리랑 그래프는 무슨 차이가 있는가

트리는 그래프의 한 종류이며 몇가지 조건을 가진다. 트리는 항상 간선의 개수가 정점의 개수보다 하나 더 적고, 사이클이 발생하지 않는다. 그리고 모든 점들이 연결되어 있다.

 

✏️ Dense 그래프와 Sparse 그래프란 

Dense 그래프는 정점의 개수보다 간선의 개수가 더 많은 그래프이고, Sparse그래프는 간선의 개수보다 정점의 개수가 더 많은 그래프이다.

 

✅  해시 & 해시테이블

✏️ 해시테이블이 무엇인가

Key-Value 맵핑으로 데이터를 저장하는 자료구조이다. 어떤 Key 값에 대해서 해당 키에 대한 고유한 인덱스를 해시함수를 통해 만들고 Value에 이 인덱스를 부여한다. Key 값을 넣으면 바로 Value가 나오기 때문에 O(1)의 시간복잡도를 가진다.

 

✏️ 해시충돌이란

어떤 키 값들이 해시 함수를 통해 동일한 해시 값을 가지게 되는 현상

 

✏️ 해시충돌을 해결할 수 있는 방법

• 분리 연결법 : 어떤 Key에 대한 해시 함수로 얻은 해시가 이미 존재하여 충돌이 일어났을 때 기존에 있던 데이터 뒤에 새로운 데이터를 연결시켜주는 방법이다. 데이터에는 Key Value가 모두 저장되고 Key값을 탐색해서 Key와 일치하는 데이터의 Value를 반환한다.
• 개방 주소법 : 어떤 Key에 대해 해시충돌이 일어났을 때 다른 비어있는 인덱스를 찾아 데이터를 저장하는 방법이다. 다른 인덱스를 찾는 방법은 동일한 방법을 적용해서 적용해야 한다.

 

✏️ 분리연결법의 단점

해시충돌이 일어날 때마다 같은 index에 새로운 데이터를 계속 연결시키기 때문에 같은 해시에 대한 충돌이 여러번 일어나면 다른 index에 빈 공간이 있는 경우에도 한쪽으로 데이터가 쏠릴 수 있다. 또한 데이터 저장을 위해 추가적인 메모리를 사용해야 한다는 단점도 있다.

 

✅  힙

✏️ 힙 자료구조를 배열로 구현할 때 0번 index를 사용하지 않는 이유

배열로 힙을 구현하면 완전 이진트리를 구현하기 위해 부모 자녀 노드의 인덱스 위치를, 부모노드의 인덱스 X 2 (왼쪽 노드), 부모노드의 인덱스 X 2 + 1 (오른쪽 노드)로 구성한다. root 노드를 0 으로 설정하면 이 연산을 수행할 수 없다.

 

✏️ 힙에 새로운 노드가 삽입되는 과정과 시간 복잡도를 설명 

Max Heap을 기준으로 힙에 새로운 노드를 삽입하기 위해서 완전이진트리의 마지막 노드로 새 노드를 추가한다. 이 노드를 부모노드와 비교하고 새로 추가한 노드가 더 크다면 부모노드와 자리를 바꿔준다. 새로 부모노드가 된 노드는 다시 자신의 부모노드와 비교를 해서 자리를 바꾸고 더 이상 자리를 바꿀 수 없을 때까지 진행한다. 따라서 최악의 경우에는 완전이진트리의 리프노드에서 루트노드까지 올라가며 교환 연산을 수행하기 때문에 O(logN)의 시간복잡도를 가진다.

 

✏️ 힙의 삭제과정과 시간 복잡도를 설명

힙의 삭제 연산은 root 노드를 삭제하는 연산이다. 이 때 완전이진트리의 마지막 노드의 값을 루트노드에 덮어씌워준다. 그리고 트리 재조정을 위해 루트노드부터 밑으로 비교&교환 연산을 수행한다. 따라서 최악의 경우에는 루트노드부터 리프노드까지 비교연산을 수행하기 때문에 O(logN)의 시간복잡도를 가진다.

 

✅  트리

✏️ 트리의 정의

사이클이 없고 모든 정점이 간선으로 연결된 자료구조이다. 사이클이 없어야 하기 때문에 간선의 개수는 항상 정점의 개수보다 하나 적다.

 

✏️ 이진트리를 탐색하는 세가지 방법

• 전위순회 : 부모노드를 먼저 체크하고 자녀노드의 서브트리 체크
• 중위순회 : 좌측 자녀 노드의 서브트리를 체크하고 더 이상 탐색이 불가능 할 때 부모노드를 체크한 뒤 우측 자녀노드 서브트리 탐색
• 후위순회 : 좌측 서브트리, 우측 서브트리를 모두 체크한 뒤 부모노드 체크

✏️ 완전이진트리란 

최대 두개의 자녀노드를 가지는 이진 트리로 마지막 레벨을 제외한 모든 레벨에 노드가 채워져있고 마지막 레벨은 왼쪽부터 빈 노드없이 채워져 있어야 한다.

 

✏️ 이진탐색트리가 무엇인가

트리와 트리 내 모든 서브트리의 루트노드를 기준으로 값이 더 작은 노드는 왼쪽, 값이 더 큰 노드는 오른쪽에 위치하게하는 이진트리

 

✏️ 이진탐색트리의 삭제 연산

• 삭제하려는 노드의 자녀노드가 없는 경우 : 삭제하려는 노드를 탐색해서 삭제
• 삭제하려는 노드가 하나의 자녀노드를 가진 경우 : 삭제하려는 노드의 자녀노드를 삭제하려는 노드의 부모 노드와 연결시킨 후 삭제
• 삭제하려는 노드가 두 개의 자녀노드를 가진 경우 : 삭제하려는 노드의 자녀 서브트리에서 왼쪽 서브트리를 사용한다면 최댓값을, 오른쪽 서브트리를 사용한다면 최소값을 삭제하려는 노드의 값으로 대체하고 해당 자녀노드를 삭제한다.

✏️ 이진탐색트리의 삽입 연산

새로운 노드의 값을 기준으로 더 이상 자녀노드가 없을 때 까지 탐색을 진행하다가 해당 노드의 자녀노드로 새로운 노드를 연결시킨다.

 

✏️ 이진탐색트리의 시간복잡도 

삽입과 삭제 모두 탐색을 사용해야하고 탐색은 각 노드를 대소비교하며 진행하기 때문에 트리의 높이가 h 라고 할 때, O(h)의 시간복잡도를 가진다. 즉, N 개의 노드에 대해 O(logN) 시간복잡도가 필요하다.

 

✏️ 이진탐색트리의 단점

루트노드를 기준으로 새로운 노드를 삽입하기 때문에 만약 루트노드보다 큰 값을 가진 노드가 계속해서 들어오면 불균형 트리가 생성

 

✏️ 이 때 시간복잡도는 O(logN)인가?

완전히 편향된 트리에서는 최악의 경우 모든 노드를 탐색해야하기 때문에 O(N)의 시간복잡도 요구

 

✏️ AVL 트리란

트리의 불균형을 막기위해 새로운 노드가 트리에 추가될 때마다 좌측 서브트리와 우측 서브트리의 높이 차를 사용해 트리의 균형을 맞춘다. 만약 불균형이 발견되면 세 루트노드 중 중간값을 가진 노드를 루트노드로 만들고 이를 기준으로 좌우에 서브트리를 위치시킨다.

 

✏️ AVL 트리의 시간복잡도는 이진탐색트리와 어떻게 다른가 

AVL트리는 이진탐색트리와 달리 재조정을 토해서 트리의 상태를 항상 균형을 유지하기 때문에 O(logN)의 시간복잡도를 가진다.

 

✏️ Red-Black Tree가 가지는 특징

레드블랙트리는 세가지 조건을 만족하는 트리이다.

1. 루트노드와 리프노드는 항상 Black이어야 한다.
2. Red노드의 자녀노드는 모두 Black이어야 한다.
3. 루트노드에서 어떤 리프노드까지의 경로에 있는 Black 노드의 수는 모두 동일하다.

✏️ Red-Black Tree의 삽입과정 

레드블랙트리는 먼저 새로운 노드 값을 기준으로 더 이상 갈 수 있는 자녀노드가 없는 노드까지 이동한 뒤 새로운 노드를 연결시킨다. 이 때 새로운 노드를 레드로 설정한다. 그리고 레드블랙 규칙에 따라 트리를 재조정해야 하는데 다음 두가지 경우로 나뉜다.

• 먼저 방금 삽입한 노드의 부모노드와 해당 부모노드와 같은 레벨에 있는 이웃 노드가 모두 레드라면, 이 두 노드를 블랙으로 만들고 두 노드의 부모노드, 즉 새로 삽입한 노드의 조상노드를 블랙으로 만들어준다.
• 만약 방금 삽입한 노드의 부모노드의 레벨에 있는 이웃 노드가 블랙이라면 방금 삽입한 노드를 중심으로 왼쪽으로 회전시킨 뒤 만들어진 리프노드를 중심으로 다시 오른쪽으로 한번 회전시킨다. 그리고 중심이 되었던 두 노드의 색깔을 서로 바꾸어준다.