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 >= 2s²

열 정렬 n값에 관계 없이 여덟 번의 단계로 수행된다. 홀수 단계들은 모두 각 열을 개별적으로 정렬하는 단계다. 각 짝수 단계들은 정해준 순서가 있다. 다음 단계를 나열한다.

1.각 열을 정렬한다.

2.행렬을 전치한다. 하지만 결과의 여전히 r행과 s열을 가지도록 재구성해야한다. 다시 말해 왼쪽 끝 열을 우에서부터 r/s개의 행에 옮긴다. 순서대로 다음 열을 그 다음 r/s개의 행으로 옮긴다. 순서대로 계속한다.

3.각 열을 정렬한다.

4.2단계에서 수행했던 작업을 반대로 수행한다.

5.각 열을 정렬한다.

6.각 열의 위쪽 절반을 같은 열의 아래쪽 절반으로 만들고 각 열의 아래쪽 절반을 오른쪽으로 한 칸 옮겨 위쪽 절반으로 만든다. 위쪽 절반의 가장 왼쪽 열은 비워놓는다. 마지막 열의 아래쪽 절반은 새로 만들어지는 오른쪽 끝 열의 위쪽 절반이 되도록 하고 이 새열의 아래쪽 절반은 비워놓는다.

7.각 열을 정렬한다.

8.6단계에서 수행한 작업을 반대로 수행한다.

   원본          1단계           2단계          3단계          4단계          5단계

6단계            7단계             8단계

행렬 전치와 절반 나누는 단계에 더 좋은 방법이 있을 것 같은데...

namespace Algorithm.Sort

{

    class ColumnSort

    {

        public static int[,] Sort(int[,] unSortList)

        {

            Sort(ref unSortList);

            Transposed(ref unSortList);

            Sort(ref unSortList);

            ReverseTransposed(ref unSortList);

            Sort(ref unSortList);

            int[,] transposedMatrix = null;

            HalfDivideTransposed(ref unSortList, out transposedMatrix);

            ReverseHalfDivideTransposed(ref transposedMatrix, out unSortList);

            return unSortList;

        }

        private static void Sort(ref int[,] unSortList)

        {

            if (unSortList.Length > 0 && (unSortList.GetLength(0) & 1) == 0)

            {

                for (int i = 0; i < unSortList.GetLength(1); i++)

                {

                    for (int ii = 0; ii < unSortList.GetLength(0); ii++)

                    {

                        for (int iii = 1; iii < unSortList.GetLength(0); iii++)

                        {

                            if (unSortList[iii, i] < unSortList[iii - 1, i])

                            {

                                Swap(ref unSortList, i, iii, i, iii - 1);

                            }

                        }

                    }

                }

            }

        }

        private static void Sort(ref int[,] unSortList, int begin, int end)

        {

            for (int i = begin; i < end; i++)

            {

                for(int ii=0; ii< unSortList.GetLength(0); ii++)

                {

                    for (int iii = 1; iii < unSortList.GetLength(0); iii++)

                    {

                        if (unSortList[iii, i] < unSortList[iii - 1, i])

                        {

                            Swap(ref unSortList, i, iii, i, iii - 1);

                        }

                    }

                }

            }

        }

        private static void ReverseHalfDivideTransposed(ref int[,] unSortList, out int[,] sortList)

        {

            sortList = new int[unSortList.GetLength(0), unSortList.GetLength(1) - 1];

            int row = unSortList.GetLength(0) / 2;

            for (int i = 0; i < row; i++)

            {

                for (int ii = 0; ii < unSortList.GetLength(1)-1; ii++)

                {

                    sortList[i, ii] = unSortList[i + row, ii];

                }

                for (int ii = 1; ii < unSortList.GetLength(1); ii++)

                {

                    sortList[row + i, ii - 1] = unSortList[i, ii];

                }

            }

        }

        private static void HalfDivideTransposed(ref int[,] unSortList, out int[,] transposedMatrix)

        {

            transposedMatrix = new int[unSortList.GetLength(0), unSortList.GetLength(1) + 1];

            int row = unSortList.GetLength(0) / 2;

            for (int i = 0; i < row; i++)

            {

                for (int ii = 0; ii < unSortList.GetLength(1); ii++)

                {

                    transposedMatrix[row + i, ii] = unSortList[i, ii];

                }

                for (int ii = 0; ii < unSortList.GetLength(1); ii++)

                {

                    transposedMatrix[i, ii + 1] = unSortList[row + i, ii];

                }

            }

            Sort(ref transposedMatrix, 1, transposedMatrix.GetLength(1) - 1);

        }

        private static void Transposed(ref int[,] unSortList)

        {

            var transposedMatrix = new int[unSortList.GetLength(0), unSortList.GetLength(1)];

            int row = 0, col = 0;

            for (int i = 0; i < unSortList.GetLength(0); i++)

            {

                if (i != 0 && (i & 1) == 0)

                {

                    row = 0;

                    col++;

                }

                for (int ii = 0; ii < unSortList.GetLength(1); ii++)

                {

                    transposedMatrix[i, ii] = unSortList[row++, col];

                }

            }

            Array.Copy(transposedMatrix, unSortList, transposedMatrix.Length);

        }

        private static void ReverseTransposed(ref int[,] unSortList)

        {

            var transposedMatrix = new int[unSortList.GetLength(0), unSortList.GetLength(1)];

            int row = 0, col = 0;

            for (int i = 0; i < unSortList.GetLength(0); i++)

            {

                if (i != 0 && (i & 1) == 0)

                {

                    row = 0;

                    col++;

                }

                for (int ii = 0; ii < unSortList.GetLength(1); ii++)

                {

                    transposedMatrix[row++, col] = unSortList[i, ii];

                }

            }

            Array.Copy(transposedMatrix, unSortList, transposedMatrix.Length);

        }

        private static void Swap(ref int[,] unSortList, int a_x, int a_y, int b_x, int b_y)

        {

            var temp = unSortList[a_y, a_x];

            unSortList[a_y, a_x] = unSortList[b_y, b_x];

            unSortList[b_y, b_x] = temp;

        }

    }

}

기수 정렬(radix sort)은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 O(dn)이다.(d는 가장 큰 데이터의 자리수)

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 O(dn)이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

설명 출처 : https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC

code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/RadixSort.cs

양수 음수 구분 한 다음 합침

namespace Algorithm.Sort

{

    class RadixSort

    {

        public static List<int> Sort(List<int> unsortList)

        {

            return Sort(ref unsortList);

        }

        private static List<int> Sort(ref List<int> unsortList)

        {

            List<Queue<int>> _positiveBucket = new List<Queue<int>>();

            List<Queue<int>> _negativeBucket = new List<Queue<int>>();

            for (int i = 0; i < 11; i++)

            {

                _positiveBucket.Add(new Queue<int>());

                _negativeBucket.Add(new Queue<int>());

            }

            var digit = unsortList.Max().ToString().Length;

            int div = 1, idx = -1;

            for (int i = 0; i < digit; i++, div *= 10)

            {

                for (int ii = 0; ii < unsortList.Count; ii++)

                {

                    idx = unsortList[ii]/ div % 10;

                    if (idx >= 0)

                        _positiveBucket[idx].Enqueue(unsortList[ii]);

                    else

                        _negativeBucket[idx * -1].Enqueue(unsortList[ii]);

                }

                idx = 0;

                for(int ii= _negativeBucket.Count - 1; ii>=0; ii--)

                {

                    while (_negativeBucket[ii].Count > 0)

                        unsortList[idx++] = _negativeBucket[ii].Dequeue();

                }

                for (int ii = 0; ii< _positiveBucket.Count; ii++)

                {

                    while (_positiveBucket[ii].Count > 0)

                        unsortList[idx++] = _positiveBucket[ii].Dequeue();

                }

            }

            return unsortList;

        }

    }

}

O(n+k) (k는 데이터의 최댓값을 의미한다.)

카운팅 정렬은 가장 큰 데이터에 따라 효율이 좌지우지된다. 

쉽게 설명하자면 특정 데이터의 개수(1이 두 개 있다면 2)를 데이터의 값에 대응하는 위치에 저장한 뒤, 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 만든 뒤, 거기서 데이터가 들어가야 할 위치를 찾아내는 정렬 알고리즘이다. 

이 경우에 데이터의 최댓값을 k라 두면, 시간 복잡도는 O(n+k).

n이 아무리 작아도 동작시간이 크다. 

그럴 땐 위의 정렬들을 사용하는 게 바람직하다. 반대로 k가 매우 작다면, 오히려 선형시간의 효과를 볼 수 있다.

즉, k가 작다는 조건이라면 매우 효율적인 정렬. 또한 카운팅 정렬은 배열을 사용하는 특성상, 정수라는 전제를 깔고 한다.

설명 출처 : https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.3.2

이미지 출처 : https://brilliant.org/wiki/counting-sort/

출처에 가면 애니메이션도 있어서 어떻게 돌아가는지 파악 가능함.

위의 이미지가 누적합까지 구하는 이미지이고

위에서 구한 누적합을 가지고 정렬을 시작한다.

0번 index (값 3) 를 정렬 배열 인덱스 2(배열의 순서는 0부터 시작하니 -1)에 넣어주고 누적합은 -1 해서 값 2

0번 index (값 2) 를 정렬 배열 인덱스 1(배열의 순서는 0부터 시작하니 -1)에 넣어주고 누적합은 -1 해서 값 1

이런식..

책에 있는 의사코드

C[0..k]를 새로운 배열로 한다.

for i = 0 to k

c[i] = 0

for j = 1 to A.length

C[A[j]] = C[A[j]] + 1

//C[i]는 이제 i와 같은 원소의 개수를 나타낸다.

//누적합

for i = 1 to k

C[i] = C[i] +[i-1]

//C[i]는 이제 값이 i보다 작거나 같은 원소의 개수를 나타낸다.

for j = A.lenght downto 1

B[C[A[j]]] = A[j]

C[A[j]] = C[A[j]]-1

의사코드를 C#으로 옮김

code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/CountingSort.cs

namespace Algorithm.Sort

{

    class CountingSort

    {

        public static List<int> Sort(List<int> unsortList)

        {

            return Sort(ref unsortList);

        }

        private static List<int> Sort(ref List<int> unsortList)

        {

            List<int> _countList = new List<int>();

            int max = unsortList.Max();

            _countList.AddRange(Enumerable.Repeat(0, max + 1));

            foreach (var value in unsortList)

                _countList[value]++;

            for (int i=1; i< _countList.Count; i++)

                _countList[i] += _countList[i - 1];

            List<int> _sortList = new List<int>(new int[unsortList.Count]);

            for(int i=0; i< unsortList.Count; i++)

            {

                _sortList[_countList[unsortList[i]] - 1] = unsortList[i];

                _countList[unsortList[i]]--;

            }

            return _sortList;

        }

    }

}

언제쯤 RB 트리 구현해보려나..-_- 책 진도가 안나간다.

code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/QuickSort.cs

namespace API.Util.Sort

{

    class QuickSort

    {

        public static List<T> Sort<T>(List<T> unsortList) where T : IComparable

        {

            Sort(ref unsortList, 0, unsortList.Count - 1);

            return unsortList;

        }

        private static void Swap<T>(ref List<T> unsortList, int indexA, int indexB)

        {

            var temp = unsortList[indexA];

            unsortList[indexA] = unsortList[indexB];

            unsortList[indexB] = temp;

        }

        private static List<T> Sort<T>(ref List<T> unsortList, int left, int right) where T : IComparable

        {

            var pivot = unsortList[(left + right) / 2];

            int l = left, r = right;

            while (l <= r)

            {

                while (unsortList[l].CompareTo(pivot) < 0)

                {

                    l++;

                }

                while (unsortList[r].CompareTo(pivot) > 0)

                {

                    r--;

                }

                if (l <= r)

                {

                    Swap(ref unsortList, l, r);

                    l++;

                    r--;

                }

            }

            if (left < r)

                Sort(ref unsortList, left, r);

            if (l < right)

                Sort(ref unsortList, l, right);

            return unsortList;

        }

    }

}

https://github.com/EomTaeWook/Algorithm

여기에 계속해서 자료구조 추가 할 예정

namespace API.Util

{

    public enum Order

    {

        Ascending,

        Descending

    }

    public class PriorityQueue<T> : IEnumerable<T> where T : IComparable<T>

    {

        private List<T> _list = new List<T>();

        private Order _order;

        public PriorityQueue(Order order = Order.Ascending)

        {

            _order = order;

        }

        public IEnumerator<T> GetEnumerator()

        {

            return _list.GetEnumerator();

        }

        IEnumerator IEnumerable.GetEnumerator()

        {

            return _list.GetEnumerator();

        }

        public int Count

        {

            get

            {

                return _list.Count;

            }

        }

        public void Clear()

        {

            _list.Clear();

        }

        public bool Contains(T item)

        {

            return _list.Contains(item);

        }

        public void CopyTo(T[] array, int arrayIndex)

        {

            _list.CopyTo(array, arrayIndex);

        }

        public T Dequeue()

        {

            if (_list.Count == 0)

            {

                throw new InvalidOperationException();

            }

            T item = _list[0];

            _list[0] = _list[_list.Count - 1];

            _list.RemoveAt(_list.Count - 1);

            int index = 0;

            int size = _list.Count - 1;

            while (true)

            {

                //Left Node Right Node

                if (size > index * 2 + 1 && size > index * 2)

                {

                    var child = _list[index * 2 + 1].CompareTo(_list[index * 2]);

                    int childIndex = 0;

                    if (child > 0 && _order == Order.Ascending)

                    {

                        childIndex = index * 2 + 1;

                    }

                    else if (child < 0 && _order == Order.Ascending)

                    {

                        childIndex = index * 2;

                    }

                    else if (child < 0 && _order == Order.Descending)

                    {

                        childIndex = index * 2 + 1;

                    }

                    else if (child > 0 && _order == Order.Descending)

                    {

                        childIndex = index * 2;

                    }

                    if (_list[index].CompareTo(_list[childIndex]) < 0 && _order == Order.Ascending)

                    {

                        Swap(index, childIndex);

                        index = childIndex;

                    }

                    else if (_list[index].CompareTo(_list[childIndex]) > 0 && _order == Order.Descending)

                    {

                        Swap(index, childIndex);

                        index = childIndex;

                    }

                    else

                        break;

                }

                //Left Node

                else if (_list.Count > index * 2 + 1)

                {

                    var order = _list[index].CompareTo(_list[index * 2 + 1]);

                    if (order < 0 && _order == Order.Ascending)

                    {

                        Swap(index, index * 2 + 1);

                        index = index * 2 + 1;

                    }

                    else if (order > 0 && _order == Order.Descending)

                    {

                        Swap(index, index * 2 + 1);

                        index = index * 2 + 1;

                    }

                    else

                        break;

                }

                else

                    break;

            }

            return item;

        }

        public void Enqueue(T item)

        {

            _list.Add(item);

            int index = _list.Count - 1;

            int parent = 0;

            while (true)

            {

                if (index == 0) break;

                parent = (index - 1) / 2;

                var order = _list[index].CompareTo(_list[parent]);

                if (_order == Order.Ascending && order > 0)

                {

                    Swap(index, parent);

                    index = parent;

                }

                else if (_order == Order.Descending && order < 0)

                {

                    Swap(index, parent);

                    index = parent;

                }

                else

                    break;

            }

        }

        public T Peek()

        {

            if (_list.Count == 0)

            {

                throw new InvalidOperationException();

            }

            return _list[0];

        }

        public T[] ToArray()

        {

            return _list.ToArray();

        }

        private void Swap(int index, int parent)

        {

            var temp = _list[index];

            _list[index] = _list[parent];

            _list[parent] = temp;

        }

    }

}

후위표기법 

검색해보니 이상하고 난잡한 소스들이 많은 것 같다. 우선순위를 구하는 함수를 따로 두질 않나..

그나마 이게 제일 깔끔해보임.

3+4+5*6+7

34+56*+7+

#include<stdio.h>

#include<iostream>

#include<string>

#include<vector>

using namespace std;

int main()

{

string dump;

int t = 0, size;

std::vector<char> v;

vector<int> result;

std::string post = "";

while (t++ < 10)

{

scanf("%d", &size);

cin >> dump;

for (int i = 0; i < size; i++) {

switch (dump[i])

{

case '(':

v.push_back(dump[i]);

break;

case ')':

while (v.back() != '(')

{

post += v.back();

v.pop_back();

}

v.pop_back();

break;

case '+':

case '-':

while (!v.empty() && v.back() != '(')

{

post += v.back();

v.pop_back();

}

v.push_back(dump[i]);

break;

case '*':

case '/':

while (!v.empty() && (v.back() == '*' || v.back() == '/'))

{

post += v.back();

v.pop_back();

}

v.push_back(dump[i]);

break;

default:

post += dump[i];

break;

}

}

while (!v.empty())

{

post += v.back();

v.pop_back();

}

for (int i = 0; i < post.size(); i++)

{

switch (post[i])

{

case '+': 

{

int op1 = result.back();

result.pop_back();

int  op2 = result.back();

result.pop_back();

result.push_back(op1 + op2);

break;

}

case '*':

{

int op1 = result.back();

result.pop_back();

int  op2 = result.back();

result.pop_back();

result.push_back(op1 * op2);

break;

}

case '/':

{

int op1 = result.back();

result.pop_back();

int  op2 = result.back();

result.pop_back();

result.push_back(op1 / op2);

break;

}

default:

result.push_back(post[i] - '0');

break;

}

}

printf("#%d %d\n", t, result.back());

result.pop_back();

}

return 0;

}

부산에 중견 코딩 테스트 때 나왔던 문제인데 스터디 같이 하시던 분이 부산 가셔서 테스트 보시고 문제 들고 오심.

최대 1000으로 생각한다.

N=4

1+1+1+1

1+1+2

2+2

3+1

#include<stdio.h>

#include<string.h>

#include <chrono>

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; i++)

{

if (sum + i > N) break;

count += GetValue(i, sum + i);

}

return memo[idx][sum] = count;

}

int main()

{

scanf("%d", &N);

long long count = 0;

system_clock::time_point start = system_clock::now();

memset(memo, -1, sizeof(memo));

for(int i=1; i<N;i++)

count += GetValue(i, i);

printf("%lld\n", count);

system_clock::time_point end = system_clock::now();

duration<double> sec = end - start;

printf("%lf", sec);

    return 0;

}