TIL(24) 21-10-20 : 구현, Linked List, 이진 탐색, 재귀

Facts

✅ 구현 11문제

✅ Linked List 2문제

✅ 이진 탐색 3문제

✅ 재귀 1문제

 

Findings

배열과 링크드 리스트의 장단점

배열

• 배열은 크기가 정해진 데이터 공간이다. 
• 인덱스를 통해, O(1)내에 접근할 수 있다.
• 배열은 원소를 중간에 삽입/삭제하려면 모든 원소를 다 옮겨야 한다.
  최악의 경우, 배열의 길이 N만큼을 옮겨야 하므로, O(N)의 시간복잡도를 가진다.

링크드리스트

• 링크드리스트는 크기가 정해지지 않는 데이터 공간이다.
  포인터로 이어주기만 하면, 자유자재로 늘어날 수 있다.
• 링크드리스트는 특정 원소에 접근하려면 포인터를 따라 탐색해야 한다.
  최악의 경우에는 모든 화물 원소를 탐색해야 하므로 O(N)의 시간 복잡도를 가진다.
• 링크드리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞뒤의 포인터만 변경하면 된다.
  원소 삽입/삭제를 O(1)시간 복잡도 안에 할 수 있다.

→ 데이터에 접근하는 경우가 빈번하면 배열, 삽입과 삭제가 빈번하면 링크드리스트를 사용하는게 좋다.

Python의 List

🤔 Python의 배열은 list라고 부르고 append를 막 하는데, Python의 list는 linkedlist일까? array일까?

❗️ Python의 list 는 array로 구현되어 있다.

🤔 그러면 append 메소드를 쓰면 새로운 배열을 생성해서 되게 안 좋은 거 아닌가?

❗️ 내부적으로 동적 배열이라는 걸 사용해서,

      배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리도록 설계되어있다.

→   파이썬의 list는 링크드 리스트로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조다!

 

Feelings

알고리즘과 친해지자 💭

앞으로 코드를 짤 때, 효율적으로 짜기 위해서, 알고리즘 문제 푸는 과정을 즐기기 🥳

 

출처

Dynamic array - Wikipedia