Day1 학습 내용 정리
이번 주차에는 자료구조/알고리즘 학습을 진행한다.
✅ Good to Know
import time
ts = time.time()
# 동작시킬 코드
elasped = time.time() - ts
위 과정을 통해서, 사용한 자료구조가 동작되는 시간을 알 수 있다.
(문제 유형 별 오래 걸리는 자료구조를 피하기 위해 사용하는 방법)
✅ Data Structure
해결하고자 하는 문제에 따라 최적의 해법이 다르기에 정확한 선택을 위해 자료구조를 학습한다.
🧨 자료구조를 알아야 하는 이유 ?
: 효과적으로 문제풀이를 진행하기 위해서 다양한 자료구조를 알아두어야 한다.
기초 자료형태인 list, dictionary, class를 살펴보았다.
- list의 경우 다음 코드를 확인하자.
li = [7, 8, 9, 10] del(li[2]) # li = [7, 8, 10] li = [7, 8, 9, 10] print(li.pop(2)) # li = [7, 8, 10]del, pop모두 제거한다는 방식은 같으나, del은 리턴값 없이 리스트에서 원소를 제거하는 것이고, pop의 경우 리턴값을 출력할 수 있고 리스트에서 원소를 제거하고자 한다.
+) 이외에도 append, find, insert, remove 등으로 원소 삽입 및 삭제, 찾기 가능# 원소 삽입 시 시간복잡도의 경우 li = [1, 2, 3, 4, 5, 6, 7, 8, 9] li.append(10) # O(1) y = 10 li = li + [y] # O(N)
🧨 정렬과 탐색
파이썬 내장 함수 : sorted() // 리스트에 사용가능한 메서드 : sort()
탐색은 선형탐색(순차탐색) O(N)소요 // 이진탐색 (logN) 소요
이진탐색의 경우 중앙값부터 탐색을 실시하므로 logN이 소요되어 시간복잡도가 향상된다.
✅ Complexity of Algorithm
시간복잡도는 문제 크기와 이를 해결하는데 소요된 시간, 공간복잡도는 소요되는 메모리 필요량을 의미한다. 위 두가지를 모두 최소화하여 해결해야 효과적으로 문제 풀이를 진행했다고 할 수 있다.
크게 Average case와 Worst case로 나누어 볼 수 있다.
- 선형 시간 알고리즘 O(N) : 최댓값 찾는 문제
- 로그 시간 알고리즘 O(logN) : 크기 순 정렬된 리스트에서 특정 값 찾기 위해 이분탐색
- 이차 시간 알고리즘 O(N**2) : Insertion sort
🎈 Big - O notation
: 입력 크기가 커질 때 얼마나 복잡도가 커지는 지 확인해주는 척도
정렬 알고리즘 별 정리 및 시간복잡도, 공간복잡도는 아래 링크에 이미 정리해놓았다.
✅ 코딩 테스트 특강
Grepp 교육 담당이신 Paul님께서 해주신 특강으로 전반적인 알고리즘, 자료구조에 대해 설명을 들으며 기존에 학습한 내용을 다시 정리한 느낌이 들었다.
코딩 테스트 : 알고리즘 풀이 역량에 따라 문제 종류, 난이도가 상이
코딩 인터뷰 : 직무에 필요한 배경지식을 갖추었는지, 알고리즘 사고를 논리적으로 진행했는지 점검 (live coding ,whiteboard test 등으로 평가)
