Diademata

설명 출처 : Introduction to algorithms code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/ColumnSort.cs 열 정렬(Column Sort) 알고리즘은 N개의 원소가 있는 직사각형 배열에서 동작한다.배열은 r개의 행과 s개의 열을 갖고 있으며(그러므로 n = rs이다) 다음 세개의 제약 사항을 가진다.r은 짝수여야 한다.r은 s로 나누어져야 한다.r >= 2s2열 정렬 n값에 관계 없이 여덟 번의 단계로 수행된다. 홀수 단계들은 모두 각 열을 개별적으로 정렬하는 단계다. 각 짝수 단계들은 정해준 순서가 있다. 다음 단계를 나열한다. 1.각 열을 정렬한다.2.행렬을 전치한다. 하지만 결과의 여전히..

기수 정렬(radix sort)은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 O(dn)이다.(d는 가장 큰 데이터의 자리수) 기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 O(dn)이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다. 설명 출처 : https://ko.wikipedia.org/w..

O(n+k) (k는 데이터의 최댓값을 의미한다.) 카운팅 정렬은 가장 큰 데이터에 따라 효율이 좌지우지된다. 쉽게 설명하자면 특정 데이터의 개수(1이 두 개 있다면 2)를 데이터의 값에 대응하는 위치에 저장한 뒤, 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 만든 뒤, 거기서 데이터가 들어가야 할 위치를 찾아내는 정렬 알고리즘이다. 이 경우에 데이터의 최댓값을 k라 두면, 시간 복잡도는 O(n+k).n이 아무리 작아도 동작시간이 크다. 그럴 땐 위의 정렬들을 사용하는 게 바람직하다. 반대로 k가 매우 작다면, 오히려 선형시간의 효과를 볼 수 있다.즉, k가 작다는 조건이라면 매우 효율적인 정렬. 또한 카운팅 정렬은 배열을 사용하는 특성상, 정수라는 전제를 깔고 한다. 설명 출처 : https://n..

언제쯤 RB 트리 구현해보려나..-_- 책 진도가 안나간다.code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/QuickSort.cs namespace API.Util.Sort{ class QuickSort { public static List Sort(List unsortList) where T : IComparable { Sort(ref unsortList, 0, unsortList.Count - 1); return unsortList; } private static void Swap(ref List unsortList, int indexA, int indexB) { var temp = unsortList[indexA];..

https://github.com/EomTaeWook/Algorithm 여기에 계속해서 자료구조 추가 할 예정 namespace API.Util{ public enum Order { Ascending, Descending } public class PriorityQueue : IEnumerable where T : IComparable { private List _list = new List(); private Order _order; public PriorityQueue(Order order = Order.Ascending) { _order = order; } public IEnumerator GetEnumerator() { return _list.GetEnumerator(); } IEnumerator..

후위표기법 검색해보니 이상하고 난잡한 소스들이 많은 것 같다. 우선순위를 구하는 함수를 따로 두질 않나.. 그나마 이게 제일 깔끔해보임. 3+4+5*6+734+56*+7+ #include#include#include#includeusing namespace std;int main(){string dump;int t = 0, size;std::vector v;vector result;std::string post = "";while (t++ > dump;for (int i = 0; i < size; i++) {switch (dump[i]){case '(':v.push_back(dump[i]);break;case ')':while (v.back() != ..

부산에 중견 코딩 테스트 때 나왔던 문제인데 스터디 같이 하시던 분이 부산 가셔서 테스트 보시고 문제 들고 오심. 최대 1000으로 생각한다. N=41+1+1+11+1+22+23+1 #include#include#include int N = 4;long long memo[1001][1001];using namespace std;using namespace chrono;int GetValue(int idx, int sum){if (sum > N)return 0;if (sum == N) return 1;if (memo[idx][sum] != -1) return memo[idx][sum];long long count = 0;for (int i = idx; i N) b..