본문 바로가기

Algorithms9

Algorithms etc part2 (기타 알고리즘 파트2) In [6]: from IPython.core.display import display, HTML display(HTML("")) View Source 9. Algorithms ETC part2¶ Objective¶ Priority Queue & Heap Tree Data Structure Bellman Ford Algorithm Binary Indexed Tree (Fenwick Tree) Lowest Common Ancestor Algorithm (LCA) 1. Priority Queue & Heap (우선순위 큐와 힙)¶ 1-1. 우선순위 큐 (Priority Queue)¶ 우선순위 큐 는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 입니다. 데이터를 우선순위에 따라 처리하고 싶을 때.. 2022. 7. 6.
Algorithms etc part1 (기타 알고리즘 파트1) In [1]: from IPython.core.display import display, HTML display(HTML("")) View Source 11. Algorithms ETC part1¶ Objective¶ Erathosthenes's Sieve (에라토스테네스의 체) Two Pointers (투포인터 알고리즘) 순열과 조합 예시 문제 1. Erathosthenes's Sieve (에라토스테네스의 체)¶ 1-1. 소수(Prime Number)¶ 소수(Prime Number) 란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수 입니다. 1-2. 소수 판별 알고리즘¶ 소수 판별 알고리즘 문제들이 자주 출제 됩니다. 하나의 수에 대해 소수 판별하는 알고리즘은 .. 2022. 7. 3.
Graph Algorithms (그래프 알고리즘) In [1]: from IPython.core.display import display, HTML display(HTML("")) View Source Graph Algorithms (그래프 알고리즘)¶ Objective¶ 서로소 집합 알고리즘 서로소 집합 알고리즘을 통한 사이클 판별 Kruskal Algorithm Topology Sort Algorithm Graph Algorithm 예시 문제 1. 서로소 집합 알고리즘¶ 1-1. 서로소 집합 정의¶ 서로소 집합 (Disjoint Sets)란 공통 원소가 없는 두 집합 을 의미합니다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 입니다. 1-2. 서로소 집합 자료구조의 연산¶ Union : 2개의 원소.. 2022. 7. 1.
Shortest Path (최단경로 알고리즘) In [1]: from IPython.core.display import display, HTML display(HTML("")) View Source Shortest Path Algorithm (최단경로 알고리즘)¶ Objective¶ 최단경로 알고리즘 정의 및 특징 Dijkstra Algorithm Floyd-Warshall Algoritm 최단경로 알고리즘 예시 문제 1. 최단경로 알고리즘¶ 1-1. 최단경로 알고리즘 정의¶ 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘 을 의미합니다. 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 1-2. 최단경로 알고리즘 종류¶ Dijkstra Algorithm Floyd-Warshall Algorithm Bellman.. 2022. 6. 29.
Dynamic Programming (동적 계획법) In [1]: from IPython.core.display import display, HTML display(HTML("")) View Source Dynamic Programming (동적 계획법)¶ Objective¶ Dynamic Programming 특징, 정의, 방식, 유의사항 Dynamic Programming 구현 방법 Dynamic Programming 예시 문제 1. Dynamic Programming 특징, 정의, 방식, 유의사항¶ 1-1. Dynamic Programming 문제 특징¶ 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있습니다. 중복되는 부분 문제 (Overlapping.. 2022. 6. 27.
이진 탐색 알고리즘 (Binary Search Algorithm) In [1]: from IPython.core.display import display, HTML display(HTML("")) View Source Binary Search Algorithm¶ Objective¶ 이진 탐색 알고리즘 특징 이진 탐색 알고리즘 구현방법 이진 탐색을 활용한 Parametric Search 1. 이진 탐색 알고리즘의 특징¶ 정렬된 상태의 데이터에서 빠르게 탐색을 하기 위한 알고리즘 탐색 범위를 반으로 줄여가면서 실시하며 이는 연산 횟수가 $log{_2}{N}$ 의미한다. 따라서 시간복잡도는 O($log{N}$) 이다. 이와는 반대로 순차적으로 데이터를 하나하나 확인하는 방법은 순차 탐색(Sequential Search) 이며 시간복잡도는 O(N) 이다. 관련된 자료구조로는 .. 2022. 6. 22.
Sorting Algorithm In [1]: from IPython.core.display import display, HTML display(HTML("")) View Source Sorting¶ - 공간복잡도는 구현마다 달라집니다... 1. Selection Sort (선택정렬)¶ - iteration 을 돌때마다 제일 작은 원소를 선택 - 선택한 제일 작은 원소를 해당 iteration의 앞의 배치 - 최선 : O(N^2) - 평균 : O(N^2) - 최악 : O(N^2) In [5]: array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if ar.. 2022. 5. 1.
adjacent list vs adjacent matrix 프로그래밍 문제를 풀다보면 (특히 graph 관련 dfs, bfs 등을 활용한 탐색의 경우들) adjacent list 와 adjacent matrix 둘중 하나의 형태로 풀리는 경우가 많습니다. 저 같은 경우는 주로 시간제약 문제가 많은 관계로 adjacent list + bfs (or dfs) 로 문제를 많이 풉니다. 하지만 adjacent matrix 로 문제를 훨씬 더 빠르고 쉽게 경우도 있습니다. (가중치가 주어진 최단경로 등) 위와 같은 경우들을 위해 graph 를 표현하는 2가지 방법에 대해 정리합니다. 1. Adjacent list - Graph 에서 node 사이들의 관계를 나타내는 방법입니다. - python 에서의 구현 방법은 대락 2가지라고 생각할수 있습니다. 개인적으로 노드들의 데.. 2022. 4. 28.
[Python] List cannot be an element in a set; use Tuple You can't add a list to a set because lists are mutable, meaning that you can change the contents of the list after adding it to the set. Ref https://stackoverflow.com/questions/1306631/add-list-to-set 2022. 4. 23.

티스토리툴바