220919 Today I Learned (TIL)

 

오늘 한 일

---

1. 블랙잭 만들기 시도 → 미완성
2. 알고리즘과 자료구조 2주차 수강
3. 거북이 스터디

배열 (Array)

---

• 특징
  1. 고정된 크기를 갖는다.
  2. 각 원소에 즉시 접근할 수 있다. ex) rooms[0] 이때, 원소의 순서는 0부터 시작하고 이를 인덱스라고 부른다.
  3. 즉시 접근 가능하기 때문에 상수 시간 내에 접근할 수 있다.
  4. 배열은 원소를 중간에 삽입하거나 삭제할 때 모든 원소를 다 옮기기 때문에 O(N)의 시간 복잡도를 가진다.
  5. 새로운 공간을 할당함으로써 원소를 새로 추가한다. -> 비효율적
  6. 파이썬의 list의 경우 배열이지만 링크드 리스트처럼 쓸 수도 있는 효율적인 자료구조다.
•  

링크드 리스트(Linked List)

---

• 특징
  1. 각 원소를 노드라고 부르고, 노드 간 연결 고리를 포인터라고 부른다.
  2. 노드는 $1)$칸에 있는 데이터와 $2)$다음칸이 뭔지 가리키는 포인터, 이 두가지를 필요로 한다.
  3. 데이터의 공간이 고정적이지 않으므로, 포인터로 이어줌으로써 자유롭게 노드를 늘리거나 줄일 수 있다.
  4. 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 하기 때문에 O(N)의 시간 복잡도를 가진다.
  5. 리스트는 원소를 중간에 삽입/삭제하려면 앞 뒤의 포인터만 변경하면 된다.
  6. 따라서 원소 삽입/삭제 시 O(1)의 시간 복잡도를 가진다.

 

이진 탐색

---

1. 범위를 절반씩 나누어 데이터를 탐색하는 방식 ↔ 순차 탐색
2. 순차 탐색은 O(N)의 시간 복잡도를 가지지만, 이진 탐색은 O(logN)의 시간 복잡도를 가진다.

 

재귀 함수

---

1. 재귀(Recursion) : 어떤 걸 정의할 때 자기 자신을 참조하는 것, 즉 재귀 함수는 자기 자신을 호출하는 함수
2. 재귀함수는 반드시 빠져나가는 지점, 탈출 조건을 지정해 주어야 한다.

기타

---

1. 같은 클래스 내부에 있는 다른 함수를 부르기 위해서는 self.함수 이름으로 호출하면 된다.