210122_TIL (시간복잡도, 자료구조 복습)

🍎 오늘 한 일

---

✔️ Big-O 표기법 & 자료구조 연관지어 생각해보기
빅오(Big-O) 표기법은 그냥 알고리즘이 돌아가는 최악의 시간이고, 상수..지수.. 등이 있다는 것, 그리고 대략 어떤 코드가 어느정도의 시간이 걸리는 구나 정도로만 알고 있었다. 빅오 표기법에 대해 좀 더 깊게 다루는 세션을 들으면서 자료구조와 어떻게 연관되는지도 자세히 배워 전에 블로깅 해뒀던 글에 추가했고, n^3의 시간도 빅오로 표시하면 n^2로 취급한다는 것, 그리고 코딩테스트 문제를 풀 때 시간복잡도에 대한 조건을 보고 어떤 자료구조를 써서 풀 수 있는 문제인지 역으로 힌트를 얻을 수 있다는 것도 알게 되었다.

✔️ Data Structure 복습
이번 주 동안 배웠던 자료구조들(스택, 큐, 연결리스트 ,해시테이블, 그래프, 트리, 이진탐색트리)을 한번씩 생각하면서 그려보고, 각 구조와 관련된 메서드들을 한번씩 더 복습하며 작성해봤다. 특히 해시 테이블은 모각코를 하면서 다른 분들은 어떤 식으로 코드를 작성했는 지 볼 기회가 있었는데, 보면서 정말 방법이 다양하구나 하고 느꼈다. 나는 bucket으로 객체를 사용하고 튜플은 그냥 속성과 값만 넣어줘서 { key1:val1, key2:val2 } 이런식으로 구현했는데, 어떤 분은 bucket을 배열로 사용해 [ {key1:val1}, {key2:val2} ] 이런식으로 하시기도 하고, 아예 객체 bucket 안에 객체 tuple을 넣어 { { key1: val1 }, { key2: val2 } } 이렇게 하신 분도 계셨다. 페어분과 처음 코드를 작성할 때도 배열이나 객체로 표현할수도 있겠다고 이야기만 하고 한가지 방법으로만 시도해봤었는데, 다들 코드를 공유해주신 덕에 실제 코드로 작성했을 때 어떤 모습인지 볼 수 있어 유익한 시간이었다 :)

 

🍎 기억할 것

---

✔️ 배열 메서드 시간복잡도
arr.filter : O(n)
arr.map : O(n)
arr.sort : O(n * log n)

✔️ 인접 행렬
num * num 저장공간 필요
인덱스를 직관적으로 관리하기 위한 방법 1) index를 1부터 시작해버리거나 2) (num+1) * (num+1) 배열로 관리할 수 있다.

 

🍎 더 공부할 것

---

✔️ Github 오류 해결
✔️ 깊이, 너비 우선 탐색
✔️ heap(우선순위큐)
✔️ 수식 파서 트리 글 읽어보기