[Algorithm] 알고리즘 공부
1.[Algorithm] 선택 정렬(Selection Sort)
선택 정렬이란? 가장 작은 것을 선택하여, 계속해서 앞으로 보내주는 방법(원래 앞에 있던 숫자와 자리를 바꿔줌) 시간 복잡도 만약 10개의 요소가 담긴 배열을 선택 정렬을 사용하여 정렬할 땐, [처음 10번 + 9번 + 8번 + 7번 + 6번 + ... + 1번] 즉, 등차수열이다. 즉 N개의 요소를 선택정렬 할 때 필요한 수행시간은 [N * (N+1)...
2.[Algorithm] 버블 정렬(Bubble Sort)
버블 정렬이란? 바로 이웃한 두 수를 비교하여, 작은 값을 앞으로 보내는 방법. 가장 효율성은 떨어지는 알고리즘이다. 시간 복잡도 1번 반복할 때 마다, 비교하는 요소가 하나 씩 줄어든다. 10개의 요소를 버블 정렬을 통해 정렬 할 때는, 10번 + 9번 + 8번 + ... + 1번 의 연산이 필요하고, 이는 등차수열이므로, [N * (N + 1) / 2...
3.[Algorithm] 삽입 정렬(Insertion Sort)
삽입 정렬이란? 각 숫자를 적절한 위치에 삽입하는 방법이다. 필요할 때만 위치를 바꿔주는 방법이다. 각 숫자를 삽입할 위치를 살펴 볼 때, 그 숫자의 앞의 숫자들은 모두 이미 정렬된 상태이다. 따라서 필요한 만큼만 이동할 수 있기 때문에 선택정렬과 버블정렬에 비해 빠르다. 시간 복잡도 최악의 경우(앞의 숫자들이 모두 정렬되지 않은 경우)는 선택 정렬, ...
4.[Algorithm] 퀵 정렬(Quick Sort)
퀵 정렬이란? 정렬해야하는 요소들을 분할시켜서 정렬하는 방법. 특정한 값을 기준으로, 큰 수와 작은 수를 반으로 나눠(두 집합으로) 정렬하는 방법이다. 퀵 정렬은 pivot(기준 값) 을 사용한다.(보통 가장 앞의 값을 pivot 값 으로 설정한다) pivot값을 기준으로, pivot 값 왼편은 pivot 값 보다 작은 집합. 오른편은 pivot 값 보...
5.[Algorithm] 병합 정렬(Merge Sort)
병합 정렬이란? 분할 정복 방법을 사용하는 정렬이다. 정확하게 반 씩 나누면서 정렬한다. 먼저 반으로 나눈 뒤, 나중에 합쳐서 정렬한다. 모든 요소가 자기 자신만 남을 때 까지 반으로 나눈다. 그 다음 인접한 두 수끼리 합친다.(각각 숫자 2개씩) 합치면서 두 수를 비교하여 정렬한다. 그 후 인접한 두 집합(각각 2 수를 가진 집합. 총 4개의 수를 ...
6.[Algorithm] 힙 정렬(Heap Sort)
힙 정렬이란? 힙 트리 구조를 이용하는 정렬방법이다. 힙이란 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대힙과 최소힙이 존재한다. 최대힙이란 부모 노드가 자식 노드보다 큰 힙이다. 만약 중간의 노드 때문에 최대 힙의 조건이 만족 되지 않는다면(아래의 예시 중 5 때문에 최대힙 조건이 만족되지 않는다.)...
7.[Algorithm] 계수 정렬(Counting Sort)
계수 정렬이란? 범위 조건이 있을 때, 매우 빠른 정렬 알고리즘이다. 크기를 기준으로 갯수를 세는 방법이다. 예를 들어 1 3 1 5 1 3 4 4 7 가 있을 때, 1의 개수를 세서 정렬, 2의 개수를 세서 정렬... 이런식으로 하는 것이다. 시간복잡도 모든 데이터의 크기를 메모리에 표현만 할 수 있다면, 각 데이터당 한 번씩만 접근하기 때문에 시간복...
8.[Algorithm] 스택(Stack) & 큐(Queue)
스택이란? 넣은 순서가 1, 2, 3, 4, 5 라고 한다면, 꺼낼 때 5, 4, 3, 2, 1 순으로 꺼내는 방법인 자료구조(짐 정리 처럼, 가장 나중에 넣은 짐을 가장 먼저 꺼낼 수 있다고 생각하면 편하다) 즉, 입구와 출구가 하나인 경우이다. 일반적으로 알고리즘
9.[Algorithm] BFS(너비 우선 탐색)
BFS란? 너비 우선 탐색(Breadth First Search)는 너비를 우선으로 탐색하는 방법이다. 탐색을 시작하는 곳에서 가까운 부분부터 탐색을 한다는 의미이다. 최단 경로를 찾아주는 탐색방법이며, 큐를 사용한다. BFS 원리 먼저, 탐색을 시작하는 부분(node)를 큐에 넣어준다. 한 번이라도 큐에 들어간 node는 방문했다는 표시를 해준다. ...
10.[Algorithm] DFS(깊이 우선 탐색)
DFS란? 깊이 우선 탐색(Depth First Search)는 깊은 것을 우선적으로 탐색하는 방법이다. 스택을 사용한다. DFS원리 먼저 시작 node를 스택에 넣어주고, 방문처리를 해준다. 그 후, 아래의 과정을 반복한다. 스택의 가장 위에 있는 node(가장 최근에 들어온 node)를 확인한다. 그 node의 인접 node 중 방문하지 않은 no...
11.[Algorithm] Union-Found(합집합 찾기)
Union-Found 란? 대표적인 그래프 알고리즘이다. 여러개의 노드가 존재할 때, 2개의 노드를 선택하여 선택한 2개의 노드가 같은 그래프에 속하는 지 확인하는 알고리즘이다. 원리 여러 노드들이 존재한다고 하고, 그 노드들의 수만큼 배열을 만들어준다. 각 노드의 배열의 값은 그 노드의 부모 노드의 값이다. 즉, 모든 노드들이 서로 연결되어 있지 ...
12.[Algorithm] Kruskal Algorithm(크루스칼 알고리즘)
크루스칼 알고리즘이란? 가장 적은 비용으로 모든 노드를 연결하기 위한 알고리즘. 즉, 최소 비용 신장 트리를 만드는 알고리즘. 모든 노드들을 연결하여 하나로 만드는 데, 비용이 가장 적게 드는 것을 찾는 것 원리 *간선의 숫자는 [노드의 수 - 1] 이다. *사이클이 포함되면 안된다. 간선을 거리가 짧은 순서대로 그래프에 포함시킨다. 1) 먼저 간선들...
13.[Algorithm] 이진트리의 구현과 순회 알고리즘
이진트리란? 가장 많이 사용되는 비선형 자료구조는 이진트리이다. ( 선형 자료구조는 배열, 스택, 큐 등이다.) 이진트리는 데이터의 탐색 속도를 빠르게 하기 위해 사용한다. 한 번 탐색 할 때마다, 반씩 탐색할 데이터가 줄어들기 때문에 트리의 높이는 logN이 된다. 완전 이진 트리는 그냥 구현할 수 있지만, 보통 이진트리를 구현할 때는 포인터를 사...
14.[Algorithm] 다이나믹 프로그래밍(Dynamic Programming)
다이나믹 프로그래밍이란? DP라고도하고, 동적 계획법이라고도 한다. 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 정렬같은 경우는 데이터를 나눠서 처리하기 때문에, 동일한 문제를 다시 풀지 않는다. 그러나 피보나치 수열 같은 경우 재귀적으로 풀면, 뒤의 값을 구할 수록, 앞에 계산했던 내용을 또 계산하는 반복이 일어난다. 원리 DP를 사용하려...
15.[Algorithm] 에라토스테네스의 체
에라토스테네스의 체 란? 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 단일 숫자 소수 여부 확인 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘...
16.[Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘이란? 다이나믹 프로그래밍을 이용한 최단 경로 찾기 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단경로를 알려준다. 단, 음의 간선이 있을 경우 사용할 수 없는 알고리즘이다. 다익스트라 알고리즘이 DP 문제인 이유는 최단경로는 여러개의 최단거리로 나타낼 수 있기 때문이다. 하나의 최단 거리를 구할 때, 그 이전까...
17.[Algorithm] 플로이드 와샬 알고리즘(Floyd Warshall)
플로이드 와샬 알고리즘이란? 다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘이라면, 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 거쳐가는 정점을 기준으로 최단 거리를 구한다. 원리 동적 프로그래밍 기법의 원리를 사용한다. 각각 정점이 다른 정점으로 가는 비용을 이차원 배...
18.[Algorithm] 위상 정렬(Topology Sort)
위상 정렬이란? 위상 정렬은 순서가 정해져있는 작업 차례로 수행해야 할 때, 그 순서를 결정해주는 알고리즘이다. 순차적으로 어떤 그래프가 형성되어있을 때, 그 그래프를 하나의 경로로 나타내는 것이다. 하나의 경로만 존재하는 것이 아니라, 여러 나열 방법이 있을 수 있기 때문에 답은 다양하게 나올 수 있는 알고리즘이다. DAG(Directed Acycl...
19.[Algorithm] 강한 결합 요소(Strongly Connected Component)
강한 결합 요소란? SCC라고도 부르며, 그래프 안에서 강하게 결합된 정점 집합을 뜻한다. 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다. 싸이클이 발생하는 경우 SCC이다. 즉, 방향 그래프일 때만 의미가 있다. 무향 그래프인 경우 그래프 전체가 SCC이기 때문에 의미가 없다. SCC를 추출하는 알고리즘은 2가지가 있다. 코사라주 알고리즘:...
20.[Algorithm] 네트워크 플로우(Network Flow)
네트워크 플로우란? 특정한 지점에서 다른 지점으로 얼마나 많은 양의 데이터가 흐르고 있는지를 측정하는 알고리즘 각 노드 사이는 실제로 가는 양(유량: Flow)/갈수있는 총량(용량: Capacity) 으로 나타낼 수 있다. 한 노드에서 여러 노드를 거쳐 최종 목적지에 도착할 때 까지, 해당 경로의 간선 중 용량이 가장작은 값이 출발점에서 목적지까지의 ...
21.[Algorithm] 이분 매칭(Bipartite Matching)
이분 매칭이란? 네트워크 플로우의 한 종류로, 네트워크 플로우와 연계되는 알고리즘이다. 네트워크 플로우의 특정한 경우에만 사용가능한데, 집단이 오로지 두 개의 집단으로 나눠졌을 때 사용할 수 있다. 최대 유량을 구하는 문제라고도 볼 수 있다. 두 집단을 그래프로
22.[Algorithm] 문자열 매칭 알고리즘
특정한 글이 있을 때, 그 글안에서 특정한 문자열을 찾는 알고리즘이다. 단순히 하나씩 비교하는 가장 간단한 형태의 알고리즘이다. 찾을 문자열을 전체 문장의 처음부분에 두고, 하나씩 비교한다.일치할 때 까지, 한 칸씩 이동하며 비교한다.시간 복잡도는 '찾을 문자열의 길이
23.[Algorithm] 라빈 카프(Rabin-Karp) 알고리즘
라빈 카프 알고리즘이란? 특이한 문자열 알고리즘이다. 항상 빠르지는 않지만 일반적인 경우 빠르게, 작동하는 간단한 구조의 문자열 알고리즘이다. 해시기법을 사용한다. 해시 기법은 긴 데이터를 그것을 상징하는 짧은 데이터로 바꿔주는 기법이다. 각 문자의 아스키 코드
24.[Algorithm] 그리디(Greedy) 알고리즘
당장 눈 앞에 보이는 최적의 상황만 쫓는 알고리즘항상 최적의 결과를 만들어내지는 않지만, 어느정도 최적화 된 값을 빠르게 구할 수 있다.(특정한 상황에서는 최적의 해를 보장할 수도 있다.)거스름돈 문제같이, 무조건 큰 경우, 작은 경우 등, 차례대로 해결해 나갈 수 있