230410 월요일
신나서 쓰는 TMI
TIL이고 뭐고~~ 일단 이번 데이터 엔지니어링 데브코스 붙은 거 완전 신난당!!!!!!!!!!!
60명 중에 꼴찌로 극적으로 붙은 나,,,ㅋ
완전 똥멍청이야~~~~~~~~~~신난당~~~~~~~~~~
아무튼 갑자기 붙게 되어 오티는 듣지도 못하구 결석처리 되고 ㅋㅋ
알바 일정도 급하게 조정했당
오늘 오전에 고용센터 상담사분께 수강 신청 좀 빨리 해주세요!!!!!!!!!ㅠㅠ 감사합니다아 하고
오후에 알바 갔다가,,,(오늘까지는 해야 해서)
알바 끝나구 집에 돌아와서 급하게 오늘 거 강의를 듣기 시작!!
요즘에 잠을 잘 못 자서 지금 엄청나게 피곤한 상태이다.
오늘은 시간이 없어서 필수 강의만 들었고 내일부터 채워나가야겠다.
학습 주제
1강 - 자료구조와 알고리즘
자료구조(Data structure)의 종류
- 문자열(str)
- 리스트(list)
- 사전(dict)
- 순서쌍(tuple), 집합(set) 등등...
알고리즘(Algorithm)이란?
- 사전적 정의: 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
- 프로그래밍에서의 정의: 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택
선택을 어떻게 하느냐를 알기 위해 자료구조를 알아야 한다!
(01) 리스트 원소 합
def solution(x):
return x[0] + x[-1]
2강 - 선형 배열(Linear Array)
파이썬에서 배열(Array) vs 리스트(List)
리스트 길이와 관계없이 빠른 실행결과를 볼 수 있는 연산들(상수시간 복잡도 O(1))
- 맨 끝에 원소 덧붙이기 .append()
- 맨 끝에서 원소 하나를 꺼내기 .pop()
리스트의 길이에 비례하여 실행 시간이 걸리는 연산들(선형시간 복잡도 O(n))
- 원소 삽입하기 .insert()
- 원소 삭제하기 del
탐색
- 원소 탐색하기 .index()
(02) 정렬된 리스트에 원소 삽입
def solution(L, x):
for i in range(len(L)):
if L[i] > x: break
i += 1
L.insert(i, x)
return L
(02) 리스트에서 원소 찾아내기
def solution(L, x):
answer = []
for i in range(len(L)):
if L[i] == x:
answer.append(i)
if len(answer) == 0:
answer.append(-1)
return answer
3강 - 정렬(Sort), 탐색(Search)
sorted() vs .sort()
- sorted()
파이썬의 내장 함수(bulit-in function)이다.
정렬된 새로운 리스트를 얻어낸다.
- sort()
리스트의 메서드(method)이다.
해당 리스트를 정렬한다.
둘 다 (reverse = True) 적용 가능(내림차순)
문자열은 사전(알파벳) 순서로 정렬됨
람다 함수를 사용하면 원하는 기준으로 정렬 가능
선형 탐색(Linear Search)과 이진 탐색
- 선형 탐색(Linear Search) 또는 순차 탐색(Sequential Search)
순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아낸다.
리스트의 길이에 비례하는 시간이 소요(O(n))되므로, 최악의 경우에는 배열에 있는 모든 원소를 다 검사해야 할 수도 있다.
- 이진 탐색(Binary Search)
탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용이 가능하며,
절반을 기준으로 왼쪽에 있는지 오른쪽에 있는지를 판단하여 탐색한다.
한번 비교가 일어날 때마다 리스트가 반으로 줄어든다.(divide and conquer)
복잡도는 O(log n)으로 선형 탐색보다 빠르다.
(03) 이진 탐색
def solution(L, x):
answer = -1
lower = 0
upper = len(L) - 1
idx = -1
while lower <= upper:
middle = (lower + upper) // 2
if L[middle] == x:
idx = middle
break
elif L[middle] < x:
lower = middle + 1
else:
upper = middle - 1
answer = idx
return answer
4강 - 재귀 알고리즘(Recursive Algorithm) 기초
ex) 이진트리, 자연수의 합 구하기......
종결 조건 명시하기!!
효율성 고려
(04) 피보나치수열
recursive version, iterative version 둘 다 작성해 보기
코드 아래에 실행 결과 사진을 보면 실행 시간에서 차이가 많이 나는 것을 알 수 있다.
# recursive
def solution(x):
if x == 0:
return 0
elif x == 1:
return 1
else:
return solution(x-1) + solution(x-2)
# iterative
def solution(x):
a, b = 0, 1
for _ in range(x):
a, b = b, a + b
return a
5강 - 재귀 알고리즘(Recursive Algorithm) 응용
조합의 수
하노이의 탑
피보나치수열
(05) 재귀적 이진 탐색
빈칸 채우기 문제이다.
def solution(L, x, l, u):
if l > u:
return -1
mid = (l + u) // 2
if x == L[mid]:
return mid
elif x < L[mid]:
return solution(L, x, l, mid-1)
else:
return solution(L, x, mid+1, u)
6강 - 알고리즘의 복잡도(Complexity of Algorithm)
시간 복잡도(Time complexity)와 공간복잡도(Space complexity)
평균 시간 복잡도(Average Time Complexity)와 최악 시간 복잡도(Worst-case Time Complexity)
Big-O notation
- 선형 시간 알고리즘 - O(n)
Average-case : O(n)
Worst-case : O(n)
- 로그 시간 알고리즘 - O(logn)
선형 시간보다 낮은 복잡도
- 이차 시간 알고리즘 - O(n^2)
ex) 삽입 정렬(insertion sort)
Best-case : O(n)
Worst-case : O(n^2)
* 삽입 정렬보다 낮은 복잡도를 가지는 정렬 알고리즘: 병합 정렬(merge sort) - O(nlogn)
정렬 문제에 대해 O(nlogn) 보다 낮은 복잡도를 가지는 알고리즘은 존재할 수 없음이 증명되어 있음
복잡한 예시 : 배낭 문제(knapsack problem)
공부하며 어려웠던 내용
할 만 했다,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(아마도)