리스트 배열 연산

맨 끝에 원소 덧붙이기 : .append()
맨 끝에서 원소 꺼내기 : .pop()
→ O(1) , 리스트 길이와 무관하게 빠르게 실행 가능

원소 삽입하기 : .insert(index, 추가 요소)
원소 삭제하기 : del(리스트[index])
→ O(n) , 리스트 길이 길수록 오래걸림

원소 탐색하기 : .index()

* pop과 del의 차이 : pop은 요소를 제거하면서 반환, del은 요소를 제거하고 반환하지 않음

리스트 정렬

sorted() : 파이썬 내장 함수
.sort() : 리스트 메서드
→ 디폴트는 오름차순, 내림차순은 reverse = True / 정렬순서는 사전순서(알파벳 순서)
→ 문자열 길이에 따라 정렬하고 싶다면 키 지정 : sorted(리스트, key = lambda x:len(x))

탐색

• 선형 탐색 linear search
  배열의 길이에 비례하는 시간 소모 → O(n)
  최악의 경우 → 모든 원소 비교

• 이진 탐색 Binary Search
  이미 정렬되어 있는 경우에만 적용 가능
  한번 비교가 일어날때 리스트를 반씩 줄임 → O(longn)

재귀 알고리즘 recursive algorithm

하나의 함수에서 자신을 다시 호출하여 작업 수행 → 종결조건(Trivial case) 필수
반복함수와 비교했을때 효율성 떨어짐(중복되는 함수호출)

알고리즘 복잡도

• 시간 복잡도 : 문제의 크기와 이를 해결하는데 걸리는 시간
• 공간 복잡도 : 문제의 크기와 이를 해결하는데 필요한 메모리 공간

big-O notation

알고리즘 복잡도를 표현할때 주로 이용

• O(n) : 원소의 크기에 비례하는 시간 소모
• O(1) : 원소의 크기에 상관없이 같은 시간 소모
• O(logn) : 원소의 크기의 로그에 비례하는 시간 소모