Algorithm

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 & BFS - 깊이우선탐색 & 너비우선탐색

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

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

Binary Search - 이분탐색

• Binary Search - Iterative manner - O(logn)

• Binary Search - Recursive manner - O(logn)

Back Tracking + Brute Force - 백트래킹 + 전체탐색 다 해보기

• 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)

Tree Algorithm - 트리 알고리즘

• 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 - 잎 노드들의 합

Shortest Path - 최단경로 알고리즘

• 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)

Sorting - 정렬

• 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 - 위상정렬

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

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

Dynamic Programming - 동적 프로그래밍 (잘 알려진 문제들)

• 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 - 조세퍼스 문제

Dynamic Programming - 동적 프로그래밍 (추가)

• Mountain Scenes - Problem Link : Click Here

• Magical Cows - Problem Link : Click Here

• Tiling Dominos - Problem Link : Click Here

Prime - 소수

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

GCD, LCM - 최대공약수, 최소공배수

• GCD - 최대공약수

• LCM - 최소공배수

Permutation & Combination - 순열과 조합

• Permutation - 순열 nPr, 순서화

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

• Combination - 조합 nCr

• Combination With Repetition - 중복 조합

Minimum Spanning Tree Algorithm - 최소 신장 트리 알고리즘

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

• Prim's Algorithm

Network Flow - 네트워크 유량

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

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

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

Bipartite Matching - 이분매칭

• Bipartite Matching - DFS Manner

Strongly Connected Component - 강한 연결 요소

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

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

Cut Edge and Articulation Point - 단절선과 단절점

• Cut Edge - O(V+E)

• Articulation Point - O(V+E)

Cycle Detection Algorithm in a graph - 그래프에서의 사이클 탐지

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

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

LCA - 최소 공통 조상

• 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)

String Pattern Matching - 문자열 패턴 매칭

• 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

Other Algorithm

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

Data structure

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

Queue - 큐

• Implementation - Using LinkedList

Stack - 스택

• Implementation - Using LinkedList

Linked List - 연결 리스트

• Linked List

Graph - 그래프

• Implementation

Set - 집합 (중복된 원소를 허용하지 않는 자료구조)

• Implementation

Priority Queue / Heap - 우선순위 큐 / 힙

• Implementation - Binary Heap

Indexed Priority Queue / Indexed Heap - 인덱스 우선순위 큐 / 인덱스 힙

• [Implementation]

Dynamic Array - 동적 배열

• Implementation

Disjoint Set - Union Find by Rank with Path Compression - 서로소 집합

• Implementation

Tree - 트리

• Implementation

Binary Search Tree - 이진탐색트리

• Implementation

Segment Tree - 세그먼트 트리

• 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 or Binary Indexed Tree - 펜윅트리

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

Sparse Table

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

Trie or Prefix Tree - 트라이, 접두사 트리

• Implementation

Bit Manipulation - 비트 조작

• Use Case