📒 1강
왜 자료구조를 알아야 하는가?
파이썬의 기본적인 데이터 타입 만으로는 해결하기 어려운 문제가 있고,
문제들을 조금 더 효과적으로 해결하기 위한 여러가지 자료구조들이 있다.
왜 알고리즘을 알아야 하는가?
문제마다 최적의 해법은 서로 다르다.
주어진 문제의 효율적인 해결을 위해 적절한 자료 구조와 연산 방법들을 선택해야한다.
📒 2강 - 선형 배열 (Arrays)
배열이란?
👉 원소들을 순서대로 늘어놓은 것
👉 파이썬에서는 list 자료형이 있고, 원소의 순서대로 0부터 매겨진 index가 존재한다.
연산
- 시간 소요가 길이와 무관한 연산: 맨 끝에 덧붙이거나 제외하는 append(), pop() 연산 --> 상수 시간 O(1)
- 리스트가 크면 클수록 오래 걸리는 연산 : 앞이나 중간 원소 삭제 혹은 삽입하는 insert(index, value), del(index) 연산 --> 선형 시간 O(n)
- 탐색하는 연산
📒 3강 - 정렬(sort), 탐색(search)
파이썬 리스트의 정렬
- sorted() - 정렬된 새로운 리스트를 얻어냄.
- sort() - 그 리스트를 새롭게 정렬함.
! reverse = True정렬에 이용하는 키를 지정하는 방법
key=lambda x : (원하는요소)
(예시) 문자열의 길이를 key로 정렬하고 싶을 때
L = ['abcde', 'xyz', 'spam']
l = sorted(L, key=lambda x : len(x))
-> ['xyz', 'spam', 'abcde'](예시) 키를 지정하는 또 다른 예
L = [{'name':'John', 'score':83}, {'name':'Paul', 'score':92}]
L.sort(key=lambda x : x['score'], reverse=True)탐색 알고리즘 - 선형 탐색 (Linear Search)
선형 탐색 혹은 순차 탐색이라고 불리는 방법은 하나하나 앞에서부터 확인하며 찾고자 하는 값과 비교한다.
리스트의 길이에 비례하는 시간 소요 --> O(n)
def linear_search(L, x):
i = 0
while i < len(L) and L[i] != x:
i += 1
if i < len(L):
return i
else:
return -1! list의 index() 메소드와 동일
이진 탐색 (Binary Search)
이 탐색 기법은 배열이 정렬되어 있다는 가정에서 작동한다.
lower, middle, upper 인덱스와 그 값을 활용하여 탐색한다.
lower = 0
upper = len(L) -1
idx = -1
while lower <= upper:
middle = (lower + upper) // 2
if L[middle] == target :
return middle
elif L[middle] < target :
lower = middle + 1
else:
upper = middle - 1📒 4강 - 재귀 알고리즘 기초
재귀 함수(recursive functions)란?
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것이다.
생각보다 많은 종류의 문제가 재귀적으로 해결 가능하다.
(예시1 - 1부터 n까지 모든 자연수의 합 구하기)
위의 경우 음수까지 반복되다가 maximum depth 에러가 발생한다.
그래서 코드를 수정하면
def sum(n):
if n < 1:
return n
else:
return n + sum(n-1)재귀함수는 호출을 계속해서 하기 때문에, 재귀 호출의 종결 조건이 매우 중요하다!
재귀 알고리즘의 효율 --> 복잡도는 반복문과 동일하지만, 표현력은 높고 효율성은 떨어질 수 있다.
(예시 - 피보나치 수열)
def fibonacci(x):
if x >= 2:
return fibonacci(x-1)+ fibonacci(x-2)
else:
return x
def solution(x):
answer = fibonacci(x)
return answer📒 5강 - 재귀 알고리즘 응용
조합의 수 계산
: n 개의 서로 다른 원소에서 m 개를 택하는 경우의 수
= n-1개에서 m개를 택한 경우의 수 + n-1개에서 m-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)재귀 알고리즘의 유용성
재귀 알고리즘은 동일한 함수를 계속 호출하기 때문에 효율성은 좋지 않지만, 직관적으로 표현할 수 있다는 장점이 있다.
📒 6강 - 알고리즘의 복잡도
시간 복잡도 (Time Complexity)
문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
-
평균 시간 복잡도
-
최악 시간 복잡도
공간 복잡도 (Space Complexity)
문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계
Big-O Notation
알고리즘의 복잡도를 표현하는 점근 표기법의 하나로, 수학적 함수와 비교하여 표현한다.
-
O(n) - 선형 시간 복잡도
선형 탐색의 경우가 해당된다. -
O(logn) - 로그 시간 복잡도
크기 순으로 정렬된 수에서 특정 값을 찾는 이진 탐색 알고리즘이 해당된다. -
O(n2) - 이차 시간 알고리즘
삽입 정렬이 여기에 해당된다. -
O(nlogn)
병합 정렬이 여기에 해당되며, 입력 패턴에 따라 정렬 속도에 차이가 있지만 정렬 문제에 대해 가장 낮은 시간 복잡도의 정렬 방법이다.📒 7강 - 연결 리스트 (Linked list)
추상적 자료 구조
-
data: 정수, 문자열, 레코드 등
-
일련의 연산들: 삽입, 삭제, 순회, 정렬, 탐색 등
📒 11강 - 스택 (Stack)
