kjp0411 님의 블로그

재귀 (Recursion)재귀는 그래프 탐색, 트리, DP(Dynamic Programming) 등 주요 자료구조와 알고리즘에 접목됩니다.재귀는 자신을 정의할 때, 자기 자신을 재호출하는 것을 의미합니다.재귀의 대표적인 예로는 팩토리얼과 피보나치가 있습니다. 재귀의 example팩토리얼(factorial)def factorial(n): if n == 1: return 1 return n * factorial(n - 1)피보나치(fibonacci)def fibo(n): if n == 1 or n == 2: return 1 return fibo(n - 1) + fibo(n - 2) 재귀의 수학적 접근앞선 factorial과 fibonacci를 보면 n 번째 함수..

해시 테이블 (Hash Table)Hash Table은 효율적인 탐색(빠른 탐색)을 위한 자료구조 입니다.key-value 쌍의 데이터를 입력 받고hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치를 지정하여key-value 데이터 쌍을 저장합니다. 저장, 삭제, 검색의 시간 복잡도는 모두 O(1) 입니다.Direct-address Table(직접 주소화 테이블)Direct-address Table은 key 값이 k인 데이터를 index k 위치에 저 장하는 방식입니다 .student[3] = "김사과"student[5] = "반하나"student[6] = "김체리"student[7] = "두리안"indexvalue0/1/2/3김사과4/5반하나6김체리7두리안8/ 하지만 직..

스택 (Stack)Stack은 시간 순서상 가장 최근에 추가한 데이터가 나오는 후입선출 LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조입니다.push : Stack의 top에 데이터를 추가하는 것pop : Stack의 top에서 데이터를 꺼내는 것List 기반 구현Python에서 Stack을 가장 간단하게 구현하는 방법은 list를 이용하는 것입니다.list의 append 메소드를 사용하면 맨 뒤에 데이터를 추가할 수 있으며list의 pop 메소드를 사용하면 맨 앞에 데이터를 꺼낼 수 있기 때문입니다.s = []# push O(1)s.append(1) # [1]s.append(2) # [1, 2]s.append(3) # [1, 2, 3]# pop O(1)s.pop() # [..

큐 (Queue)Queue는 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조입니다.enqueue : Queue의 rear(뒤)에서 데이터를 추가하는 것dequeue : Queue의 front(앞)에서 데이터를 꺼내는 것구현 방법으로는 List와 Linked List기반으로 구현할 수 있습니다.List 기반 구현Python에서 Queue를 가장 간단하게 구현하는 방법은 list를 이용하는 것입니다.list의 append 메소드를 사용하면 맨 뒤에 데이터를 추가할 수 있으며list의 pop 메소드에서 인덱스를 지정하여 사용하면 맨 앞에 데이터를 꺼낼 수 있기 때문입니다.q = []# enqueue O(1)q.append(1) # [1..

리스트 (List)List는 순서를 가지고 원소들을 저장하는 자료구조입니다.구현 방법으로는 Array List와 Linked List로 구현할 수 있습니다.Python에서 사용하는 list 자료구조는 Array List로 구현되어 있습니다.Array ListArray List는 배열을 기반으로 구성된 list 자료구조 입니다.구현 방법으로는 static array와  dynamic array로 구현할 수 있습니다.배열 Static array배열의 특성1. 고정된 저장 공간(fixed-size)2. 순차적인 데이터 저장(order)배열은 선언 시에 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를 연속적/순차적으로 저장하는 자료구조입니다.int arr[5] = {3, 7, 4, 2..