Recursive Function, 재귀함수 : 하나의 함수에서 자기 자신을 다시 호출하는 함수 귀납적 사고 어떤 문제를 재귀로 푼다는 것은 귀납적인 방식으로 문제를 해결하겠다는 것이다. 1번 도미노가 쓰러진다. k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다. 위 조건 두 가지만 생각한 후 바로 "모든 도미노가 쓰러진다"라는 사고로 이어져야 한다. 귀납법 개별적인 특수한 사실이나 현상에서 그러한 사례들이 포함되는 일반적인 결론을 이끌어내는 또는 역으로 보편성에서 구체성을 유도하는 추론 형식 · 추리 방법 절차지향적 사고 vs 귀납적 사고 def recursive(n): if n == 0: # base condition return print(n) recursive(n-1) 절차지향적 사고 recurs..
hashing 된 맵, 해싱 함수를 사용하여 key와 value 쌍으로 데이터를 보관하는 맵 자료구조 특성 순차적으로 데이터를 저장하지 않는다. key를 통해 value 를 얻는다. value값은 중복가능하지만 key는 중복될 수 없다. 수정 가능(mutable)하다. 시간복잡도 삽입 : O(1) 탐색 : O(1) Dictionary ### 선언 및 초기화 d = {} d = {'alice': 1, 'bob': 20, 'tony': 15, 'suzy': 30} d = dict() d = dict(alice = 5, bob = 20, tony = 15, suzy = 30) # 컴프리헨션 초기화 num_d = {key: 0 for key in range(10)} # {0: 0, 1: 0, 2: 0, 3: 0..
먼저 들어간 데이터가 먼저 나오는 FIFO (First In First Out)의 성질을 가진 자료구조 특성 삭제 연산이 수행되는 곳을 front, 삽입연산이 수행되는 곳을 rear 라 한다. 요소는 rear로 들어와서 front로 빠진다. 접근은 가장 첫 원소와 끝 원소만 가능하다. rear에서 수행되는 삽입연산을 enQueue, front에서 수행되는 삭제연산을 deQueue라 한다. 시간복잡도 삽입/삭제 : O(1) 탐색 : O(n) Queue 사용 with Python # 데이터 흐름: 왼쪽방향 queue = [1, 2, 3] # enQueue queue.append(4) # queue = [1, 2, 3, 4] # deQueue queue.pop(0) # 1 반환, queue = [2, 3, 4..
가장 마지막으로 들어간 데이터가 먼저 나오는 LIFO(Last In First Out)의 성질을 가진 자료구조 특성 top으로 정한 곳을 통해서만 접근이 가능하다. top 은 가장 위에 있는 요소를 가리키며, 삽입되는 새 요소는 top 위에 쌓인다. top이 가리키는 요소가 추출/삭제된다. 삽입 연산을 push, 추출 연산을 pop이라 한다. 시간복잡도 삽입/삭제 : O(1) 탐색 : O(n) Stack 사용 with Python stack = [1, 2, 3] # push stack.append(4) # stack = [1, 2, 3, 4] # pop stack.pop() # 4 반환, stack = [1, 2, 3] # top stack[-1] # 마지막 인덱스의 데이터 = 제일 위에 있는 데이터 = 3
알고리즘의 성능을 평가하는 요소로 복잡도 (Complexity)를 사용한다. 복잡도에는 시간복잡도와 공간복잡도가 있으며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을수록 좋은 알고리즘이라 한다. 시간복잡도 (Time Complexity) : 특정한 크기의 입력에 대한 알고리즘의 수행시간 분석 공간복잡도 (Space Complexity) : 특정한 크기의 입력에 대한 알고리즘의 메모리 사용량 분석 시간복잡도 빅오 표기법 최상 (Big-Ω Notation), 평균 (Big-θ Notation), 최악 (Big-O Notation)의 세 표기법 중 최악의 경우를 계산하는 방식인 빅오표기법으로 경우를 판단하여 평균과 가까운 성능을 예측하는 방식 O(1) (Constant) 입력 데이터의 크기에 상관..
