Big-O 표기법 (1) 기본 원칙, 배열(ArrayList), 재귀함수, 이진트리(Binary Tree, BT)에서의 Big-O
알고리즘 문제를 풀다보면 big-O notation을 통해 시간복잡도, 공간복잡도를 계산하곤 합니다. 저는 대략적인 호출 수, for loop, 캐싱 등을 염두에 두고 계산하곤 했는데요, CTCI(Cracking the Code Interview)책을 읽다 보니 recursion, string, binary tree 등에서 보다 정확한 Big-O Notation에 대한 부분이 있어 정리해두려고 합니다. 01. big-O 표기법이란? big-O 표기법은 N에 따라 수행시간이 어떻게 변화하는지를 표현해주는 도구입니다. 두 big-O 표기법 중 어떤게 더 수행시간이 빠른지를 비교하는것이 아닙니다! 즉, big-o 표기로 더 크다고 해서 항상 더 느린 것은 아닙니다. 입력과 연산에 따라 O(N) 코드가 O(1)..
Longest Increasing Subsequence | LeetCode 810 | Python3 🐍
📄 목차 🤔 문제 : Longest Increasing Subsequence | LeetCode 810 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/810/ 주어진 리스트 내 가장 긴 increasing subsequence 의 길이를 찾는 문제입니다. subsequence 란 배열에서 몇개의 요소를 삭제해서 만들 수 있는 sequnce를 말합니다. (순서는 바꾸지 않습니다) 예를들어, [2, 1, 3]의 subsequence는 아래와 같습니다. [2, 1, 3], [2, 1], [2, 3], [1, 3], [2], [1], [3], [] increasing subs..
