YS's develop story

👩‍💻 다익스트라 알고리즘 정리 with Python 🥝 다익스트라 알고리즘 (Dijkstra Algorithm)이란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제(가중치 합이 최소가 되도록 하는 경로를 찾는 문제)에서 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 알고리즘입니다. 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법입니다. 우선순위 큐를 활용하여 다익스트라 알고리즘을 구현해 보겠습니다. 1. 초기화 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장합니다. 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장합니다. (inf라고 표현함) 우선순위 큐에 (첫 정점, 거리 0)만 먼저 넣습니다. 2. 우선순위 큐에..

👩‍💻 그리디 알고리즘 (탐욕법) 정리 with Python 🥝 그리디 알고리즘 (Greedy Algorithm)이란? 1. 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식입니다. 2. 각각의 선택은 그 순간 보았을 때는 가장 좋아 보이지만 나중에는 최적의 해가 아닐 수 있습니다. 3. 즉 매 순간의 선택은 locally optimal 하지만 globally optimal하지 않습니다. 그렇기에 그리디 알고리즘으로 최적해를 얻을 수 없는 것이 존재합니다. 🍋 그리디 알고리즘 예시 1 - 동전 문제 지불해야 하는 값이 7870원 일 때 가장 적은 수의 돈으로 지불하는 방법을 그리디 알고리즘을 활용하여 구할 수 있습니다. 가장 큰돈부터 최대한 지불해야 하는 값을 채우..

👩‍💻 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS) 정리 with Python 🥘 너비 우선 탐색 (Breadth-First-Search) Node 같은 레벨에 있는 Node들 (형제 Node들)을 먼저 탐색하는 방식입니다. 파이썬을 이용한 그래프 표현 코드 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I'] 너비..

👩‍💻 순차 탐색(Sequential Search)과 이진 탐색(Binary Search) 정리 🥘 순차 탐색(Sequential Search) 데이터가 담겨있는 리스트를 앞에서부터 하나씩 살펴보아서 원하는 데이터를 찾는 방법입니다. 🍀 순차 탐색 코드 def sequentialSearch(list, search): for index in range(len(list)): if list[index] == search: return True return False ☘️ 순차 탐색 시간 복잡도 찾고자 하는 값이 리스트의 맨 마지막에 있을 때, 리스트의 길이만큼 데이터를 비교해야 합니다. 따라서 시간 복잡도는 O(n)입니다. 🍳 이진 탐색 (Binary Search) 탐색할 데이터를 정확히 반으로 나누어 한쪽에..

👩‍💻 퀵 정렬 (Quick Sort) 정리 with Python 🥘 퀵 정렬 (Quick Sort)이란? 🌸 정렬 알고리즘의 꽃, Quick Sort 기준점 (Pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성합니다. 나누어진 왼쪽, 오른쪽 데이터를 재귀 용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복합니다. 함수는 왼쪽, Pivot, 오른쪽을 리턴하게 됩니다. Divde And Conquer 기법을 사용하는 대표 알고리즘 중 하나입니다. 🍳 퀵 정렬 구현 with Python # QuickSort def quickSort(list): if len(list) = pivot] return quickSort(left) + [pivot] + quick..

👩‍💻 병합 정렬 (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 시간 복..

알고리즘 ) 동적 계획법과 플로이드 알고리즘 동적 계획법, Dynamic Programming 동적 계획법의 원리는 매우 간단합니다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 문제를 푸는 것입니다. Step 1 : 문제의 답을 구하기 위한 recursive property를 세운다. Step 2 : bottom-up 방식으로 작은 문제들을 먼저 풀면서 최종 문제를 풀겠다. 동적 계획 알고리즘은 최단경로 문제, 행렬의 제곱 문제 등의 최적화에 사용됩니다. 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그중에 최적의 풀이법을 찾아내기 때문이죠. 플로이드의 최단 경로 알고리즘 플로이드 알고리즘은 각각의 정..

알고리즘 ) 분할 정복법 알고리즘의 해결전략 Divide and Conquer를 분할 정복법이라고 합니다. 분할 정복법은 주어진 문제를 작은 사례로 나누어(Divide) 각각의 작은 문제들을 해결(Conquer)하는 방법입니다. 프랑스의 황제 나폴레옹이 전투에서 사용했던 훌륭한 전략에서 이름을 따왔다고 하네요. 나누어라, 그리고 정복하라.. 멋있는 말입니다... Merge Sort Best Case 시간복잡도 : O(n log n) Worst Case 시간복잡도 : O(n log n) 분할 단계 array를 두 개의 subarrays로 나눕니다. 정복 단계 각각의 subarray가 충분히 작다면 바로 정렬 합니다. 그렇지 않다면 재귀를 통해 각각을 정렬합니다. 결합 단계 정렬된두 개의 subarray를 ..