📚 알고보면 알기쉬운 알고리즘
✳ 2주차 ❇
✔ Linked List
▶ 크기가 정해지지 않은 데이터의 공간
모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.
| Array | Linked List | |
|---|---|---|
| 특정 원소 조회 | O(1) | O(N) 데이터 전부 건드림 |
| 중간 삽입/삭제 | O(N) 데이터 전부 건드림 | O(1) 포인터만 |
| 데이터 추가 | 새로 할당 | 노드만 추가 |
| 사용처 | 접근 빈번 | 삽입/삭제 빈번 |
python의 경우 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계되어 있음.
링크드 리스트로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조!
✔ 이진 탐색
▶ 반절씩 범위를 좁혀가면서 탐색
의 시간 복잡도를 가지는 순차 탐색과 다르게 만큼의 시간 복잡도가 걸린다.
k번 탐색하면 반절이 줄어드니 개가 남고, 횟수를 시도하면 정답을 찾을 수 있다.
✔ 재귀 함수
▶ 자기 자신을 호출하는 함수
범위를 좁혀갈 수 있다면 재귀 함수를 활용해보기!
but 탈출 조건을 항상 생각해 주어야 한다.
