Computer Science/Algorithm

1. Quick sort 분할 정복 테크닉을 사용한 매우 빠른 시간 복잡도를 가진 정렬 알고리즘이다. 정렬 로직 수행 간 초기 정렬 상태를 보장하지 않는 불안정 정렬이다. 추가 메모리 공간을 필요로 하지 않는다. 시간 복잡도 : O(NlogN) Quick sort의 로직 동작 과정 주어진 배열의 범위 내에서 하나의 값(Pivot)을 기준으로 정하고, pivot 왼쪽에는 pivot보다 작은 값들이 오른쪽에는 pivot보다 큰 값들이 오도록 정렬한다. pivot을 기준으로 나뉜 배열은 정렬된 순서는 보장하지 않기 때문에 각각 배열에서 새로운 pivot을 설정하여 다시 분할해서 재귀 호출 한다. 1,2번의 과정을 배열을 분할할 수 없을 때 까지 반복한다. Quick sort 장/단점 장점 - pivot과 거리..

1. Merge sort 분할 정복기법을 활용하여 정렬시키는 정렬 알고리즘이다. 재귀를 활용하여 큰 문제를 작은 문제로 쪼개서 풀이한 다음 return하면서 값을 합쳐서 도출해낸다. 정렬 로직 수행 간 초기 정렬상태를 보장하는 안정 정렬 방식이다 시간복잡도 : O(NlogN) // 공간복잡도 : O(N) Merge sort의 로직 동작 과정 1. 정렬할 배열의 처음과 끝 인덱스를 함수의 인자로 넘겨준다. 2. 처음과 끝 인덱스를 2로 나눈, 즉 mid = (left + right)/2. mid를 기준으로 재귀함수를 호출하여 범위가 1이 될 때 까지 나눠준다. 3. 정렬한 후 값을 복사해서 return 한다. mid를 기준으로 나눴을 때 왼쪽 부분의 범위 : left~mid mid를 기준으로 나눴을 때 오..

1-1. Bubble sort / 버블 정렬 인접한 두 원소를 비교해서 정렬이 잘못되어 있으면 서로 바꾸는 방식으로 정렬한다. 한번 큰 for문을 돌 때마다 탐색 범위 중에서 가장 큰 값을 가지는 원소가 뒤로 이동한다(오름차순 정렬일 경우) 돌 때마다 큰 숫자 하나는 무조건 정렬되기 때문에 (전체 원소의 갯수 - 큰 for문을 돈 횟수)만큼 돌아주면 된다. 시간복잡도 : O(N^2) 1-2. Code #include using namespace std; int n; vector arr; void Print() { for (int a : arr) { cout

오늘 백준에서 문제를 풀다가 vector정렬 시 내가 원하는 순서대로 커스텀해서 정렬하는 compare함수를 만들어서 사용하다가 Runtime Error를 만나서 구글링으로 알아낸 결과를 정리하려고 한다. 결론은 벡터를 정렬하기 위해 sort로 넘겨준 cmp 함수가 잘못돼서 발생한 문제였다. 1. C++ 공식 문서에서 알아보는 Sort C++ STL의 sort함수는 수학적으로 strict weak ordering 조건을 만족해야 한다. 1. cmp(a, a) == false 2. cmp(a, b) == true이면 cmp(b, a) == false. 두 비교체를 바꾸면 참/거짓 값도 변경되어야한다. 3. cmp(a, b) == true이고 cmp(b, c) == true이면 cmp(a, c) == tru..

1. 유니온 파인드 알고리즘이란? 대표적인 그래프 알고리즘으로 두개의 노드가 같은 집합에 속하는지 판별하는 알고리즘 서로소 집합 또는 상호배타적 집합(Disjoint-Set) 알고리즘이라고도 불린다 노드를 합치는 Union연산과 루트 노드를 찾는 Find연산으로 이루어져있다. 시간복잡도는 트리의 높이만큼 탐색하는 O(logN)을 가지게 된다. Union을 해주는 과정에서 한쪽으로만 노드들이 달리는 사향트리의 형태를 띄게 되면 O(n)이 되어버린다. 2. Default Logic 현재 7개의 서로 관련이 없는 노드가 존재하고 우리는 1, 2 / 4, 5 / 5, 6 노드를 서로 연결하려고 한다. 현재는 아무런 연관이 없기 때문에 각 노드들에 대한 root node는 자기 자신이다. 1번 노드와 2번 노드를..

1. 이분탐색이란? 이분 탐색 알고리즘은 정렬되어 있는 배열에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 알고리즘이다. 이분탐색은 결정 문제의 답이 이분적일 때 사용할 수 있는데 대표적인 예시로 카드 뽑기 문제가 있다. 결정 문제란 답이 Yes or No인 문제를 의미한다. 시간 복잡도 : O(logN) 카드 뽑기 문제는 1 ~ 50까지 오름차순으로 정렬된 카드묶음에서 28번 카드를 찾는 문제를 예시로 들어보겠다. 첫번째 카드부터 n번째 카드는 card[i], 우리가 찾고자 하는 카드인 28은 val로 가정한다. 이때 문제를 푸는 방법에 v[i] >= val 인가를 잡으면 답은 1~27까지는 False, 28이후로는 True가 나오게된다. 이때 우리가 찾고자 하는 값은 처음으로 card[i] >= ..

1. 위상정렬이란? 순환하지 않고 방향이 정해져있는 그래프의 노드를 거스르지 않은 상태로 정렬하는 방법. 비순환 유향 그래프에서만 사용할 수 있으며 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저오는 순서로 정렬이 된다. 시간 복잡도 : O(V+E) {Vertex : 노드의 갯수 / Edge : 간선의 갯수} 2. Default Logic 위상정렬을 하는 방법에는 BFS를 사용하는 방법과 DFS를 사용하는 방법이 있는데 나는 BFS로 설명할 것이다. 먼저 BFS를 사용한 방법을 말로 설명해 보자면 1. 모든 정점의 inDegree를 설정해준다. (inDegree : 정점으로 들어오는 간선 수) 2. 한 간선을 처리한 후 inDegree를..

1. 다익스트라(Dijkstra) 란? 다익스트라 알고리즘이란 하나의 그래프에서의 최단 경로 탐색 알고리즘이며, 우리가 흔히 알고있는 동적계획법 즉 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 한 정점에서 모든 정점까지의 최단거리를 구할 때 사용하며, 주어진 그래프중에서 음의 가중치가 없는 그래프에서 사용 가능하다. 음의 가중치가 있을 경우 벨만-포드 알고리즘을 사용하여 해결할 수 있다. 2. Default Logic 다익스트라 알고리즘 동작 반복 과정 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. 2. 현재 위치한 정점을 거쳐 다른 노드로 넘어가는 가중치 값을 계산하여 최소 비용을 갱신한다. 3. 위의 과정을 목표한 노드에 도달 할 때까지 반복한다. 이해를 돕기 위해..

1. Two pointers 란? 리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 치리하는 알고리즘 보통 알고리즘에서 엄청나게 많은 입력들 중에서 원하는 값을 찾거나 반복문을 사용했을때 시간복잡도가 터지는 경우에 사용. 시간 복잡도 : O(N) || 매 과정에서 인덱스를 옮기는데 무조건 1씩 증가하고 항상 start m (현재 부분합이 우리가 원하는 부분합보다 클 때) - sum -= vec[start] (start인덱스의 값) - start 증가 글로는 이렇게 표현할 수 있지만 직접 그림으로 보자 Testcase 10 4 5 1 3 5 10 7 4 9 2 2 end == 2가 됐을 때 구간합과 원하는 Value가 일치하게 된다. 그리고 이후에 원하는 Value 값이 나왔기때문에 end..

1. Dynamic Programming 이란? Dynamic Programming 즉 동적 계획법은 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것. 내가 이해한 DP란 재귀를 활용하게 되면 알고리즘 문제를 풀 때 이미 계산한 값도 중복해서 계산을 해야 하지만 DP는 내가 생성한 DP테이블에 계산한 값을 저장해 놓기 때문에 동일한 연산을 마주치면 값을 계산하지 않고 dp테이블에서 가져와서 하위 연산을 하지 않기 때문에 시간복잡도를 줄일 수 있음. 동적계획법이라고 하기보단 "memoization / 값 저장해서 필요할 때 가져오는 방법" 이라고 이해하면 편할 것 같다 2. DP와 재귀 연산횟수 비교 (백준 2576 계단 오르기) 해당 문제 또한 ..