Repository files navigation

In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks. - Wikipedia.

수학과 컴퓨터 과학에서, 알고리즘은 일반적으로 어떤 집합의 문제를 풀기 위하거나 계산을 수행하기 위해, 잘 정의된 한 유한순서이자, 컴퓨터가 실행할 수 있는 지시사항들 입니다. 알고리즘은 항상 모호하지 않고, 계산이나 데이터 처리, 자동 추론 등등 여러곳에서의 명세로 사용됩니다.

• DFS - Recursion manner - O(V+E)

• BFS - Using Queue - O(V+E)

• Binary Search - Iterative manner - O(logn)

• Binary Search - Recursive manner - O(logn)

• Permutation - O(n!) 순열

• Power Set Problem - O(2^n) 모든 조합 나열

• N Queen Problem - N x N 격자판에 N개의 퀸이 서로 공격하지 않으면서 놓아지게 하는 법 구하기

• Rat In A Maze Problem - 미로찾기 문제

• Sudoku - 스도쿠, 숫자 퍼즐 문제

• Sum Of Subset - 집합에서의 원소들을 조합해서 특정 값을 만들 수 있는지? O(2^n)

• Pre Order, In Order, Post Order - 전위 순회, 중위 순회, 후위 순회 | 기본적인 트리의 순회 방법

• Center of a Binary Tree - 트리의 중심(1개 또는 최대 2개가 될 수 있다.)

• Height of a Binary Tree - 트리의 높이(루트노드로 부터 가장 깊은 잎 노드로의 경로에서의 노드 개수)

• Diameter of a Binary Tree - 트리의 지름(트리에서 가장 긴 경로의 노드 개수)

• Sum of Nodes - 트리에서의 노드들의 합

• Sum of Leaf Nodes - 잎 노드들의 합

• Dijkstra Algorithm - Priority Queue(Binary Heap) - Binary Heap 적용 O(E(logV)

• Dijkstra Algorithm - Min Indexed Heap - Indexed Priority Queue 적용 O(V(logV)

• Floyd Washall Algorithm - All Pair Shortest Path - 모든 쌍 최단경로 O(v^3)

• SPFA - Shortest Path Faster Algorithm - O(E) on Average. Not proved.해당 알고리즘 블로그 글 보기

• Bellman Ford - Adjacency List - O(VE)

• Bellman Ford - Edge List - O(VE)

• Shortest Path On DAG Using TopSort - 위상정렬 적용 후 위상순서에 따라 변 경감 연산 수행 O(V+E)

• Shortest Path On A Graph Using BFS - 그래프에서 모든 Edge의 가중치가 같은 상황에서의 최단경로 O(V+E)

• Quick sort - 빠른정렬, Worst case: O(n^2), Average case: O(nlogn) where n is the number of item in an array

• Merge sort - 병합정렬 O(nlogn), Worst case: O(nlogn) where n is the number of item in an array

• Counting sort - 카운팅 소트, 계수정렬, O(kn) where k is upper bound number, n is the # of items in an array

• Selection sort - 선택정렬 Worst case: O(n^2)

• Bubble sort - 버블소트 Worst case: O(n^2)

• Insertion sort - 삽입정렬 Worst case: O(n^2)

• Heap sort - 힙 정렬 Worst case: O(nlogn)

• Radix sort - 기수 정렬, Time Complexity: O(nw) n = 정렬될 키의 개수, w = 정렬될 키 중에서 가장 큰 자릿수

• Bucket sort - 버킷 소트

• Topological Sort - Using In Degree - Using In Degree, O(V+E)

• Topological Sort - Using DFS - Using DFS, O(V+E)

• Fibonacci - Bottom up Manner - n번째 피보나치 수열 구하기(반복적 방법), Iterative

• Fibonacci - Top Down Manner - n번째 피보나치 수열 구하기(재귀적 방법), Recursive + Memoization

• Maximum Sum Sub array(Kadene's Algorithm) - 배열에서의 연속된 부분배열의 최대 합, O(n)

• Coin Change Problem 1 - 주어진 종류의 코인으로 특정 금액을 만드는데 드는 가능한 최소의 동전 수 (동전의 개수는 무한)

• Coin Change Problem 2 - 주어진 종류의 코인으로 특정 금액을 만들 수 있는 경우의 수(조합의 수) (동전의 개수는 무한)

• 0 1 Knapsack - 물건의 수량이 최대 1개인 배낭 문제

• Unbounded Knapsack - 물건의 수량이 제한 없는 배낭 문제

• LCS(Longest Common Subsequence) - 최장 공통 부분 순서(Compare with 3 Strings), Bottom Up Manner O(n^3)

• LCS(Longest Common Substring) - 최장 공통 부분 문자열(Compare with 2 Strings), Bottom Up Manner O(n^2)

• LIS(Longest Increasing Subsequence) - 최장 증가 부분순서, Bottom Up Manner O(n^2)

• Maximum Sub Square Matrix of 1 - 1로 이루어진 가장 큰 정사각형 부분 행렬 구하기

• 격자 경로 문제

• Stair Case Problem N번 계단 까지 올라가는 방법의 수

• Tiling Dominoes - 타일링 문제, e.g 2 x N or 3 x N and so on

• Edit Distance - 편집거리

• Longest Palindrome Subsequence - 최장 팰린드롬 부분순서

• Josephus Problem - 조세퍼스 문제

• Mountain Scenes - Problem Link :Click Here

• Magical Cows - Problem Link :Click Here

• Tiling Dominos - Problem Link :Click Here

• Sieve Of Eratosthenes - 에라토스테네스의 체

• GCD - 최대공약수

• LCM - 최소공배수

• Permutation - 순열 nPr, 순서화

• Permutation Using Swap - 순열 nPn, 비순서화

• Combination - 조합 nCr

• Combination With Repetition - 중복 조합

• Kruskal's Algorithm - 가능한 가중치가 가장 작은 간선으로 시작해 N-1개의 간선을 선택하는 Greedy Algorithm

• Prim's Algorithm

• Ford-Fulkerson method - 최대유량 알고리즘

• Edmonds Karp Algorithm - 최대유량 알고리즘, Ford Fulkerson method에서의 탐색방법을 BFS로 적용

• Min Cost Max Flow - 최소비용 최대유량 알고리즘, 최소비용에는 SPFA Algorithm, 최대비용에는 Edmonds Karp Algorithm 적용

• Bipartite Matching - DFS Manner

• Tarjan's Algorithm - O(V+E)

• Kosaraju's Algorithm - O(V+E)

• Cut Edge - O(V+E)

• Articulation Point - O(V+E)

• Cycle Detection in a Directed Graph - 방향 그래프에서의 사이클 탐지, DFS 사용 - O(V+E)

• Cycle Detection in an UnDirected Graph - 비방향 그래프에서의 사이클 탐지, 유니온 파인드 사용 - O(V+E)

• LCA - Euler Tour + Sparse Table(RMQ) Euler Tour = O(n), Construction of Sparse Table = O(nlogn), LCA Query = O(1)

• LCA - Naive Approach LCA Query = O(n)

• KMP Pattern Matching Algorithm - KMP(Knuth, Morris, Pratt) 패턴 매칭 알고리즘, O(n+m) where n is pattern matching and m is LPS construction (LPS : Longest Proper Prefix which is also Suffix)

• Boyer Moore Algorithm - Using Bad Character Rule

• Rabin Karp Algorithm

• Count Inversions In An Array - 인덱스 위치가 i < j 이면서 A[i] > A[j]인 원소들을 역전관계라고 한다. 역전관계의 원소들이 해당 배열안에 몇개나 있는지 찾는 알고리즘. 머지소트를 이용한다. O(nlogn), Naive Approach : O(n^2)

In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. - Wikipedia

• Implementation - Using LinkedList

• Implementation - Using LinkedList

• Linked List

• Implementation

• Implementation

• Implementation - Binary Heap

• [Implementation]

• Implementation

• Implementation

• Implementation

• Implementation

• Segment Tree - Range Sum Query - Construction : O(n), Update: O(logn), Min Query : O(logn)

• Segment Tree - Range Minimum Query - Construction : O(n), Update: O(logn), Min Query : O(logn)

• Fenwick Tree - Range Sum Query - Construction : O(n), Update: O(logn), Sum Query : O(logn)

• Sparse Table - Range Minimum Query - Construction : O(nlogn), Min Query : O(1)

• Implementation

• Use Case