🤖 Computer Science/Algorithm

컴퓨터 과학에서는 알고리즘의 복잡도를 나타내는 데 $$T(n), O, \Theta, \Omega$$ 등의 표기법을 사용한다. 이러한 표기법은 알고리즘의 실행 시간이나 공간 요구사항의 상한, 하한, 또는 정확한 경계를 지정한다. 이러한 표기법을 빅 오 표기법이라고도 하며, 각각은 다음과 같은 의미를 가진다. Big O 표기법 (O): 함수의 상한을 설명한다. ( O(g(n)) )은 함수 ( f(n) )이 ( c \times g(n) )을 초과하지 않음을 의미한다. 이는 주로 최악의 경우 성능을 나타내는 데 사용된다. Theta 표기법 ((\Theta)): 함수의 정확한 성장률을 나타낸다. ( \Theta(g(n)) )은 ( f(n) )이 ( c_1 \times g(n) )과 ( c_2 \times g(..

겹치는 하위 문제(Subproblem)를 해결하고 그 결과를 저장해 나가는 방식으로 최적화 문제들 특징1. 작은 하위문제들이 반복적으로 발생하며, 이들의 해결 결과가 재활용될 수 있을 때 2. Optimal Substructure(최적부분구조)을 갖춘 문제. 큰 문제의 최적해가 작은 문제의 최적해를 통해 구할 수 있을 때 3. 중복된 계산을 최소화할 수 있는 구조. 같은 하위 문제를 반복해서 해결해야 할 때 하위문제가 독립적, 줄여가면서 해결 -> Divide & Conquer 하위문제가 중첩됨, 반복해야 함 -> Dynamic Programming DP로 해결하는 대표적인 문제들longest common subsequenceKnapsack problemRod cutting problemshortest ..

ascending order로 정렬하는 qseudocode는 다음과 같다. (index가 1부터 n까지라고 가정했을 때) INSERTION-SORT(A, n) -> A[1 .. n] for j

DFS/BFS 를 위한 자료구조 기초 : 스택, 큐, 재귀함수탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정대표적인 탐색 알고리즘 DFS, BFS - 기본 자료구조인 스택과 큐에대한 이해 필요  스택스택 : 선입후출파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요가 없다.기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.append() 메서드는 리스트의 가장 뒤쪽에 삽입, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터 꺼내기 때문  큐큐 : 선입선출collections 모듈에서 제공하는 deque 자료구조를 활용하자.deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며que..