Data_Structure_Algorithm
Big-O, Big-Theta, Big-Omega는 알고리즘의 시간 복잡도를 분석할 때 사용하는 점근 표기법입니다. 이들은 입력 크기 ( n )이 커질 때 알고리즘의 성능이 어떻게 변화하는지를 나타내기 위해 사용됩니다.
1. Big-O
Big-O는 알고리즘의 최악의 경우 성능을 나타내는 표기법으로, 주어진 함수 f(n)이 특정 함수 g(n) 보다 느리지 않다는 점근적 상한(upper bound)을 나타냅니다. 즉, Big-O 표기법은 알고리즘이 최악의 경우에 얼마나 느려질 수 있는지를 설명합니다.
예시: f(n) = 3n + 2 라면 Big-O는 O(n)으로 나타낼 수 있습니다.
2. Big-Theta
Big-Theta는 알고리즘의 평균적인 성능을 나타내며 상한과 하한이 일치하는 경우를 표현합니다. f(n)이 정확히 g(n)의 점근적 성장을 따른다고 말할 수 있습니다.
예시: f(n) = 3n + 2는 Θ(n)로 표기할 수 있습니다. 이 경우, f(n)이 정확히 g(n) = n의 증가율을 따릅니다.
3. Big-Omega
Big-Omega는 알고리즘의 최상의 경우 성능을 나타내는 표기법으로, 주어진 함수 f(n)이 특정 함수 g(n)보다 빠르지 않다는 점근적 하한(lower bound)을 나타냅니다.
예시: f(n) = 3n + 2는 Ω(n)으로 표기할 수 있습니다.
[1] Big-O를 주로 사용하는 이유
Big-O는 알고리즘의 최악의 경우 성능을 보장하므로, 최악의 경우에도 성능이 크게 저하되지 않을 것을 확인할 수 있어 실무에서 많이 사용됩니다. 실제 상황에서는 알고리즘이 예상치 못한 큰 입력이나 최악의 케이스를 마주칠 수 있기 때문에, 상한을 나타내는 Big-O 표기법이 특히 유용합니다. 반면, Big-Theta나 Big-Omega는 평균적이거나 최상의 성능을 나타내기 때문에 최악의 경우를 보장하지 못할 수 있습니다.
[2] O(1)과 O(N^2)의 비교: O(1)이 항상 더 빠를까?
O(1)은 점근적으로 상수 시간을 의미하며, O(N²)은 점근적으로 N² 시간을 의미하므로 일반적으로 입력 크기 ( n )이 커질수록 O(1)이 O(N²)보다 빠릅니다.
그러나, 무조건적으로 O(1)이 더 빠르다고 단정할 수는 없습니다. 작은 입력 크기에서는 O(N²) 알고리즘이 특정 조건에서는 더 효율적일 수 있습니다. 예를 들어, O(1) 연산이 매우 복잡하여 많은 자원을 사용하고, 반면 O(N²) 알고리즘은 간단하고 입력 크기가 작다면 오히려 O(N²) 알고리즘이 더 빠를 수 있습니다. O(1)과 O(N²) 알고리즘을 비교할 때, 단순히 점근적 복잡도만 보면 O(1)이 항상 더 빠른 것처럼 보이지만, 실제로는 알고리즘의 복잡도와 상수 계수에 따라 다를 수 있습니다. 아래 예를 들어 설명해 보겠습니다.
복잡한 O(1) 연산과 간단한 O(N²) 연산 파헤치기
1. O(1) 알고리즘: 복잡한 수학적 계산을 포함한 상수 시간 연산. 예를 들어, 고급 수학 연산이나 머신러닝 모델을 통해 미리 계산한 복잡한 결과를 반환하는 경우.
import math
def complex_constant_time_operation():
# 매우 복잡한 상수 시간 연산
result = 0
for i in range(1000000):
result += math.sin(i) * math.cos(i)
return result
이 함수는 항상 O(1)입니다. 왜냐하면 입력 크기와 상관없이 고정된 반복을 수행하기 때문입니다. 그러나, 내부 계산이 복잡하여 많은 시간이 소요됩니다.
2. O(N²) 알고리즘: 단순한 연산을 포함하는 이중 반복문.
def simple_quadratic_operation(n):
count = 0
for i in range(n):
for j in range(n):
count += 1
return count
이 함수는 이중 반복문이므로 O(N²)의 시간 복잡도를 가집니다. 하지만 내부 연산은 단순히 숫자를 더하는 것이기 때문에, 실행 속도가 매우 빠릅니다.
비교
1. 작은 입력 ( n = 10 )인 경우:
complex_constant_time_operation() 함수는 항상 고정된 100만 번의 계산을 수행하므로, 여전히 시간이 많이 소요될 것입니다.
반면, simple_quadratic_operation(10) 함수는 ( 10 * 10 = 100 ) 번의 단순한 덧셈을 수행하므로 상대적으로 훨씬 빠릅니다. 즉, 이 경우에는 복잡한 O(1) 연산보다 단순한 O(N²) 연산이 더 빠를 수 있습니다.
2. 큰 입력 (( n = 10,000 ))인 경우:
이제 simple_quadratic_operation(10000) 함수는 ( 10,000 * 10,000 = 100,000,000 ) 번의 덧셈을 수행해야 하므로, 시간이 많이 걸립니다.
complex_constant_time_operation()는 여전히 100만 번의 고정된 계산만 수행하기 때문에 상대적으로 빠릅니다.
이처럼 입력이 작을 때는 단순한 O(N²) 알고리즘이 복잡한 O(1) 알고리즘보다 빠를 수 있지만, 입력이 커질수록 O(N²)의 성능 저하가 두드러져 결국 O(1)이 유리하게 됩니다.
요약
점근적 복잡도가 낮다고 항상 더 빠른 것은 아니며, 알고리즘의 실제 수행 시간은 내부 연산의 복잡도와 상수 계수에 따라 달라질 수 있습니다. 입력 크기가 작을 때는 더 높은 점근 복잡도를 가진 단순한 알고리즘이 복잡한 상수 시간 알고리즘보다 효율적일 수 있지만, 입력 크기가 커질수록 낮은 점근 복잡도를 가진 알고리즘이 더 빠르게 수행됩니다.
[3] 링크드 리스트에 대해 설명해주세요.
: 링크드 리스트(linked list)는 데이터를 저장하는 노드들이 서로 연결된 형태로 구성된 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(참조)를 가지고 있어서, 연결된 방식으로 데이터가 순서대로 저장됩니다.
[4] 일반 배열과 링크드 리스트를 비교해주세요.
[5] 링크드 리스트를 이용해서 구현할 수 있는 다른 자료구조에 대해 설명해주세요.
1. 스택 (Stack): 스택은 마지막에 들어간 요소가 먼저 나오는 LIFO(Last In, First Out) 자료구조입니다. 링크드 리스트의 첫 번째 노드를 추가 및 제거하는 방식으로 스택을 구현할 수 있습니다.
2. 큐 (Queue): 큐는 먼저 들어간 요소가 먼저 나오는 FIFO(First In, First Out) 자료구조입니다. 링크드 리스트의 첫 번째 노드에서 삭제하고, 마지막 노드에 추가하는 방식으로 큐를 구현할 수 있습니다.
3. 덱 (Deque): 덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 링크드 리스트를 활용하여 앞뒤로 노드를 추가 및 삭제하는 방식으로 구현할 수 있습니다.
4. 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전과 다음 노드를 가리키는 포인터를 가지고 있어 양방향으로 탐색이 가능합니다. 이중 연결 리스트는 양쪽에서 삽입/삭제가 필요한 상황에서 유용합니다.
5. 원형 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 구조로, 연결 리스트의 끝과 처음이 연결된 형태입니다. 원형 연결 리스트는 한 바퀴 순환해야 하는 문제를 해결할 때 유용하게 사용됩니다.
https://github.com/VSFe/Tech-Interview/blob/main/01-DATA_STRUCTURE_ALGORITHM.md
Tech-Interview/01-DATA_STRUCTURE_ALGORITHM.md at main · VSFe/Tech-Interview
Contribute to VSFe/Tech-Interview development by creating an account on GitHub.
github.com