[데이터 엔지니어링 데브코스 2기] TIL-2주차-파트01 자료구조와 알고리즘

1. Python의 기본 데이터 타입(data type)

• 문자열(string)
• 리스트(list)
• 딕셔너리(dictionary)
• tuple, set ..

리스트 혹은 딕셔너리와 같은 기본 데이터 타입으로도 문제를 해결할 수 있지만, 그럼에도 불구하고 자료구조를 알아야 하는 이유는 효율적으로 문제를 해결하기 위해서이다. 즉, 문제마다 적합한 자료구조를 적용하기 위해서 자료구조를 알아야 한다.

2. Linear Array(파이썬의 리스트)

• 리스트의 장점) 리스트의 길이와 상관없이 맨 끝에 원소를 덧붙이거나(list.append()) 꺼내는(list.pop()) 시간 복잡도가 O(1)으로 속도가 매우 빠르다.
• 리스트의 단점) 특정 index에 원소를 삽입(list.insert(idx, element))하거나 삭제(del(), pop(idx))하는 연산의 시간 복잡도가 O(n)으로 리스트의 길이에 따라 소요 시간이 많아진다.

3. 정렬 및 탐색

• sorted(내장 함수), sort(list의 method)
• linear search(선형 탐색) : O(n)의 시간 복잡도. 인덱스 0부터 순서대로 탐색함.
• binary search(이진 탐색) : O(log(n))의 시간 복잡도. divide and conquer 방식으로 탐색하며, 정렬된 리스트(배열)라는 전제 조건이 존재함.

일반적으로 이진 탐색이 더 좋다고 보이겠지만, 무조건적으로 이진 탐색이 더 좋다고 볼 수는 없다. 이진 탐색의 경우, 위 전제 조건이 필요하기 때문에 데이터의 특성에 맞게 적용하여야 한다.

4. 재귀 알고리즘(Recursive Alg.) 기초

ex) 이진 트리(binary tree), 피보나치 수열, 팩토리얼(factorial) 연산에 적용 가능.
단순히 효율적인 측면에서는 재귀(recursive) 알고리즘보다는 반복(iterative) 알고리즘이 효율이 더 좋다. 하지만, 재귀 알고리즘의 경우 직관성이 높아 인간이 이해하기에 편하다는 장점이 있다.

5. 재귀 알고리즘 응용

ex) 피보나치 수열, n번째 값 찾기.

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

이를 반복 알고리즘으로 표현하면 다음과 같다.

def fibo(n):
	if n <= 1:
    	return n
    else:
    	L = [0, 1]
        for i in range(2, n+1):
        	L.append(L[i-2] + L[i-1])
        return L[-1]

6. 알고리즘 복잡도

1. 시간 복잡도 (시간 관련)
2. 공간 복잡도 (메모리 관련)

보통 Big-O Notation으로 시간 복잡도를 표현한다. 이는 입력의 크기에 따른 시간 복잡도의 관계를 표현하는 지표이다.

• O(1): list.append(), 항상 동일한 시간.
• O(n): linear search, 0번 idx부터 n번 idx까지 탐색.
• O(log(n)): binary search, 길이 n을 1/2씩 줄여가며 탐색.
• O(n*log(n)): merge sort, 길이 n을 1/2씩 줄여가며 1개의 원소로 분할 후(log(n)), 원소의 값을 비교하며 병합(n).
• O(n^2): insertion sort(최악의 경우), 역순으로 정렬된 리스트의 경우, 인덱스 끝까지 원소를 접하고(n), 각 원소를 삽입하는 과정(n).