기술면접 답변 정리 (알고리즘, 자료구조)

1. 빅오 표기법에 대해서 설명해주세요.

 

빅오 표기법은 알고리즘의 성능을 분석하고 표현하는 데 사용되는 표기법으로, 알고리즘의 실행 시간 또는 공간 복잡도를 입력 크기에 대한 상한을 나타냅니다. 빅오(O)는 알고리즘의 최악의 실행 시간 또는 공간 복잡도를 나타내며, 입력 크기에 대한 함수의 상한을 표현합니다. 예를 들어, O(n)은 선형 시간 복잡도를 나타내며, 입력 크기에 비례하여 선형적으로 증가합니다.

 

 

2. 팩토리얼(factorial)을 구현해 보세요(손코딩).

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

 

3. 피보나치 수열 구현 방식 세 가지를 말해보시고, 시간복잡도와 공간복잡도를 설명해 주세요.

 

재귀함수:

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

• 시간복잡도: O(2^n) - 지수 시간 복잡도
• 공간복잡도: O(n) - 재귀 호출 스택의 깊이

 

반복문 방식 (Bottom-up) :

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

• 시간복잡도: O(n)
• 공간복잡도: O(1)

 

메모이제이션(Top-Down 방식):

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    return memo[n]

• 시간복잡도: O(n)
• 공간복잡도: O(n) - 메모이제이션을 위한 저장공간

 

4. BFS/DFS 차이는 무엇인가요?

 

• BFS (너비 우선 탐색): 루트 노드에서 시작하여 인접한 모든 노드를 탐색한 후 다음 레벨로 이동하는 방식입니다. 큐를 사용하여 구현하며, 최단 경로를 찾을 때 유용합니다.
• DFS (깊이 우선 탐색): 루트 노드에서 시작하여 한 방향으로 끝까지 탐색하고, 더 이상 진행할 수 없을 때 다시 이전 노드로 돌아와 다른 방향으로 탐색하는 방식입니다. 스택 또는 재귀 함수를 사용하여 구현하며, 미로 찾기나 그래프 순회에 사용됩니다.

 

5. 프림 알고리즘에 대해서 설명해 주세요.

 

프림 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하는 그래프 알고리즘 중 하나입니다. 주어진 그래프에서 모든 노드를 연결하면서 가중치의 합이 최소가 되는 트리를 찾는 목적으로 사용됩니다. 프림 알고리즘의 동작은 다음과 같습니다:

• 임의의 시작 노드를 선택하고, 이 노드를 포함한 트리를 시작합니다.
• 선택한 트리와 연결된 간선 중에서 최소 가중치를 가진 간선을 찾습니다.
• 해당 간선으로 연결된 노드를 트리에 추가합니다.
• 위 과정을 반복하여 모든 노드가 트리에 포함될 때까지 진행합니다.

 

6. 다익스트라 알고리즘에 대해서 설명해 주세요.

 

다익스트라 알고리즘은 최단 경로를 찾는 알고리즘 중 하나로, 음의 가중치를 가지지 않는 그래프에서 사용됩니다. 특정 출발 노드에서 다른 모든 노드로의 최단 경로를 찾는 목적으로 사용됩니다. 다익스트라 알고리즘의 동작은 다음과 같습니다:

• 출발 노드에서 각 노드까지의 최단 거리를 저장하는 배열을 초기화합니다.
• 아직 방문하지 않은 노드 중에서 최단 거리를 가진 노드를 선택합니다.
• 선택한 노드와 인접한 노드들의 최단 거리를 업데이트합니다.
• 위 과정을 반복하여 모든 노드의 최단 거리를 계산합니다.

 

7. 은행원 알고리즘에 대해서 설명해 주세요.

 

은행원 알고리즘은 교착 상태(데드락)을 해결하기 위한 알고리즘 중 하나입니다. 교착 상태란 여러 프로세스가 서로의 리소스를 기다리며 진행하지 못하는 상황을 가리킵니다. 은행원 알고리즘은 다음과 같은 접근 방식을 사용하여 교착 상태를 예방하거나 해결합니다:

• 각 프로세스가 필요한 리소스를 미리 선언합니다.
• 각 프로세스가 리소스를 요청할 때마다 시스템은 해당 요청이 교착 상태를 유발하지 않는지 검사합니다.
• 만약 요청이 교착 상태를 유발할 가능성이 있다면, 해당 요청을 거부합니다.
• 교착 상태를 방지하기 위해 각 프로세스가 리소스를 요청할 때, 시스템은 해당 요청이 안전한지 여부를 검사하여 안전한 경우에만 리소스를 할당합니다.

 

정렬

 

8. 정렬의 종류에는 어떤 것들이 있나요?

 

정렬의 주요 종류로는 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬, 힙 정렬, 기수 정렬 등이 있습니다.

 

9. 삽입 정렬이 일어나는 과정을 설명해 보세요.

 

삽입 정렬은 현재 위치에서 정렬된 부분과 비교하며 원소를 적절한 위치에 삽입하는 정렬 알고리즘입니다. 과정은 다음과 같습니다:

• 첫 번째 원소는 이미 정렬된 부분으로 간주합니다.
• 다음 원소를 선택하고, 이미 정렬된 부분과 비교합니다.
• 선택한 원소를 정렬된 부분의 적절한 위치에 삽입합니다.
• 위 과정을 반복하여 모든 원소가 정렬될 때까지 진행합니다.

 

10. 퀵 정렬이 일어나는 과정을 설명해 보세요.

 

퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘으로, 과정은 다음과 같습니다:

• 피벗(pivot)을 선택합니다. 피벗은 배열의 중간 값 또는 무작위로 선택됩니다.
• 피벗을 기준으로 작은 값은 피벗의 왼쪽으로, 큰 값은 피벗의 오른쪽으로 분할합니다.
• 분할된 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.
• 모든 부분 배열이 정렬되면, 합쳐진 정렬된 배열이 얻어집니다.

 

11. 54321 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?

 

54321과 같이 역순으로 정렬된 배열은 버블 정렬과 같은 비효율적인 정렬 알고리즘의 성능을 악화시킬 수 있습니다. 퀵 정렬 또는 합병 정렬과 같은 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.

 

12. 랜덤으로 배치된 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?

 

랜덤으로 배치된 배열은 대부분의 효율적인 정렬 알고리즘에서 잘 작동합니다. 퀵 정렬, 합병 정렬, 힙 정렬 등이 랜덤한 배열에 효과적으로 작동합니다.

 

13. 자릿수가 모두 같은 수가 담긴 배열이 있을 때, 어떤 정렬을 사용하면 좋을까요?

 

자릿수가 모두 같은 수가 담긴 배열은 랜덤한 배열과 비슷한 특성을 가지므로 퀵 정렬, 합병 정렬, 힙 정렬 등이 적합합니다. 이러한 정렬 알고리즘은 입력 데이터의 특성에 상관없이 일정한 성능을 제공합니다.

 

자료구조

 

14. 배열과 링크드 리스트의 차이점에 대해서 설명해 주세요.

 

• 배열: 고정 크기를 가지며, 연속적인 메모리 공간에 원소를 저장합니다. 인덱스를 사용하여 원소에 빠르게 접근할 수 있습니다. 크기를 변경하려면 새 배열을 할당하고 데이터를 복사해야 합니다.
• 링크드 리스트: 동적 크기를 가지며, 각 노드가 데이터와 다음 노드를 가리키는 링크를 포함합니다. 데이터 추가 및 삭제가 쉽고, 메모리는 불연속적으로 할당됩니다. 하지만 원소에 접근하는 데에는 선형 시간이 걸립니다.

 

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

 

• 스택(Stack): 후입선출(LIFO, Last-In-First-Out) 원칙을 따르는 자료구조로, 데이터를 쌓아 올리는 형태입니다. 주요 연산으로는 push(데이터 추가), pop(데이터 제거), top(가장 위의 데이터 확인)이 있습니다.
• 큐(Queue): 선입선출(FIFO, First-In-First-Out) 원칙을 따르는 자료구조로, 데이터를 줄을 서는 형태로 관리합니다. 주요 연산으로는 enqueue(데이터 추가), dequeue(데이터 제거), front(가장 앞의 데이터 확인)가 있습니다.

 

16. 해시테이블에 대해서 설명해 주세요.

 

해시테이블은 키(key)와 값(value)을 저장하는 자료구조로, 키를 해시 함수를 사용하여 해시코드로 변환하고 이를 배열의 인덱스로 사용하여 값을 저장하거나 검색합니다. 해시테이블은 평균적으로 상수 시간(O(1))에 데이터를 검색할 수 있으며, 많은 데이터를 빠르게 관리하기 위해 사용됩니다. 충돌(Collision)이 발생할 경우 이를 해결하기 위한 다양한 기법이 있습니다.

 

트리

 

17. 포화(Perfect) 이진트리, 완전(Complete) 이진트리, 정(Full) 이진트리의 차이점에 대해 각각 설명해주세요.

 

• 포화 이진트리 (Perfect Binary Tree): 모든 레벨이 완전히 채워져 있는 이진트리입니다. 총 노드 수가 2^n - 1개입니다.
• 완전 이진트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있는 이진트리입니다. 마지막 레벨은 왼쪽부터 순서대로 노드가 채워져야 합니다.
• 정 이진트리 (Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진트리입니다.

 

18. 그래프와 트리의 차이점에 대해서 설명해 주세요.

 

• 그래프 (Graph): 노드와 엣지로 구성된 자료구조로, 노드들 간에 임의의 연결 관계를 가질 수 있습니다. 순환이 발생할 수 있으며, 방향 그래프와 무방향 그래프로 나눌 수 있습니다.
• 트리 (Tree): 그래프의 한 종류로, 계층적인 구조를 가집니다. 노드 간에 부모-자식 관계가 있으며, 순환하지 않습니다.

 

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

 

힙은 부모 노드와 자식 노드 간에 특정한 순서를 유지하는 이진트리 기반의 자료구조입니다. 주로 최대 힙(Max Heap)과 최소 힙(Min Heap) 두 가지 종류가 있으며, 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 가지고, 최소 힙은 반대로 부모 노드가 자식 노드보다 작거나 같은 값을 가집니다. 힙은 주로 우선순위 큐와 같은 응용에서 사용됩니다.

 

20. 힙의 삽입과 삭제는 어떻게 이루어지나요?

 

• 힙 삽입 (Heap Insertion): 일반적으로 최소 힙에서 새로운 원소를 삽입할 때, 원소를 힙의 마지막 위치에 추가한 후, 부모 노드와 비교하여 힙 속성을 유지하도록 조정합니다. 최대 힙에서도 비슷한 방식으로 동작하나 부모 노드와 크기를 비교합니다.
• 힙 삭제 (Heap Deletion): 일반적으로 최소 힙에서 최솟값을 삭제할 때, 최솟값을 반환하고 힙의 마지막 노드를 루트로 이동한 후 자식 노드와 비교하여 힙 속성을 유지하도록 조정합니다. 최대 힙에서는 최대값을 삭제하는 방식으로 동작합니다.

 

21. 레드 블랙 트리에 대해 설명해주세요.

 

레드 블랙 트리는 균형 이진 탐색 트리(Binary Search Tree)의 일종으로, 각 노드에 레드 또는 블랙 색상을 할당하여 트리가 균형을 유지하도록 구성됩니다. 레드 블랙 트리의 특징은 다음과 같습니다:

• 모든 노드는 레드 또는 블랙 색상을 가집니다.
• 루트 노드는 블랙이어야 합니다.
• 레드 노드의 자식은 모두 블랙이어야 합니다.
• 어떤 노드에서 임의의 리프 노드까지 도달하는 경로는 모두 같은 수의 블랙 노드를 포함해야 합니다.
• 레드 블랙 트리의 이러한 특성을 통해 트리의 높이가 항상 로그 시간 안에 유지되므로 검색, 삽입, 삭제 등의 연산이 O(log n) 시간 복잡도를 보장합니다.

 

22. 레드 블랙 트리의 삽입과 삭제 과정에 대해서 말해보세요.

• 레드 블랙 트리의 삽입: 삽입된 노드를 일단 레드로 삽입한 후, 레드 블랙 트리 속성을 유지하도록 회전 및 리컬러링 작업을 수행합니다.

 

23. B-Tree에 대해서 설명해 주세요.

 

B-트리(B-Tree)는 데이터를 효율적으로 저장하고 검색하기 위한 자료구조로, 대용량의 데이터를 관리하는 데 사용됩니다. B-트리의 특징은 다음과 같습니다:

• 각 노드는 여러 키-값 쌍을 저장할 수 있습니다.
• 높이가 낮아서 검색 시간이 효율적입니다.
• 데이터가 정렬되지 않아도 검색이 가능합니다.
• 데이터의 삽입, 삭제, 검색 연산이 평균적으로 O(log n) 시간 복잡도를 가집니다.
• 데이터베이스 시스템에서 인덱스 구조로 많이 사용됩니다.

 

24. 최소 신장 트리에 대해서 설명해 주세요.

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프에서 모든 노드를 연결하면서 그 가중치의 합이 최소가 되는 부분 그래프를 의미합니다. 최소 신장 트리는 대표적으로 크루스칼 알고리즘과 프림 알고리즘을 사용하여 구할 수 있습니다. 주로 네트워크 설계, 도로 건설, 클러스터링 등 다양한 응용 분야에서 사용됩니다.