[CS 면접] 자료구조 및 알고리즘 - 1

보초님의 github에 있는 질문들을 보며 답변을 달아본 것입니다.

문제사항, 잘못된점 혹은 궁금한점이 있다면 댓글로 남겨주시면 감사하겠습니다.

시간복잡도와 공간복잡도에 대해 설명해 주세요.

시간 복잡도는 시간효율성, 공간복잡도는 공간 효율성을 의미합니다.

이를 나타내는 점근 표기법으로 big-O, big-omega, big-theta 표기법이 있습니다.

이중 big-O 방식을 이용하는데 big-o는 상한선을 나타내는데 사용합니다.

이를 이용해 알고리즘의 최악의 효율성일 때를 의미하는 것을 나타내기 위해 빅오표기법을 사용합니다.

O(1)은 O(N^2) 보다 무조건적으로 빠른가요?

네 무조건적으로 빠릅니다. O(1)은 상수 시간을 의미하여 입력값의 크기와 상관없이 수행시간이 고정이지만 O(N^2)는 입력값의 크기가 커질수록 수행시간이 증가하게 됩니다. 따라서 입력값이 적은경우에는 그 차이가 적을 수 있지만 입력값이 커지게 된다면 수행속도 차이가 충분히 나게됩니다. 이는 그래프를 통해서도 알 수 있습니다.

링크드 리스트에 대해 설명해 주세요.

링크드 리스트는 데이터의 요소들이 노드로 구성되고 각 노드는 데이터와 다음 노드를 가리키는 링크로 이루어져 있는 자료구조입니다. 장점으로는 연속된 메모리 공간을 사용하지 않아도 데이터를 저장하고 관리할 수 있어. 또한 크기를 지정하지 않아 추가, 삭제가 자유로운 자료구조입니다.

삽입은 맨 앞에 삽입하는 경우는 O(1)이지만 특정 위치를 지정하여 삽입하는 경우 O(N)의 시간복잡도를 가지게 되고 조회의 경우는 O(N)의 시간복잡도를 가집니다.

배열과 링크드 리스트를 비교해 주세요

배열의 경우는 크기를 정해놓고 사용하여 확장이 어려운 구조이며 낭비되는 메모리가 발생할수 있고, 연속된 메모리 공간을 할당해서 사용합니다. 때문에 캐시의 활용성이 좋아 성능에 유리할 수 있습니다. 또한 각각의 요소들이 인덱스를 가지고 있어 조회 속도가 빠르다. 삽입은 맨뒤라면 O(1) 그 외에 경우는 O(N)이 걸리고 조회의 경우 O(1)의 시간 복잡도를 가지게됩니다.

링크드 리스트는 크기를 정하지 않고 사용해 낭비되는 메모리는 적지만 다음노드를 가리키는 추가적인 메모리가 발생합니다. 때문에 캐시 활용성은 낮을 수 있습닌다. 추가 및 삭제가 용이한 구조이고 연속된 메모리 공간을 할당해서 사용하지 않습니다. 따라서 조회는 O(N), 삽입은 맨 앞이라면 O(1), 중간이라면 O(N)의 시간 복잡도를 가지게 됩니다.

링크드 리스트를 사용해서 구현할 수 있는 다른 자료구조에 대해 설명해주세요.

링크드 리스트를 이용하여 스택과 큐, 덱 등을 구현할 수 있습니다

스택과 큐에대해 설명해주세요

스택은 LIFO 구조로 먼저 들어간 데이터가 나중에 나온다는 특징이 있습니다. 스택을 사용하는 예시로는 메모리의 Stack, DFS 등이 있습니다.

큐는 FIFO 구조로 먼저 들어간 데이터가 먼저 나온다는 특징이 있습니다. 큐를 사용하는 예시로는 은행 대기열, BFS 등이 있습니다.

스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요

먼저 스택 2개로 큐를 만드는 방법은 입력을 담당하는 스택과 출력을 담당하는 스택을 정햐여 데이터를 삽입할 때는 입력을 담당하는 스택에 데이터를 삽입합니다. 데이터를 출력할 때는 입력스택에 있는 데이터를 꺼내 출력스택에 쌓으면 먼저들어간 데이터가 스택의 최상단으로 나오게 되어 먼저 출력할 수 있게됩니다. 출력스택이 비었다면 입력스택의 데이터를 모두 출력스택으로 옮겨서 출력한다면 스택 2개로 큐를 구현할 수 있게됩니다. 시간복잡도는 입력의 경우 O(1), 출력은 최악의 경우 O(N) 이 걸리게 됩니다. 하지만 이 작업은 n 번마다 1번씩만 발생하므로 전체 시간 복잡도는 O(1)입니다.

다음으로 큐2개로 스택을 만드는 방법은 먼저 한개의 큐의 데이터를 삽입합니다 출력이 필요한 경우 가장 마지막 데이터를 제외한 나머지 데이터를 다른 큐로 옮겨 넣습니다. 또 다시 입력을 하는 경우는 데이터가 쌓여 있는 쪽에 삽입을 합니다. 출력이 필요한 경우는 위 과정을 반복하면 됩니다. 시간복잡도는 입력의 경우 O(1), 출력은 경우 O(N) 이 걸리게 됩니다. 근데 전체 과정 중 해당 작업은 한번만 일어나므로 O(1)이 됩니다.

시간복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?

크기를 일정한 스택과 큐에서는 가능합니다. 스택은 현재 배열의 크기를 관리해서 해당 인덱스 다음에 삽입하고 가장 마지막 인덱스를 pop하면 됩니다. 큐 같은 경우는 시작 인덱스와 마지막 인덱스를 관리해 배열을 순환구조로 사용한다면 시간복잡도를 유지하며 큐를 관리할 수 있습니다.

Prefix, Infix, Postfix에 대해 설명하고, 이를 스택을 활용해서 계산하는 방법에 대해 설명해주세요.

Prefix 는 +23 과 같이 연산자가 가장 먼저 나오는 형태, Infix는 일반적으로 사용하는 연산자가 2+3으로 나오는 형태, Postfix 는 23+ 같이 연산자가 가장 마지막에 나오는 형태를 의미합니다.

Postfix를 계산하기 위해서는 표현식을 왼쪽에서 오른쪽으로 스캔하면서 피연산자인 경우 스택에 집어넣고 연산자가 나온다면 스택의 값 상위 2개를 꺼내어 계산 후 다시 스택에 집어넣습니다.

Prefix를 계산하기 위해서는 식을 오른쪽에서 왼쪽으로 스캔하며 위의 과정을 진행하면 됩니다.

Deque는 어떻게 구현할 수 있을까요?

시작 인덱스와 끝인덱스를 관리하는 순환구조의 배열이나 큐 2개를 이용해 구현할 수 있습니다. 큐 하나에 데이터를 삽입하고 popleft를 한다면 큐에서 데이터를 꺼냅니다. 만약 마지막 데이터를 꺼낸다면 큐 2개를 이용해 스택을 구현하였을 때의 방식을 이용해 마지막 데이터를 꺼내면 됩니다. 시간복잡도는 O(1)이 됩니다.

해시 자료구조에 대해 설명해 주세요.

해시는 해시 함수를 통해 인풋 값에 따라 고유한 값을 만들어 자료의 삽입, 조회 를 O(1) 만에 할 수 있는 구조입니다. 다만 유일한 값을 만들지 못하는 경우 해당 인덱스에 값을 연결하여 링크드 리스트를 구성하는 chaining method 와 해당 인덱스 근처 값을 이용하는 open addrsing, 해시 함수를 여러번 쓰는 방법등을 통해서 해시충돌을 해결하고 데이터의 접근할 수 있도록 합니다.

충돌이 최대한 적은 해시 함수를 설계하는 방법

먼저 좋은 해시 알고리즘을 사용해야 합니다. 적절한 해시 테이블의 크기를 선택해야 하며 이 크기는 소수를 사용하는 것이 데이터를 고르게 분산시키는데 유용합니다. 또한 솔팅을 이용해 패턴의 다양화를 추가합니다.

해시값이 충돌했을 때, 어떤 방식으로 처리할수 있을까요?

chaining 을 이용해 해당 고유값에 링크드 리스트 같은 자료구조를 만들어 해당 고유값을 가진 값들을 관리하는 방법이 있고 open addressing 방법은 해시 충돌이 발생하면 해당 값 주변을 탐색하는 선형 프로빙, 2차 함수를 기반으로 빈 공간을 확인하는 2차 프로빙, 그리고 두번째 해시 함수를 이용하는 이중해싱과 같은 방법이 있습니다.

자바에서 해시 충돌을 처리하는 방법

기본적으로 separate chaining 방식을 이용하여 해시충돌을 처리합니다. java8 이상부터는 8개 이상 데이터에 대해서는 링크드 리스트가 아닌 레드블랙트리를 이용해 관리하여 탐색에 대한 효율성을 높여서 처리합니다.

Double Hashing의 장점과 단점에 대해서 설명하고, 단점을 어떻게 해결할 수 있을지 설명해 주세요.

먼저 장점으로는 선형 프로빙에 비해 더 값을 고르게 분산시킬 수 있다는 점과 해시 테이블 크기를 유연하게 조정할 수 있다는 점입니다. 단점으로는 적절한 두번째 해시함수를 선택하는 것이 어렵고 이에 따라 충돌을 유발하는 패턴이 생성되어 성능 저하가 발생할수 있습니다. 이러한 단점을 해결하기 위해서는 open addrssing 이나 seprate chaing 과 같은 다른 해결 기술과 함께 사용하거나 해시 테이블 크기를 소수로 사용하고 이를 이용한 해시 함수를 만드는 방법등이 있습니다.

트리와 이진트리, 이진탐색트리에 대해 설명해 주세요.

트리는 노드와 간선으로 이루어진 자료구조를 말하며 순환구조가 없어야 한다. 이 때 한 노드당 연결된 자녀 노드가 최대 2개로만 이루어진 트리를 이진트리라고 부른다. 이진탐색트리는 이진트리에서 부모 노드의 값보다 큰 경우 오른쪽 자녀로 부모 노드의 값보다 작은 경우 왼쪽 자녀로 배치하여 탐색을 용이하게 만든 구조를 의미한다.

그래프와 트리의 차이가 무엇인가요?

그래프 같은 경우는 순환구조가 있을 수 있지만 트리에는 순환구조가 있으면 안되고 방향성을 가져야 한다 그래서 트리를 다른이름으로는 DAG(Direted Acyclic Graph)라고 부르기도 한다.

이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?

트리를 오름차순으로 정렬한 값을 얻을 수 있다.

이진탐색트리의 주요 연산에 대한 시간복잡도를 설명하고, 왜 그런 시간복잡도가 도출되는지 설명해주세요.

삽입, 삭제, 조회 모두 평균 O(logN) 최악의 경우O(N)이 걸린다. 이진탐색트리가 균형잡혀서 생긴 경우 높이는 logN이 되어 트리를 탐색하는데 걸리는 시간이 logN 이 되지만 트리가 한쪽으로 편향되었다면 최악의 경우 선형탐색처럼 되어 O(N)이 걸리게 된다.

이진탐색트리의 한계점에 대해 설명해주세요.

트리가 편향되게 생긴다면 이진탐색트리가 주는 탐색의 이점을 얻을 수 없고 선형탐색과 유사해진다. 이렇게 편향된 트리가 생성될 수 있다는 점을 극복한 Balanced 이진탐색트리가 있다.그 예로는 AVL, Red-Black 트리 등이 있다.

이진탐색트리의 값 삽입, 삭제 방법에 대해 설명하고, 어떤식으로 값을 삽입하면 편향이 발생할까요?

값을 삽입할 때는 트리의 루트노드부토 탐색해가며 위치를 찾아 삽입을 하게 된다. 삭제의 경우는 해당 노드를 탐색해 삭제한 후 그 위치를 자신의 왼쪽 자녀 트리 중 가장 큰 값을 해당 자리로 넣게된다. 값을 넣을 때 오름차순 혹은 내림차순으로 데이터를 넣게 된다면 편향된 트리가 생기게 된다.

힙에 대해 설명해 주세요.

힙은 최소힙과 최대힙이 있고 완전이진트리로 구성되어 있습니다. 다른 이름으로는 우선순위 큐라고도 부릅니다. 최소힙은 최솟값을 찾는데,최대힙은 최댓값을 찾는데 용이합니다. 힙은 힙정렬에 사용됩니다.

힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?

0번인덱스를 사용하지 않고 루트 노드를 1번 부터 사용하여 저장, 왼쪽 자식은 index * 2 오른쪽 자식은 index * 2 + 1 로 인덱스를 갖게 저장합니다.

힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.

힙은 삽입 할때 맨 마지막 인덱스에 해당 값을 삽입하고 힙 정렬 규칙에 맞추어 부모노드와 계속 교환해나갑니다. 삭제할 때는 해당 노드와 가장 마지막 인덱스를 가진 노드를 스왑합니다. 그리고 역시 힙정렬 규칙에 맞추어 자식노드와 스왑해가며 해당 노드의 위치를 재조정 합니다. 시간복잡도는 O(logN입니다. 이진탐색트리 같은 경우는 루트노드부터 해당 아이템이 어디 들어갈지를 조사하게 되어 한쪽으로 편향된 트리가 생길 수 있지만 힙은 마지막 노드에 삽입해 부모 노드와 스왑해가며 정렬하기 때문에 편향되지 않게 구성할 수 있습니다.

힙 정렬의 시간복잡도는 어떻게 되나요? stable 한가요?

힙을 구성하는데 O(logN), 자료의 개수가 N 이므로 정렬 시간복잡도는 O(NlogN)입니다. 힙정렬은 stable하지 않습니다.

 

 

 

---

출처

• vsfe github - tech interview