알고리즘 문제 풀기 : Step1) 문제 이해하기, Step2) 접근 방법, Step3) 코드 설계, Step4) 코드 구현
1. 시간복잡도
- 시간복잡도에 데이터의 크기(n)를 넣어서 나온 값이 100,000,000(10^8)이 넘게 되면, 코딩테스트에서 시간 초과할 가능성이 있다.
- 그러므로, 관행적으로 10^8을 넘지 않도록 유의한다.
2. 제약조건
- 한 문제의 다양한 제약조건 중 시간이 증가할만한 것을 N의 기준으로 삼는다.
3. Big-O Notation
- T(n) = n^2 + 2n + 1에서 +1과 2n은 무시될 수 있다.
- 1 무시 이유 : n의 변화에 따른 T(n)의 변화 정도 판단이 목적
- 2n 무시 이유 : n이 증가할 수록 2n의 비율이 미미해진다.
- 따라서 T(n) = n^2 + 2n + 1에서 Big-O -> O(n^2)
T(n)에서 실제로 영향력을 끼치는 부분을 Big-O라고 함
- T(n) = n^2 + 2n + 9 -> O(n^2)
- T(n) = n^4 + n^3 + n^2 + 1 -> O(n^4)
- T(n) = 5n^3 + 3n^2 + 2n + 1 -> O(n^3)
O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)
4. 예시
- O(1) : 입력 데이터에 의존하지 않는 경우
if a > b:
return True
else:
return False
- O(log n) : 각 단계에서 입력 데이터의 크기를 줄여나갈 때
def binary_search(data, value):
n = len(data)
left = 0
right = n - 1
while left <= right:
middle = (left + right) // 2
if value < data[middle]:
right = middle - 1
elif value > data[middle]:
left = middle + 1
else:
return middle
raise ValueError('Value is not in the list')
if __name__ == '__main__':
data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(data, 8))
- O(n) : 입력 데이터의 크기에 따라 실행 시간이 선형적으로 증가할 때
def linear_search(data, value):
for index in range(len(data)):
if value == data[index]:
return index
raise ValueError('Value not found in the list')
if __name__ == '__main__':
data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
print(linear_search(data, 7))
- O(nlog n) : 입력 데이터의 각 연산이 로그 시간 복잡도를 갖는 경우
def merge_sort(data):
if len(data) <= 1:
return
mid = len(data) // 2
left_data = data[:mid]
right_data = data[mid:]
merge_sort(left_data)
merge_sort(right_data)
left_index = 0
right_index = 0
data_index = 0
while left_index < len(left_data) and right_index < len(right_data):
if left_data[left_index] < right_data[right_index]:
data[data_index] = left_data[left_index]
left_index += 1
else:
data[data_index] = right_data[right_index]
right_index += 1
data_index += 1
if left_index < len(left_data):
del data[data_index:]
data += left_data[left_index:]
elif right_index < len(right_data):
del data[data_index:]
data += right_data[right_index:]
if __name__ == '__main__':
data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
merge_sort(data)
print(data)
- O(n^2) : 입력 데이터의 각 값에 대해 선형 시간 연산을 수행해야 하는 경우
def bubble_sort(data):
swapped = True
while swapped:
swapped = False
for i in range(len(data)-1):
if data[i] > data[i+1]:
data[i], data[i+1] = data[i+1], data[i]
swapped = True
if __name__ == '__main__':
data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
bubble_sort(data)
print(data)
- O(2^n) : 입력 데이터가 추가될 때마다 증가율이 두 배가 되는 경우
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
- O(n!) : 입력 데이터의 크기에 따라 계승적 방식으로 증가할 때
def heap_permutation(data, n):
if n == 1:
print(data)
return
for i in range(n):
heap_permutation(data, n - 1)
if n % 2 == 0:
data[i], data[n-1] = data[n-1], data[i]
else:
data[0], data[n-1] = data[n-1], data[0]
if __name__ == '__main__':
data = [1, 2, 3]
heap_permutation(data, len(data))
'Algorithm > Study' 카테고리의 다른 글
Linked List 구현 (0) | 2024.05.04 |
---|---|
자료구조 기초 (0) | 2023.06.27 |