YS's develop story

👩‍💻 병합 정렬 (Merge Sort) 정리 with Python 🍳 병합 정렬 (Merge Sort)이란? 재귀 용법을 활용한 정렬 알고리즘입니다. 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눕니다. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬합니다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합합니다. Merge Sort는 Divide And Conquer의 대표적인 예시 알고리즘입니다. 🥘 병합 정렬 구현 with Python def mergeSort(data): if len(data) leftPoint and len(right) > rightPoint: if left[leftPoint] > right[rightPoint]: merged.append(right[rightPo..

👩‍💻 동적 계획법과 분할 정복 정리 with Python 🥘 동적 계획법 (Dynamic Programming) 동적 계획법, Dynamic Programming이란? 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 큰 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘 기법입니다. 상향식 접근법으로 가장 최하위 해답을 구한 후 이를 저장하고, 해당 결괏값을 이용해 상위 문제를 풀어가는 방식을 활용합니다. Memoization 기법을 활용합니다. Memoization (메모이제이션) : 프로그램 실행 시 이전에 계산한 값을 저장하며, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술입니다. 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됩니다. ..

👩‍💻 버블 정렬, 선택 정렬, 삽입 정렬 정리 with Python 🥘 버블 정렬 버블 정렬이란? 인접한 두 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 알고리즘입니다. Python 코드 def bubbleSort(list): swaped = False for index in range(len(list) - 1): for index2 in range(len(list) - index - 1): if list[index2] > list[index2 + 1]: list[index2], list[index2 + 1] = list[index2 + 1], list[index2] swaped = True if swaped == False: break return list 시간 복..

👨🏼‍💻 Graph (그래프) 정리 With Python 🥝 Graph 란? 실제 세계의 현상이나 사물을 Vertex(정점)와 Edge(간선)로 표현하기 위해 사용합니다. Vertex : 위치를 말합니다. Node라고 하기도 합니다. Edge : 위치 간의 관계를 표시한 선입니다. Degree : 방향이 없는 그래프에서 하나의 정점에 인접한 정점의 수입니다. Simple Path : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로입니다. (A-B-C는 Simple Path) Cycle : Simple Path의 시작 정점과 종료 정점이 동일한 경우입니다. 🍋 그래프의 종류 Undirected Graph 방향이 없는 그래프입니다. Edge를 통해 Vertex 양 방향으로 갈 수 있습니다. Dire..

👨🏼‍💻 Heap (힙) 정리 With Python 🥝 Heap 이란? 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)입니다. 완전 이진트리? Node를 삽입할 때 최하단 왼쪽 Node부터 차례대로 삽입하는 Tree 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n) 이 걸리지만 힙에 데이터를 넣고, 최댓값과 최솟값을 찾으면 O(logn) 이 걸리기 때문에 최댓값, 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘에 활용됩니다. 힙은 아래의 두 가지 조건을 가지고 있어야 합니다. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같습니다. 완전 이진트리 형태를 가집니다. 🍋 Heap VS Binary Search Tree 공통점..

👨🏼‍💻 Tree (트리) 정리 With Python 🥝 Tree란? Node와 Branch를 이용해서 Cycle을 이루지 않도록 구성한 데이터 구조입니다. 🍋 관련 용어 Node : 트리에서 데이터를 저장하는 기본 요소 Root Node : 트리의 최상위 노드 Level : 최상위 노드를 Level 0이라고 했을 때, 하위 Branch로 연결된 노드의 깊이를 나타냅니다. Parent Node : 어떤 노드의 부모 노드 Child Node : 어떤 노드의 자식 노드 Leaf Node : Child Node가 하나도 없는 노드 Sibling : 동일한 Parent Node를 가지는 노드 Depth : 트리에서 Node가 가질 수 있는 최대 Level (위 사진에서의 Depth는 2) 🍊 이진 탐색 트리 이..

👨🏼‍💻 Hash Table (해시 테이블) 정리 With Python 🥝 Hash Table이란? 키(key)에 데이터(Value)를 저장하는 데이터 구조입니다. Key를 통해 바로 데이터를 받을 수 있으므로, 속도가 매우 빠릅니다. 파이썬에서는 딕셔너리 타입을 사용하면 됩니다. 🍋 간단한 해시 예시 hashTable = [0 for i in range(20)] def hashFunction(key): return key % 8 def insertToHashTable(data, value): key = ord(data[0]) hashAddress = hashFunction(key) hashTable[hashAddress] = value def getFromHashTable(data): key = ord..