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

시간 복잡도는 알고리즘이 수행되는 시간을 의미하고 공간복잡도는 알고리즘이 수행될 때 차지하는 공간의 크기를 의미한다.

Big-O, Big-Theta, Big-Omega 에 대해 설명해 주세요.

• Big-O : 복잡도의 상한선을 의미한다. 즉 최악의 경우이다.
• Big-Omega : 복잡도의 하한선을 의미한다. 알고리즘의 복잡도가 Big-Omega보다 크거나 같다.
• Big-Theta : Big-O와 Big-Omega를 둘다 만족하는 경우를 의미한다.

다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?

알고리즘의 최악의 경우에 대응해야되기 때문이다. 알고리즘이 수행되는 동안 최악의 경우가 있을 수 있기 때문에 이에 대응하기 위해서 Big-O를 주로 사용한다.

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

아니다. O(1)의 의미는 입력과 상관없이 일정 시간내에 종료한다는 것이다. O(N^2)이 입력의 수가 적은 경우에 O(1)보다 빠를 수 있다.

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

링크드 리스트란 노드를 포인터로 연결하여 구현하는 리스틀 의미한다. 그 종류로는 단순 연결 리스트, 이중 연결 리스트, 원형 리스트가 있다.

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

일반 배열은 연속적인 메모리 공간상에 있으며 인덱스를 이용한 접근이 O(1)로 빠르다. 하지만 삽입과 삭제연산의 경우 배열의 데이터를 이동시켜야 하기 때문에 O(N)의 시간으로 수행된다. 링크드 리스트는 연속적인 메모리 공간에 존재하지 않고 포인터로 연결되어 있기 때문에 노드를 순차적으로 접근해야한다. 하지만 배열과 달리 크기에 대한 제약이 없다. 또한 삽입,삭제 연산이 O(1)의 시간으로 수행된다.

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

배열로 구현할 수 있는 자료구조는 대부분 만들 수 있다. 대표적으로 스택이나 큐가 있다.

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

• 스택 : Last In Fist Out을 하는 자료구조
• 큐 : First In Fist Out을 하는 자료구조

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

스택 2개로 큐

• 삽입 연산
  stack 1에 데이터를 삽입한다.
• 삭제 연산
  stack 2의 데이터를 삭제한다. 이때 stack 2의 데이터가 비어있다면 stack 1의 데이터를 옮긴다.
• 시간복잡도

1. stack2가 비어있을 때 삭제
   O(N)
2. 비어있지 않을 때 삭제, 삽입
   O(1)

큐 2개로 스택

• 삽입 연산
  queue 2에 데이터를 삽입한다. 만약 queue2에 데이터가 있다면 queue 1 기존 데이터를 삽입한다.
• 삭제 연산

1. queue 2에 데이터가 있을 경우
   queue 2에 데이터를 삭제한다.
2. queue 2에 데이터가 없을 경우
   1. queue 2에 queue1의 데이터가 하나 남을 때까지 옮기고 마지막 하나를 삭제한다.
   2. queue 2에 데이터가 하나 남을 때까지 데이터를 queue 1으로 옮긴다.

• 시간복잡도

1. 삽입, queue 2에 데이터가 있을 경우 삭제
   O(1)
2. queue 데이터가 없을 경우 삭제
   O(N)

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

스택

가능

큐

배열의 빈 공간을 미리 확보 후 배열의 중간부터 큐의 head를 시작한다면 가능하다. 하지만 빈 공간보다 더 많은 수의 데이터가 삽입될 시 더 많은 시간이 걸릴 가능성도 있다.

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

• Prefix : +1 2
  - 연산자를 만나면 push 연속 두개의 피연산자를 만날시 pop
• Infix : 1+2
• Postfix : 1 2+
  - 피연산자를 만나면 push 연산자를 만나면 pop

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

• 원형 큐를 확장하여 구현한다.
• 나머지 연산들은 원형 큐와 같고 delete_rear(), add_front()에서 rear와 front를 반대 방향으로 회전시키면 된다.

front = (front - 1 + MAX_SIZE) / MAX_SIZE
rear = (rear - 1 + MAX_SIZE) / MAX_SIZE

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

해시란 여러 길이의 데이터를 효율적으로 관리하기 위해 해시 함수를 통해 일정한 길이의 값으로 매핑하는 것을 말한다.

값이 주어졌을 때, 어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요?

• Division Method
  값을 버킷 사이즈로 나누어 나머지를 전체 버킷사이즈에서 뺀값으로 사용, 이 때 버킷사이즈는 소수를 사용하고 2의 제곱수와 먼 값을 사용하는 것이 좋다.
• Digit Folding
  값이 문자열일 때 아스키코드로 바꿔 합한 값을 사용, 이때 버킷사이즈를 넘어갈 수 있기 때문에 Divison Method를 함께 사용
• Multiplication Method
  floor(k*A mod 1) * m의 식을 사용한다. A는 0과 1사이의 실수 m은 2의 제곱수를 사용한다.
• Univiersal Hashing
  여러 해시함수를 무작위로 사용한다.

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

• Chaning
  연결리스트를 사용해 중복된 값을 저장한다.
• Open Addressing
  인덱스가 중복되었다면 다른 빈 인덱스를 찾아 저장하는 방법
  1. linear probing
  가장 가까운 빈 인덱스를 사용
  2. quadratic probing
  2의 제곱수로 탐색하여 빈 인덱스를 사용
  3. double hashing probing
  빈 인덱스를 찾을 때 까지 해시 함수를 사용하여 탐색

     h(i,k) = (h1(k) + i*h2(k)) mod M (h2(k) != 0, h2 != h1)

  h2 함수는 m과 서로소 관계여야 한다.

본인이 사용하는 언어에서는, 어떤 방식으로 해시 충돌을 처리하나요?

해시 알고리즘

• SipHash를 사용
• 기존에는 XOR이 국룰, 충돌 비율이 높은 문제
• Seed를 통해 클라이언트마다 해시 값을 다르게 함

충돌

• linear probing으로 해결
• 충돌이 일어났을 시에 == operation을 이용해 값을 찾기 때문에 Equatable 채택 필요

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

장점 : 클러스터링에 영향을 받지 않음
단점 : 연산량이 많음, 캐쉬의 효율이 가장 좋지 않음

primary clustering : 특정 영역에 원소가 몰리는 현상
secondary clustering : 여러 개의 원소가 동일한 초기 해시 값을 갖는 현상

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

트리

노드와 간선으로 이루어져있는 구조로, 사이클이 없고 노드의 개수가 N개라면 간선의 개수는 N-1개를 가지는 구조이다.

이진 트리

각각의 노드가 자식노드를 최대 2개 가지는 트리이다.

이진 탐색 트리

이진 트리 중 중복이 없고 왼쪽 자식노드는 루트보다 작고 오른쪽 자식노드는 루트보다 큰 값을 가지는 구조이다.

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

그래프와 트리의 가장 큰 차이는 사이클이 없다는 것이다.

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

이진탐색트리의 정렬된 순서를 읽을 수 있다.

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

삽입

삽입이 될 위치를 찾아야되기 때문에 탐색과 동일하게 O(logn)

삭제

삭제할 노드를 탐색하고 만약 삭제된 자리를 대체를 하기 위한 노드들 찾아야 된다면 다시 탐색을 수행한다.
따라서 다른 연산들과 동일하게 O(logn)

탐색

$n = 2^{h+1} -1$
$n + 1 = 2^{h+1}$
$log(n+1) = h + 1$
$h = log(n+1) - 1$
최악의 경우 트리의 높이 만큼 탐색하기 때문에 O(logn)

하지만 이 경우는 포화 트리일 경우이고 편향 트리일 경우에는 O(n)

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

모든 연산이 트리의 높이에 의해 결정이 되기 때문에 편향 트리일 경우 이진 탐색 트리의 장점을 살릴 수 없다. 따라서 AVL트리 같은 개선된 트리가 나왔다.

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

삽입

탐색을 하여 탐색이 실패한 자리에 값 삽입

삭제

1) 삭제하려는 노드가 리프일 경우 그냥 삭제
2) 삭제하려는 노드가 하나의 서브트리만 가지고 있는 경우 삭제된 노드에 부모에 연결
3) 삭제하려는 노드가 두개의 서브트리를 가질 경우 왼쪽 서브트리에서 가장 큰 값을 올리거나 오른쪽 서브트리에서 가장 작은 자손을 올린다.

참고자료

• https://velog.io/@wonhee010/Stack-2개로-Queue-구현하기
• https://devahj.tistory.com/43
• https://jeong9216.tistory.com/523
• https://sihyungyou.github.io/iOS-hash-collision-swift/
• http://egloos.zum.com/sweeper/v/925740
• http://contents2.kocw.or.kr/KOCW/document/2017/cup/hwangsoyoung/9.pdf
• https://velog.io/@haero_kim/이진-탐색-트리-Binary-Search-Tree
• https://mommoo.tistory.com/101