Today, I Learned

• 알고리즘 시간 복잡도 : 시간 복잡도란, 나만의 정의로 표현해보면, 자료의 크기의 증가에 따라 자료에 대해 작업을 하는 시간이 증가하는 정도(비례 정도)로 표현해볼 수 있다. 그래프를 하나 떠올렸을 때, 가로축에는 자료의 크기(n)이 있고, 세로축에는 시간이 있다고 가정해보면, 자료의 크기(가로축) 늘어날수록(오른쪽으로 갈수록), 시간(세로축)이 어떤 양상으로 변하느냐에 따라 시간 복잡도가 결정된다. 예를 들어, 자료의 크기가 커져도 시간이 변하지 않는다면, 즉, 그래프의 기울기가 0이라면, 그 알고리즘의 시간 복잡도는 O(1)로 표현할 수 있다. 즉, 아무리 많은 자료를 바탕으로 작업을 수행해도, 수행을 완성하는 데 걸리는 시간이 일정하다는 것이다. 이와 달리, 자료의 크기가 증가할 때(n), 증가분 만큼 시간도 증가하는 알고리즘의 시간 복잡도를 O(n)이라고 한다. 이는 기울기가 1인 그래프를 떠올리면 된다. 그리고, 자료의 크기가 n씩 커짐에 따라 시간은 n**2만큼 커지는 알고리즘도 있는데 이는 O(n**2)의 시간 복잡도를 지니는 알고리즘이다. 이와 달리, 예를 들어, 이진 탐색과 같이 O(logn)의 시간 복잡도를 가지는 알고리즘도 있다.( 정리 링크 )
• Binary Search Tree, Tree, Linked List, Array라는 자료구조들의 추가, 조회, 제거, 탐색 작업을 보면서 어떤 자료구조가 어떤 시간 복잡도를 갖는지를 공부했고, 프로그래머는 어떤 상황에서 어떤 자료구조를 써야 가장 효율적인 알고리즘을 짤 수 있는지를 알아야 한다는 것을 이론적, 현실적으로 이해할 수 있었다.( 정리 링크 )
• 알고리즘 복잡도는 n이 몇이냐에 따라 다른 것임. 예를 들어, Big O Notation을 생각했을 때, 무조건 O(n**3)이 안좋다고 생각하면 안되고, n이 몇이냐에 따라 다른 것임. O(n)도 n이 100억개라면 안좋은 알고리즘인 것임[O(n**2)에서 n이 500만에서 1000만 정도되면 안좋은 단계라고 생각하면 됨]. 그러나, O(1)이 제일 좋다는 건 변하지 않음! + 보통 코딩테스트에서 O(nlogn), O(logn), O(1)이면 사실상 다 풀었다고 생각하면됨. 그러나, n제곱일 때도, 500만부터 1000만 이하면 요구 사항에 부합할 것이기에 고려를 해봐야함. 결론 : 외우면 안되고, 상황에 적합한 것을 적용해야함!
• 프로그래머는 항상 '최악'의 케이스를 고려해야한다. 유저들도 이상한 행동(?)을 하는 유저를 항상 고려해줘야 한다. 알 수 없는 인풋을 넣을 수 있는 유저들을 고려하여 프로그래밍을 해야한다는 것!