[TIL] 2주차_Day1: 자료구조/알고리즘 풀기(1)

💡Today I Learned

• 자료구조/알고리즘에 대한 첫번째 이론 및 실습 강의를 진행했습니다.
• 배열 / 정렬, 탐색, 재귀 알고리즘 / 알고리즘의 복잡도 관련 이론
• 리스트, 탐색, 재귀 알고리즘에 관한 실습 문제 풀이

---

1. 자료구조 & 알고리즘

- 자료구조 = data + data에 대해 행할 수 있는 연산

- 알고리즘: 주어진 문제를 해결하기 위한 자료구조와 연산 방법을 선택

- ex) List 내 특정 item을 찾을 때 → 정렬된 List에서 item을 찾는 것이 효율적 → 순서가 정렬된 자료구조가 좋겠음

 

2. 선형 배열

-  원소들을 순서대로 늘어놓은 것

- 0-based indexing

- (in python) List는 여러 타입의 자료를 함께 저장 가능

- 리스트 중간의 원소 삭제 방법 간 차이

1. del(L[idx]): 리스트 아이템 삭제
2. L.pop(idx): 삭제할 아이템 return & 삭제

 

3. 정렬

- 리스트 정렬 방법 간 차이

1. sorted(): 내장함수, 정렬된 새로운 리스트 return (원본 리스트의 변화 x)
2. sort(): 리스트의 메소드, 메소드를 호출한 해당 리스트를 정렬함 (원본 리스트의 변화 o)

- 정렬에 사용될 키 지정: key = lambda x: 매개변수 x에 대한 람다 함수로 구현

 

4. 탐색

- 선형 탐색(linear search): O(N)

- 이진 탐색(binary search):  O(logN), 탐색하려는 리스트가 이미 정렬돼있는 경우만 적용 가능

 

5. 재귀함수

- ex) 이진 트리, 조합의 수, 피보나치 수열 etc..

- 재귀 알고리즘 내 종결 조건이 반드시 필요

 

6. 알고리즘 복잡도

- Big-O notation: 입력 크기 N에 비례하는 알고리즘의 시간 소요, 계수는 중요하지 x (ex: O(kN^2) == O(N^2))

- 삽입 정렬(insertion sort): O(N^2)

- 병합 정렬(merge sort): O(N*logN)

 

---

📒 Furthermore

• 피보나치 수열 반복문으로 구현하기
• '하노이의 탑' 재귀 함수로 풀이