들어가며
지난주 금요일 OT에 이어, 오늘 본격적으로 데이터 엔지니어링 데브코스가 시작되었다.
앞으로 공부한 내용들을 정리하여 블로그에 업로드할 예정이다. 🤗
오늘의 학습 주제
- 자료구조 & 알고리즘
- 선형 배열(Linear Array)
- 정렬(Sort), 탐색(Search)
- 재귀 알고리즘 기초 / 응용
- 알고리즘의 복잡도
1. 자료구조 & 알고리즘
-
자료구조를 왜 공부해야 할까?
python에서 제공하는 기본적인 데이터 타입으로 해결할 수 없는 문제를 해결하기 위해 -
자료구조(data structure)
개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법 -
알고리즘(algorithm)
사전적 의미 : 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
프로그래밍 : 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택
해결하고자 하는 문제에 따라 (응용 종류와 범위에 따라) 최적의 해법은 달라진다.
따라서, 최적의 방법을 선택하기 위해 자료구조를 이해해야 한다.
2. 선형 배열(Linear Array)
-
배열(Array)
원소들을 순서대로 늘어놓은 것. 보통 같은 종류의 데이터가 줄지어 늘어서 있는 것을 뜻함. -
선형 배열(Linear Array)
데이터들이 선처럼 일렬로 늘어선 형태 -
리스트(List)
다른 프로그래밍 언어들과는 다르게 파이썬의 리스트(List)는 각 원소가 서로 다른 데이터 타입을 가지고 있을 수 있다. 문자열의 경우, 문자열의 길이가 달라도 상관없다.
- 리스트(배열) 연산
L = ['Bob', 'Cat', 'Spam', 'Programmers']
L.append('New') #원소 덧붙이기
L.pop() #끝에서 꺼내기
#리스트의 길이와 무관하게 빠른 결과 (상수 시간) O(1)L = [20, 37, 58, 72, 91]
L.insert(3, 65) #원소 삽입하기
del(L[3]) #원소 삭제하기
#리스트의 길이에 비례하는 결과 시간 (선형 시간) O(n)
#del(L[2]) 과 L.pop2(2) 의 차이점은?3. 정렬(Sort), 탐색(Search)
- 정렬
배열의 원소들을 조건에 따라 정렬하는 것
문자열로 이루어진 리스트의 경우, 사전 순서로 정렬한다. (문자열의 길이 순서 X)
sorted()
#내장 함수, 정렬된 새로운 리스트를 얻어냄
sort()
#리스트의 메서드, 해당 리스트를 정렬함
reverse=True
#정렬 순서를 반대로
sorted(L, key = lambda x : len(x))
#문자열 길이 순서로 정렬하기 위에서는 key를 지정해야 한다.-
탐색 알고리즘(1) - 선형 탐색(Linear Search)
순차 탐색이라고도 함. 처음부터 하나하나 차례대로 탐색.
리스트의 길이에 비례하는 시간 소요 O(n) -
탐색 알고리즘(2) - 이진 탐색(Binary Search)
탐색하려는 리스트가 이미 크기 순으로 정렬되어 있는 경우에만 적용 가능
주어진 리스트에서 하나의 원소를 찾기 위해 가장 낮은 값과 높은 값의 '중간' 값을 비교색.
한 번 비교가 일어날 때마다 리스트를 반씩 줄임 (=divide & conquer) O(log n)
4. 재귀 알고리즘 기초 / 응용
-
재귀 함수(Recursive Funtion)
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
같은 알고리즘을 반복하며 적용하여 풀이 ex.이진트리 -
종결 조건(Trivial Case)
재귀 함수 사용 시 종결 조건이 반드시 필요하다.
재귀 알고리즘의 효율 -
재귀 함수의 효율성
#1. recursive version O(n)
def sum(n) :
if n <= 1 :
return n
else :
return n + sum(n-1)
#iterative version과 비교하여 시간복잡도는 같지만, 효율성은 떨어짐.
#2. iterative version O(n)
def sum(n) :
s=0
while n>= 0 :
s += n
n -= 1
return s
#3.
def sum(n) :
return n*(n+1)//2
효율성 가장 좋음 O(1)
#재귀 알고리즘 예시
def combi(n, m) :
if n==m:
return 1
elif m==0:
return 1
else:
return combi(n-1, m) + combi(n-1, m-1)재귀 알고리즘은 반복문에 비해 효율성이 떨어지지만,
사람이 생각하는 방식대로 코딩할 수 있다는 장점이 있기에 활용하는 경우도 많다.
ex. 하노이의 탑, 조합의 수 계산 - trivial case를 고려하지 않은 실수 주의
5. 알고리즘의 복잡도
-
알고리즘의 복잡도
- 시간 복잡도 : 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
- 평균 시간 복잡도 : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
- 최악 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간
- 공간 복잡도 : 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계
-
Big-O Notation (빅오 표기법)
점근 표기법의 하나로, 함수의 증가 양상을 다른 함수와의 비교를 통해 표현한다.
알고리즘의 복잡도를 표현할 때 주로 사용된다.
-
입력의 크기가 n일 때(계수는 그다지 중요하지 않음),
-
O(logn) : 로그 시간 알고리즘
입력의 크기의 로그에 비례하는 시간 소요
이진 탐색 알고리즘에 적용 -
O(n) : 선형 시간 알고리즘
입력의 크기에 비례하는 시간 소요
average-case = worst-case = O(n) -
O(log n^2) : 이차 시간 알고리즘
삽입 정렬(insertion sort)
base case : O(n), worst case : O(n^2) -
O(nlogn) :
병합 정렬
현재 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재하지 않는다.
정렬할 데이터를 반씩 나누어 각각 정렬한 다음, 가장 앞에 놓일 것부터 골라나가는 O(logn)과 정렬된 데이터를 앞에서부터 하나하나 확인하여 두 묶음씩 다시 합쳐나가는 O(n)과정을 통해 정렬
-
