CS 기술 면접 예상 질문 [자료구조/알고리즘]

CS 개념 정리

CS 기술 면접 예상 질문 [자료구조/알고리즘]

Squidward 2022. 10. 11. 02:07

Trie 예상질문

1. Trie란?

: '문자열'을 저장하고 '문자열'을 효율적으로 탐색하기 위한 '트리' 형태의 자료구조

2. Trie의 사용 예시?

: 자동완성 기능, 사전 검색 등 문자열을 탐색하는 곳

3. Trie를 다른말로?

: 래딕스 트리 or 접두사 트리 or 탐색트리

4. Trie의 장단점?

: 문자열 검색을 빠르게 함

: 각 노드에서 자식들에 대한 포인터를 배열로 모두 저장하고 있어 메모리 측면에서 비효율적

5. Trie의 생성시간 복잡도, 탐색시간 복잡도는? 그렇게 된 이유?

: 생성시간 복잡도 - O(M*L) , 모든 문자열 M개를 넣고, 트라이에 가장 긴 문자열 길이만큼 넣기 때문

: 탐색시간 복잡도 - O(M) , 트리 제일 깊게 탐색하는 경우가 가장 긴 문자열 길이까지 들어가는 것이기 때문

> L: 제일 긴 문자열 길이, M: 총 문자열 수

AVL Tree 예상질문

1. AVL Tree의 탄생 이유?

: 이진트리의 한계(이진 트리가 한쪽으로 쏠려 루트 시작-끝 모두 탐색해야할 때)를 극복하기 위해

2. AVL Tree란?

: 이진 탐색 트리로, 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 트리

3. Balance Factor, BF란?

: 왼쪽과 오른쪽의 자식의 높이 차이

> 균형이 잡혔다는 것은 BF가 최대 1까지 차이나는 것, 즉 -1부터 1까지일 때를 의미함

3. 균형이 무너진 유형을 설명하세요.

: 총 4가지 유형으로 LL, RR, LR, RL이 있다.

LR은 y가 z의 왼쪽 자식, x가 y의 오른쪽 자식일 때

Red-Black Tree 예상질문

1. 레드 블랙 트리란?

: 각 노드에 색깔을 저장하는 공간을 추가하여 색깔을 기준으로 균형을 맞추는 트리

2. 레드 블랙 트리의 조건은?

1. 모든 노드는 빨간색 혹은 검은색이다.

2. 루트 노드는 검은색이다.

3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)

4. 빨간색 노드의 자식은 검은색이다. > No Double Red(빨간색 노드가 연속으로 나올 수 없다)

5. 모든 리프 노드에서 Black Depth는 같다. > 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

3. Double Red란?

: 레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다. 이렇게 되면 4번 조건이 위배되는 상황이 발생한다. 즉, 빨간색 노드가 연속으로 2번 나타날 수 있다(Double Red)

4. Double Red 해결 방법, 2가지 설명

: Double Red가 발생했을 때

삼촌 노드가 검은색이라면 -> Restructuring을 수행하면 된다.
삼촌 노드가 빨간색이라면 -> Recoloring을 수행하면 된다.

Restructuring

1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

Recoloring

1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.   
   1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.   
   1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

시간복잡도와 공간복잡도 예상질문

1. 시간 복잡도란? 공간 복잡도란?

시간복잡도란 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 의미하고,

공간복잡도란 작성한 프로그램이 얼마나 많은 메모리를 차지하는지를 분석하는 방법을 말합니다.

2. 빅-오 표기법이란?

: 알고리즘의 효율성을 표기해주는 것으로, 점근적 실행시간을 표기할 때 쓰이는 수학적 표기 방법입니다.

3. O(n**2) 예시 > ex. 이중 for문

: 삽입정렬, 버블정렬, 선택정렬

4. 상한? 하한?

: 가장 빨리 실행될때가 하한, 가장 늦게 실행될때가 하한입니다. 빅오 표기법은 주어진 경우의 수행시간의 상한을 나타냅니다.

5. 빅오, 빅오메가, 빅세타?

: 가장 늦게실행될때가 빅오, 가장 빨리 실행될때가 빅오메가, 평균이 빅세타

완전 탐색 알고리즘 (Brute Force) 예상질문

1. 완전 탐색이란?

: 모든 경우의 수를 전부 시도하는 법. 구현이 간단하고, 해가 존재하면 항상 찾음.

경우의 수에 따라 실행시간 비례, 입력의 범위가 작을 때 유용

2. 완전 탐색의 종류

: Brute-Force기법, 백트래킹, 비트마스크, 재귀함수, 순열, DFS/BFS

3. Brute-Force기법?

: 반복/조건문을 이용해 가능한 모든 방법을 단순히 찾는 것

4. 비트마스크란?

: 경우의 수가 두가지 선택으로 구성되는 경우 유용. 비트니까,, 예시로 포함여부를 0,1로 구분해 배열에 저장 가능

5. 재귀함수란?

: 자신을 정의할 때 자기 자신을 재참조하는 방법입니다. 예시로 피보나치 수열이 있습니다. 시간 복잡도는 O(N) 입니다.

DFS와 BFS 예상질문

1. DFS란?

: 깊이 우선 탐색으로, 그래프의 깊은 곳을 먼저 탐색하는 알고리즘 입니다.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

2. BFS란?

: 넓이 우선 탐색으로, 그래프의 가까운 곳을 먼저 탐색하는 알고리즘 입니다.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

3. DFS 동작 과정?

1) 시작 노드 방문 처리

2) 시작노드와 연결된 노드(인접 노드) 중 방문하지 않은 노드가 있으면 그 노드를 스택에 넣고 방문 처리

3) 모두 방문처리 된 경우 다음 최상단 노드 꺼냄

4) 더 이상 수행할 수 없을때까지 반복

4. DFS 코드 작성

def dfs(graph, v, visited):

visited[v]=True

for i in graph[v]:

if not visited[i]:

dfs(graph, i, visited)

5. DFS에 스택 자료구조가 쓰이는 이유?

: 재귀함수와 스택자료구조가 동일하기 때문입니다. 스택은 후입선출이기때문에 가장 마지막에 호출된 함수 factorial(1)을 먼저 완료하고, 값을 아래로 전달해 최초 호출된 factorial(3)을 최종적으로 계산합니다. 재귀함수에서는

6. BFS 동작 과정?

1) 탐색 시작할 노드 큐에 삽입

2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드 큐에 삽입하고 방먼 처리

3) 2번을 수행할 수 없을때까지 반복

7. BFS 코드 작성

def bfs(graph, start, visited):

queue = deque([start])

visited[start] = True

while queue:

v = queue.popleft()

for i in graph[v]:

queue.append(i)

visited[i]=True

순열 예상질문

1. 순열이란?

: 순서가 부여된 임의의 집합을 다른 순서로 섞는 연산. n!

2. 순열 구현 - 이터툴즈 이용

from itertools import permutations

arr = [0, 1, 2, 3, 4, 5]

print(list(permutations(arr, 3)))

조합 예상질문

1. 조합이란?

: 순열과 다르게 순서 상관 없이 n개의 값 중 r개의 순서를 고려하지 않고 나열한 경우의 수. 계산식으로 nCr이라고 표현한다.

nCr
= nPr / r!
= n! / ((n-r)! * r!)

2. 점화식이란? : 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것

ex. f(n) = f(n-1)+f(n-2)

3. 조합의 점화식?

n-1Cr-1 : 어떤 특정한 원소를 포함시키고 뽑았을 때
n-1Cr : 어떤 특정한 원소를 포함시키지 않고 뽑았을 때

4. 조합 vs 순열

: 조합은 순서 없이 나열, 순열은 순서 있이 나열

5. 조합 구현 - 이터툴즈 이용

from itertools import combinations

arr = [0, 1, 2, 3, 4, 5]

print(list(combinations(arr, 3)))

부분집합 예상질문

: 주어진 집합에 포함되어있는 집합, 시간 복잡도 O(n * nCr)

2. 부분집합 구현 - 파이썬

from itertools import combinations 

arr = [1, 2, 3]
result = []
for i in range(len(arr)+1):
  result = result+list(combinations(arr,i))  

print(result)
# [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

combinations 메서드의 첫번째 인자로 대상 리스트를 넣고,
두번째 인자로는 부분집합의 길이를 넣는다. => 해당 길이를 가지는 부분집합
메서드에서 나왔을 때는 combinations 객체라는 형태로 있기 때문에 list 메서드로 형변환을 해주어야만 리스트로 사용할 수 있습니다.
공집합을 포함한 모든 부분집합을 구하려면 두번째로 들어갈 인자의 값을 배열의 길이를 모두 커버할때까지 1씩 더하면서 result 배열에 더해주면 됩니다.

백트래킹 (Backtracking) 예상질문

1. 백트래킹이란?

: 현재 상태에서 가능한 모든 경로를 탐색하다, 원하는 결과와 불일치하는 부분이 발생하면 탐색을 멈추고 전단계로 돌아가는, 왔던길 그대로를 되짚어가는 알고리즘이다.

2. 백트래킹 구현
def btrack():

if len(arr) == m:

return

else:

for i in range n:

if i not in arr:

arr.append(i)

btrack()

arr.pop()

3. 백트래킹 vs DFS

백트래킹은 불필요한 탐색을 하지 않는다. 132, 234, 123, 총 3개의 요소를 가지고 있는데, 123이라는 값을 찾고 있다고 하자. 순서대로 132라는 값에 접근했을 때, 백의 자리 수가 동일하나, 십의 자리 수가 다르기 때문에 더 이상 탐색을 진행하지 않고 다음 수로 넘어간다.

그러나 DFS는 모든 경우의 수를 탐색한다. 다시 위의 예를 빌려, 132이라는 수를 탐색할 때, 십의 자리 수에 접근했을 때 원하는 수가 아님에도 불구하고 일의 자리 수까지, 즉 트리의 바닥에 도달할 때까지 탐색을 계속한다.

728x90