Algorithm & DS Question and Answer

08 January 2024 - 7 mins read time
Tags: Algorithm

Algorithm 과 DS 질문과 답

1. 배열과 링크드 리스트의 장단점에 대해 간략히 설명해주세요

배열 :

장점 :

1. 빠른접근: 인덱스를 사용하여 직접 원소에 접근할 수 있어 검색이 빠릅니다.
2. 메모리 효율적: 연속된 메모리 공간에 원소를 저장하므로, 메모리 관리가 상대적으로 편합니다.

단점 :

1. 크기 고정: 배열의 크기는 선언 시에 결정되며, 크기를 변경하기 어렵습니다.
2. 삽입 및 삭제가 비효율적: 중간에 원소를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 원소를 이동시켜야 합니다.

링크드 리스트 :

장점 :

1. 가변적인 크기: 동적으로 크기를 조정할 수 있습니다.
2. 중간 삽입 및 삭제가 효율적: 특정 노드를 삽입하거나 삭제할 때, 해당노드만 조작하면 됩니다.

단점 :

1. 접근 속도가 느림: 특정 인덱스에 직접 접근하기 어려워, 검색이 배열에 비해 느립니다.
2. 추가적인 메모리 사용: 각 노드가 다음 노드의 주소를 저장하므로, 추가적인 메모리를 사용합니다.

Array:

Advantages:

1. Fast Access: Directly accessing elements using indices makes searching quick.
2. Memory Efficient: Storing elements in contiguous memory allows for relatively straightforward memory management.

Disadvantages:

1. Fixed Size: Array sizes are determined at declaration and are difficult to change.
2. Inefficient Insertion and Deletion: Inserting or deleting elements in the middle requires shifting all subsequent elements.

Linked List:

Advantages:

1. Variable Size: Can dynamically adjust its size.
2. Efficient Midpoint Insertion and Deletion: Adding or removing a node in the middle involves manipulating only that node.

Disadvantages:

1. Slow Access Speed: Directly accessing a specific index is challenging, resulting in slower searches compared to arrays.
2. Additional Memory Usage: Each node stores the address of the next node, requiring extra memory.

The choice between these data structures depends on the specific use case. Arrays are suitable for fast access and situations where the size does not change frequently, while linked lists are preferable for dynamic size adjustments and frequent insertions or deletions.

2. BST의 최악의 시간 복잡도와 최악의 시간이 걸리는 케이스에 대해 설명해주세요

이진탐색트리(Binary Serach Tree, BST)의 최악의 시간복잡도는 트리의 균형이 깨진 경우에 나타납니다. BST의 기본아이디는 각 노드가 왼쪽서브트리의 모든 노드보다 작고 오른쪽 서브트리의 모든 노드보다 큰 값을 가지도록 하는것입니다. 그러나 특정한 순서로 노드를 삽입하면 트리가 불균형하게 될 수 있습니다.

최악의 시간 복잡도는 주로 한 쪽으로 치우친(skewed) 트리일 때 발생합니다. 삽입이나 삭제 연산이 항상 트리의 한 쪽으로만 진행되어 트리가 연결 리스트와 유사한 형태를 가지는 경우입니다.

예를들어, 노드를 오름차순으로 삽입할 경우에 최악의 시간 복잡도가 발생할 수 있습니다. 계속해서 더 큰 값을 삽입하면 트리는 왼쪽으로만 성장하게 되어 높이가 N이 될 수 있습니다.

이런 경우에 최악의 시간복잡도는 O(N)이 됩니다. 탐색, 삽입, 삭제 등의 연산이 모두 트리의 높이에 비례하게 되므로 불균형한 트리의 경우 성능이 크게 저하됩니다.

The worst time complexity of a Binary Search Tree (BST) occurs when the tree is unbalanced. The fundamental idea of a BST is that each node should have values smaller than all nodes in its left subtree and greater than all nodes in its right subtree. However, inserting nodes in a specific order can lead to an unbalanced tree.

The worst time complexity typically occurs with a skewed tree, where insertion or deletion operations consistently progress in one direction, causing the tree to resemble a linked list.

For instance, inserting nodes in ascending order can result in the worst-case scenario. Continuously adding larger values causes the tree to grow exclusively to the left, resulting in a height of N.

In such cases, the worst time complexity becomes O(N). Operations like search, insertion, and deletion all become proportional to the height of the tree, leading to significant performance degradation in unbalanced trees.

On the other hand, when the tree is balanced, with a height of log(N), the average time complexity for operations like search, insertion, and deletion becomes O(log N).

3. 해쉬 테이블에 대해 설명해주세요

해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위한 자료 구조 중 하나입니다. 해시 테이블은 Key와 Value로 이루어진 데이터를 저장하는데, 특히 특정 키를 입력하면 해당 키에 대응하는 값을 빠르게 찾아낼 수 있습니다.

해시테이블은 해시 함수(Hash Function)를 사용하여 키를 고정된 길이의 해시 코드로 변환합니다. 이 해시 코드를 배열의 인덱스로 사용하여 데이터를 저장하거나 검색합니다. 해시 함수는 특정한 입력에 대해 일관된 길이의 해시 코드를 반환해야 하며, 가능한 서로 다른키에 대해 다른 해시코드를 생성해야합니다. 그러나 해시 함수는 두개 이상의 다른 키에 대해 동일한 해시 코드를 생성할 수 있는 충돌을 방지하기 위한 방법이 필요합니다.

충돌 (Collision): 서로 다른 키가 같은 해시 코드를 생성하는 경우를 충돌이라고 합니다. 충돌은 해시 테이블에서 해결해야 하는 주요 문제 중 하나입니다.

충돌 해결 방법 (Collision Resolution): 충돌이 발생하면 이를 해결하기 위한 다양한 방법이 있습니다. 대표적인 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다.

체이닝 (Chaining): 각 배열의 인덱스에 연결 리스트를 사용하여 충돌된 데이터를 연결하여 저장하는 방법입니다.

개방 주소법 (Open Addressing): 충돌이 발생하면 다른 빈 공간을 찾아 데이터를 저장하는 방법입니다. 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해시(Double Hashing) 등이 개방 주소법의 예시입니다.

A hash table is a data structure designed for efficient storage and retrieval of data. It consists of key-value pairs, where data is stored based on a key, and a hash function is used to map the key to a fixed-size hash code. This hash code is then used as an index to store or retrieve the associated value in an array.

• Collision: Occurs when different keys produce the same hash code. Collision resolution is a key concern in hash table design.

• Collision Resolution: Various methods exist to handle collisions, including chaining and open addressing.

• Chaining: A collision resolution method where each array index maintains a linked list to store multiple key-value pairs with the same hash code.

• Open Addressing: A collision resolution method where, in case of a collision, the system searches for the next available slot in the array to store the data.

4. Fibonacci 공식을 recursive와 dynamic programming으로 구현시 차이점에 대해 설명해주세요.

1. 중복계산방지 :

• 재귀 : 재귀적으로 피보나치를 구현할 때, 같은 값이 여러번 계산될 수 있습니다. 중복계산으로 인한 성능저하가 될 수 있습니다.
• 동적 프로그래밍: 계산된 값을 저장하고 나중에 재사용함으로써 중복 계산을 방지합니다.

2. 시간복잡도 :

• 재귀 : 중복계산으로 인해 지수 시간 복잡도를 가질 수 있습니다. 계산 시간이 입력 크기에 비례하여 기하급수 적으로 증가할 수 있습니다.
• 동적 프로그래밍: 선형 시간복잡도를 가집니다. O(n)

3. 스택 오버플로우 :

• 재귀 : 재귀호출은 호출 스택을 사용하므로, 큰 값에 대해 스택 오버 플로우를 일으킬 수 있습니다.
• 동적 프로그래밍: 반복문이나 Memoization 재귀방식을 사용하므로 스택오버플로우 문제가 발생할 가능성이 적습니다.

Differences between Recursive and Dynamic Programming Implementations of the Fibonacci Sequence:

1. Avoiding Duplicate Calculations:
   • Recursive: When implementing Fibonacci recursively, the same values may be calculated multiple times, leading to inefficient duplicate calculations.
   • Dynamic Programming: Dynamic Programming prevents duplicate calculations by storing computed values for later reuse. This method, also known as memoization, uses an array or hash table to store results.
2. Time Complexity:
   • Recursive: Recursive methods can have exponential time complexity due to duplicate calculations, growing exponentially with the input size.
   • Dynamic Programming: Dynamic Programming, by avoiding duplicate calculations and leveraging optimal substructure, achieves linear time complexity. For the Fibonacci sequence, it can be efficiently computed in O(n) time.
3. Stack Overflow:
   • Recursive: Recursive calls use the call stack, and for large Fibonacci values, this can lead to a stack overflow.
   • Dynamic Programming: Dynamic Programming typically uses iteration or optimized recursive approaches, reducing the likelihood of stack overflow issues.

5. DFS와 BFS에 대해 간략히 설명해주세요

1. DFS:
   • 한 노드에서 시작하여 깊이를 기준으로 최대한 깊숙히 들어가면서 탐색합니다.
   • 스택 또는 재귀 함수를 통해 구현할 수 있습니다.
   • 한 경로를 끝까지 탐색 한 수, 다음 경로로 넘어가기전에 백트래킹을 통해 이전 경로로 돌아갑니다.
2. BFS:
   • 한 노드에서 시작하여 현재 노드와 같은 레벨에 있는 모든 노드를 먼저 탐색합니다.
   • 큐를 사용하여 구현합니다. 큐에 노드를 삽입한 후에는 해당 노드와 인접한 모든 노드를 큐에 삽입합니다.
   • 레벨 단위로 탐색하며, 먼저 발견된 노드에 가까운 노드부터 탐색합니다.
3. DFS (Depth-First Search):
   • It starts from a node and explores as far as possible along each branch before backtracking.
   • It can be implemented using a stack or recursion.
   • After exploring one path to its deepest level, it backtracks to the previous path before moving on to the next one.
4. BFS (Breadth-First Search):
   • It starts from a node and explores all the nodes at the current level before moving on to the next level.
   • It is implemented using a queue. Nodes are inserted into the queue, and all adjacent nodes are explored before moving to the next level.
   • It explores nodes level by level, prioritizing nodes closer to the starting node.