본문 바로가기
C++/자료구조와 알고리듬

2. Sort, Search, Stack, Queue

by GameStudy 2022. 10. 23.

2.1 Sort

  Note) 정렬의 종류

    버블 정렬 / 퀵 정렬 / 선택 정렬 / 삽입 정렬 / 병합 정렬 / 힙 정렬

 

  Note) 정렬의 차이

    시간 복잡도 / 공간 복잡도 / 안정성 / 직렬 Vs. 병렬

 

  Note) 정렬 알고리듬의 안정성

    똑같은 키 값을 가진 데이터들의 순서가 

    바뀌지 않으면 안정적인 정렬.

    바뀌면 불안정한 정렬.

    안정성이 보장 안되어도 대부분은 문제가 되진 않음.

    그래서 잘 모르고, 생각도 안하는 부분.

    

  Note) 안정성이 문제가 되는 경우

    정렬 기준이 되는 정렬 키 값이 실제 데이터와 다를 경우.

    ex. std::map과 같은 자료구조의 정렬. 

    ex. 구조체 혹은 클래스의 일부 멤버로만 정렬하는 경우.

 

  Note) 안정성이 문제가 되는 경우 해결 방법

    - Upper bound와 Lower bound. 

      정렬 기준이 되는 정렬 키 값은 같지만 실제 데이터와 다른 경우에

      키 값이 같은 것들 중 가장 큰 경우와 가장 작은 경우.    

    - Radix sort

      비트를 이용하여 정렬 하는 방식.

 

  Note) 정렬 알고리듬 비교

  평균 최악 메모리 안정성
버블 O(n^2) O(n^2) O(1) O
선택 O(n^2) O(n^2) O(1) X
삽입 O(n^2) O(n^2) O(1) O
퀵 O(n*log(n)) O(n^2) O(n*log(n)) X
병합 O(n*log(n)) O(n*log(n)) O(n) O
힙 O(n*log(n)) O(n*log(n)) O(1) X

 

 

2.1-1 Bubble Sort

  Note) 장단점
    장점1. 빠르게 구현해야 할 때 간단히 사용 할 수 있음.

    장점2. 값이 같은 요소의 순서가 유지됨.

    단점1. 데이터가 이미 정렬되어 있어도 불필요한 비교연산. 시간 복잡도가 O(N^2) 필요.

    결론. 빨리 구현해야 할 때와 데이터의 개수가 적을 때 사용 가능.

 

  Thm) 버블 정렬 템플릿 코드

<hide/>

#include <iostream>
#include <vector>

void BubbleSort(std::vector<int>& InData) 
{
    size_t Size = InData.size();
    for (size_t i = 0u; i < Size - 1u; ++i) 
    {
        for (size_t j = 0u; j < Size - i - 1u; ++j) 
        {
            if (InData[j + 1] < InData[j])
            {
                std::swap(InData[j], InData[j + 1]);
            }
        }
    }
}

 

 

2.1-2 Quick Sort

  Note) 장단점

    장점1. 평균적으로 O(NlogN) 시간 복잡도.
    단점1. 이미 정렬된 데이터에 대해 O(N^2) 시간복잡도. 랜덤 피벗을 통해 해결.
    단점2. 구현이 복잡함.
    단점3. 값이 같은 요소의 순서가 유지 되지 않을 수 있음.
    단점4. 재귀 호출로 인해 스택 오버 플로가 발생할 수 있음.

 

  Thm) 퀵 정렬 템플릿 코드

<hide/>

#include <iostream>
#include <vector>

// 퀵 정렬 함수
void QuickSort(std::vector<int>& InData, size_t InLeft, size_t InRight) 
{
    if (InRight <= InLeft)
    {
        return;
    }

    int Pivot = InData[InRight];
    size_t PartitionIndex = InLeft;

    for (size_t i = InLeft; i < InRight; ++i) 
    {
        if (InData[i] < Pivot) 
        {
            std::swap(InData[i], InData[PartitionIndex]);
            ++PartitionIndex;
        }
    }
    std::swap(InData[PartitionIndex], InData[InRight]);

    if (1u <= PartitionIndex)
    {
        QuickSort(InData, InLeft, PartitionIndex - 1u);
    }
    QuickSort(InData, PartitionIndex + 1u, InRight);
}

 

 

2.2 Search

  Note) 대표적인 탐색 알고리듬

    선형 탐색 / 이진 탐색 / 해시 기반 탐색
    해시 기반 탐색은 6단원에서 Hash Table을 정리하며 살펴볼 예정.

 

2.2-1 Linear Search

  Def) 정의

    자료구조의 모든 데이터를 처음부터 끝까지 비교하여 원하는 데이터를 찾는 알고리듬.

 

  Note) 장단점
    장점1. 직관적이라 구현이 쉬움.
    장점2. 정렬되지 않은 데이터에서도 사용 가능.
    장점3. 공간복잡도가 높아지지 않음.
    단점1. 시간복잡도가 O(N). 즉, 자료구조에 데이터가 많아질수록 비교적 느려짐.
    결론. 데이터가 정렬되어 있지 않고, 개수가 적고 탐색 빈도가 낮은 경우에 사용.

 

2.2-2 Binary Search
  Def) 정의
    정렬된 자료구조의 데이터들을 반씩 나누어 원하는 데이터를 찾는 알고리듬.

  Note) 장단점
    장점1. 시간복잡도가 O(logN)으로 매우 빠른 탐색 가능.
    단점1. 데이터가 정렬되어 있어야함.
    단점2. 구현이 선형 탐색보다는 복잡함.
    결론. 데이터가 정렬되어 있고, 개수가 많고 탐색 빈도가 높은 경우에 사용.

<hide/>

#include <iostream>
#include <vector>
#include <algorithm> // sort()

size_t binarySearch(const std::vector<int>& InData, int InTarget) 
{
    if (InData.size() == 0u)
    {
        return (size_t)(-1);
    }

    size_t Left = 0u;
    size_t Right = InData.size() - 1u;

    while (Left <= Right) 
    {
        size_t Mid = Left + (Right - Left) / 2;
        if (InData[Mid] == InTarget) 
        {
            return Mid;
        }
        else if (InData[Mid] < InTarget) 
        {
            Left = Mid + 1u;
        }
        else 
        {
            Right = Mid - 1u;
        }
    }

    return (size_t)(-1);
}

 

  코드업2655)
    x 절편을 구하는 문제. 문제와 이진탐색과의 연관성을 잘 캐치 해야함.

<hide/>

#include <iostream>
#include <iomanip>
#include <cmath>

double FindXIntercept(double InA, double InB) 
{
    double Left = -999.0;
    double Right = 999.0;
    double Mid = Left + (Right - Left) / 2.0;
    
    while (1e-6 < Right - Left)
    {
        Mid = Left + (Right - Left) / 2.0;
        double Y = InA * Mid + InB;

        if (0 < Y) 
        {
            Right = Mid;
        }
        else 
        {
            Left = Mid;
        }
    }

    return Mid;
}

int main() 
{
    double a, b;
    std::cin >> a >> b;

    double xIntercept = FindXIntercept(a, b);
    std::cout << std::fixed << std::setprecision(4) << xIntercept << std::endl;

    return 0;
}

 

  백준2776)
    배열의 원소가 또 다른 배열의 원소로 존재하는지 찾는 문제.

<hide/>

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

void solve(const vector<int>& InNoteBook1, const vector<int>& InNoteBook2) 
{
    if (InNoteBook1.empty() == true || InNoteBook2.empty() == true)
    {
        return;
    }

    std::vector<int> SortedNotebook1 = InNoteBook1;
    std::sort(SortedNotebook1.begin(), SortedNotebook1.end());

    for (int Number : InNoteBook2)
    {
        size_t Left = 0u;
        size_t Right = SortedNotebook1.size() - 1u;
        size_t Mid = (Left + Right) / 2;
        bool bIsFound = false;
        while (Left <= Right)
        {
            Mid = (Left + Right) / 2;
            if (Number < SortedNotebook1[Mid])
            {
                Right = Mid - 1;
            }
            else if (Number == SortedNotebook1[Mid])
            {
                std::cout << "1" << std::endl;
                bIsFound = true;
                break;
            }
            else if (SortedNotebook1[Mid] < Number)
            {

                Left = Mid + 1;
            }
        }

        if (false == bIsFound)
        {
            std::cout << "0" << std::endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;  // 테스트 케이스의 수
    cin >> T;

    while (T--) {
        int N;
        cin >> N;
        vector<int> notebook1(N);
        for (int i = 0; i < N; ++i) {
            cin >> notebook1[i];
        }

        int M;
        cin >> M;
        vector<int> notebook2(M);
        for (int i = 0; i < M; ++i) {
            cin >> notebook2[i];
        }

        solve(notebook1, notebook2);
    }

    return 0;
}

 

  백준1072)
    승률이 바뀌는 최소 판수를 구하는 문제. 조건문 속 식을 잘 세워야 함.

<hide/>

#pragma once

#include <iostream>

long long Solve(long long X, long long Y)
{
    long long MinGameCount = -1ll;
    long long Z = Y * 100 / X;               // 현재 승률

    long long Left = 1ll;
    long long Right = 1e9;
    while (Left <= Right)
    {
        long long Mid = (Left + Right) / 2;  // 판수
        if (Z < (Y + Mid) * 100 / (X + Mid))
        {
            MinGameCount = Mid;
            Right = Mid - 1;
        }
        else
        {
            Left = Mid + 1;
        }
    }

    return MinGameCount;
}

int main() 
{
    long long X, Y;
    std::cin >> X >> Y;

    std::cout << Solve(X, Y) << "\n";

    return 0;
}

 

백준2828)

<hide/>

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void solve(int n, int m, int j, vector<int>& apples)
{
    int Left = 1;
    int Right = m;
    int MoveCount = 0;

    for (int Apple : apples)
    {
        if (Apple < Left)
        {
            int MoveLeft = Left - Apple;
            MoveCount += MoveLeft;
            Left -= MoveLeft;
            Right -= MoveLeft;
        }
        else if (Left <= Apple && Apple <= Right)
        {
            continue;
        }
        else if (Right < Apple)
        {
            int MoveRight = Apple - Right;
            MoveCount += MoveRight;
            Left += MoveRight;
            Right += MoveRight;
        }
    }

    cout << MoveCount << endl;
}

int main() {
    int n, m, j;
    cin >> n >> m;
    cin >> j;

    vector<int> apples(j);
    for (int i = 0; i < j; ++i) {
        cin >> apples[i];
    }

    solve(n, m, j, apples);
    return 0;
}

 

 

2.2 스택과 큐

2.2-1 스택

  Def) 정의
    먼저 삽입된 데이터가 먼저 제거되는 자료구조.

  Note) 장단점
    장점. 선입선출 한정으로 삽입/삭제 시간복잡도가 O(1)
    결론. 뒤집기, 괄호검사, 후위표기법, Undo/Redo에 활용 가능.

  Note) 구현코드

<hide/>

#pragma once

#include <iostream>

template<typename T>
class SStack final
{
public:
    SStack(size_t InCapacity = 2u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
        , Size(0u)
    {

    }

    ~SStack()
    {
        delete[] Data;
    }

    size_t GetCapacity() const
    {
        return Capacity;
    }

    size_t GetSize() const
    {
        return Size;
    }

    void Push(const T& InValue)
    {
        if (Full() == true)
        {
            std::cout << __FUNCTION__ << " Full() == true." << std::endl;
            return;
        }
        Data[Size++] = InValue;
    }

    void Pop()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        --Size;
    }

    T& Top()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

    const T& Top() const
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

private:
    bool Full() const
    {
        return Size == Capacity;
    }

    bool Empty() const
    {
        return Size == 0u;
    }

private:
    T* Data;

    size_t Capacity;

    size_t Size;

};

 

 코드업1402)
    거꾸로 출력하기. 간단하게 스택으로 구현 가능.

<hide/>

#pragma once

#include <iostream>
#include <vector>

template<typename T>
class SStack final
{
public:
    SStack(size_t InCapacity = 2u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
        , Size(0u)
    {

    }

    ~SStack()
    {
        delete[] Data;
    }

    size_t GetCapacity() const
    {
        return Capacity;
    }

    size_t GetSize() const
    {
        return Size;
    }

    void Push(const T& InValue)
    {
        if (Full() == true)
        {
            std::cout << __FUNCTION__ << " Full() == true." << std::endl;
            return;
        }
        Data[Size++] = InValue;
    }

    void Pop()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        --Size;
    }

    T& Top()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

    const T& Top() const
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

private:
    bool Full() const
    {
        return Size == Capacity;
    }

    bool Empty() const
    {
        return Size == 0u;
    }

private:
    T* Data;

    size_t Capacity;

    size_t Size;

};

void Solve(const std::vector<int>& InData)
{
    size_t Size = InData.size();
    SStack<int> Stack(Size);

    for (const auto& Data : InData) 
    {
        Stack.Push(Data);
    }

    while (Stack.GetSize() > 0) 
    {
        std::cout << Stack.Top() << " ";
        Stack.Pop();
    }

    std::cout << std::endl;
}

int main() {
    size_t n;
    std::cin >> n;

    std::vector<int> data(n);
    for (size_t i = 0; i < n; ++i) 
    {
        std::cin >> data[i];
    }

    Solve(data);

    return 0;
}

 

  코드업1714)
    문자열 뒤집기 느낌의 문제. std::to_string()을 잘써야함.

<hide/>

#pragma once

#include <iostream>
#include <vector>
#include <string>

template<typename T>
class SStack final
{
public:
    SStack(size_t InCapacity = 2u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
        , Size(0u)
    {

    }

    ~SStack()
    {
        delete[] Data;
    }

    size_t GetCapacity() const
    {
        return Capacity;
    }

    size_t GetSize() const
    {
        return Size;
    }

    void Push(const T& InValue)
    {
        if (Full() == true)
        {
            std::cout << __FUNCTION__ << " Full() == true." << std::endl;
            return;
        }
        Data[Size++] = InValue;
    }

    void Pop()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        --Size;
    }

    T& Top()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

    const T& Top() const
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

private:
    bool Full() const
    {
        return Size == Capacity;
    }

    bool Empty() const
    {
        return Size == 0u;
    }

private:
    T* Data;

    size_t Capacity;

    size_t Size;

};

void Solve(const int& InN)
{
    std::string DataString = std::to_string(InN);

    size_t Size = DataString.size();
    SStack<char> Stack(Size);

    for (const auto& Data : DataString)
    {
        Stack.Push(Data);
    }

    while (Stack.GetSize() > 0) 
    {
        std::cout << Stack.Top();
        Stack.Pop();
    }

    std::cout << std::endl;
}

int main() {
    size_t n;
    std::cin >> n;

    Solve(n);

    return 0;
}

 

  코드업3129)

    괄호 짝맞추기 문제. 조건문을 잘 작성하는 것이 포인트.

<hide/>

#pragma once

#include <iostream>
#include <vector>
#include <string>

template<typename T>
class SStack final
{
public:
    SStack(size_t InCapacity = 2u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
        , Size(0u)
    {

    }

    ~SStack()
    {
        delete[] Data;
    }

    size_t GetCapacity() const
    {
        return Capacity;
    }

    size_t GetSize() const
    {
        return Size;
    }

    void Push(const T& InValue)
    {
        if (Full() == true)
        {
            std::cout << __FUNCTION__ << " Full() == true." << std::endl;
            return;
        }
        Data[Size++] = InValue;
    }

    void Pop()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        --Size;
    }

    T& Top()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

    const T& Top() const
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

private:
    bool Full() const
    {
        return Size == Capacity;
    }

    bool Empty() const
    {
        return Size == 0u;
    }

private:
    T* Data;

    size_t Capacity;

    size_t Size;

};

void solve(const std::string& InBracketString) 
{
    SStack<char> Stack(InBracketString.size());

    for (char Bracket : InBracketString) 
    {
        if (Bracket == '(') 
        {
            Stack.Push(Bracket);
        }
        else if (Bracket == ')') 
        {
            if (Stack.GetSize() == 0) 
            {
                std::cout << "bad" << std::endl;
                return;
            }

            Stack.Pop();
        }
    }

    if (Stack.GetSize() == 0)
    {
        std::cout << "good" << std::endl;
    }
    else
    {
        std::cout << "bad" << std::endl;
    }
}

int main() 
{
    std::string input;
    std::cin >> input;

    // solve 함수 호출
    solve(input);

    return 0;
}

 

  코드업2016)
    천단위 마다 구분 기호를 넣어주는 문제.

<hide/>

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // std::reverse

template<typename T>
class SStack final
{
public:
    SStack(size_t InCapacity = 2u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
        , Size(0u)
    {

    }

    ~SStack()
    {
        delete[] Data;
    }

    size_t GetCapacity() const
    {
        return Capacity;
    }

    size_t GetSize() const
    {
        return Size;
    }

    void Push(const T& InValue)
    {
        if (Full() == true)
        {
            std::cout << __FUNCTION__ << " Full() == true." << std::endl;
            return;
        }
        Data[Size++] = InValue;
    }

    void Pop()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        --Size;
    }

    T& Top()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

    const T& Top() const
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

private:
    bool Full() const
    {
        return Size == Capacity;
    }

    bool Empty() const
    {
        return Size == 0u;
    }

private:
    T* Data;

    size_t Capacity;

    size_t Size;

};

void solve(const std::string& InNumberString, const int& InLength) 
{
    std::string ResultString;

    int Count = 0;
    for (int i = InLength - 1; i >= 0; --i) 
    {
        ResultString += InNumberString[i];
        Count++;

        if (Count % 3 == 0 && i != 0) 
        {
            ResultString += ',';
        }
    }

    std::reverse(ResultString.begin(), ResultString.end());
    std::cout << ResultString << std::endl;
}

int main() 
{
    int n;
    std::string number;

    std::cin >> n;
    std::cin >> number;

    solve(number, n);

    return 0;
}

 

  코드업3021)
    큰 수 간의 덧셈. 한 자리씩 덧셈해서 아무리 큰 수라도 덧셈이 가능하게끔 구현.

<hide/>

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // std::reverse

template<typename T>
class SStack final
{
public:
    SStack(size_t InCapacity = 2u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
        , Size(0u)
    {

    }

    ~SStack()
    {
        delete[] Data;
    }

    size_t GetCapacity() const
    {
        return Capacity;
    }

    size_t GetSize() const
    {
        return Size;
    }

    void Push(const T& InValue)
    {
        if (Full() == true)
        {
            std::cout << __FUNCTION__ << " Full() == true." << std::endl;
            return;
        }
        Data[Size++] = InValue;
    }

    void Pop()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        --Size;
    }

    T& Top()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

    const T& Top() const
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
            exit(0);
        }

        return Data[Size - 1u];
    }

private:
    bool Full() const
    {
        return Size == Capacity;
    }

    bool Empty() const
    {
        return Size == 0u;
    }

private:
    T* Data;

    size_t Capacity;

    size_t Size;

};

void Solve(const std::string& InA, const std::string& InB) 
{
    if (InA.size() == 0u || InB.size() == 0u)
    {
        return;
    }

    std::string Result;

    int Carry = 0;
    int i = InA.size() - 1;
    int j = InB.size() - 1;

    while (0 <= i || 0 <= j || 0 < Carry) 
    {
        int DigitA = (0 <= i) ? InA[i] - '0' : 0;
        int DigitB = (0 <= j) ? InB[j] - '0' : 0;

        int SumDigit = DigitA + DigitB + Carry;
        Result += (SumDigit % 10) + '0';
        Carry = SumDigit / 10;

        --i;
        --j;
    }

    std::reverse(Result.begin(), Result.end());
    std::cout << Result << std::endl;
}

int main() 
{
    std::string a, b;
    std::cin >> a >> b;

    Solve(a, b);

    return 0;
}

 

  Ex) 프로그래머스 Level 0 - 컨트롤 제트  

<hide/>

void Solve(const std::string& InString) 
{
    SStack<int> Stack(200);
    std::istringstream InputStringStream(InString);
    std::string Token;

    while (InputStringStream >> Token) 
    {
        if ("Z" == Token)
        {
            if (0 < Stack.GetSize()) 
            {
                Stack.Pop();
            }
        }
        else 
        {
            Stack.Push(std::stoi(Token));
        }
    }

    int ResultSum = 0;
    while (Stack.GetSize() > 0) 
    {
        ResultSum += Stack.Top();
        Stack.Pop();
    }

    std::cout << ResultSum << std::endl;
}

 

  백준3986)
    스택으로 간단히 풀이가능. 문제 자체가 짝을 짓는 문제라서 스택 활용.

<hide/>

#pragma once

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool isGoodWord(const string& word) {
    std::stack<char> Stack;
    for (const char& Alphabet : word)
    {
        if (Stack.empty() == false && Stack.top() == Alphabet)
        {
            Stack.pop(); // 짝이지어지면 팝.
        }
        else
        {
            Stack.push(Alphabet); // 아니면 푸시.
        }
    }

    return Stack.empty() == true;
}

int main() {
    int N;
    cin >> N;

    int goodWordCount = 0;
    for (int i = 0; i < N; ++i) {
        string word;
        cin >> word;
        if (isGoodWord(word)) {
            ++goodWordCount;
        }
    }

    cout << goodWordCount << endl;
    return 0;
}

 

해커랭크ExtraLongFactorial)
  엄청나게 큰 수의 팩토리얼을 구하는 문제.
  숫자를 하나씩 올려가며 n까지 곱셈을 함. 이걸 스택을 활용.
  중요한 것은 캐리에 대한 개념. 

<hide/>

#pragma once

#include <stack>

void ProductForFactorial(std::stack<int>& InReversedResult, int InNumber)
{
    std::stack<int> NewReversedResult;
    int Carry = 0;

    while (InReversedResult.empty() == false)
    {
        int Digit = InReversedResult.top();
        InReversedResult.pop();

        int Product = Digit * InNumber + Carry;
        int NewDigit = (Product) % 10;
        Carry = (Product) / 10;

        NewReversedResult.push(NewDigit);
    }

    while (0 < Carry)
    {
        NewReversedResult.push(Carry % 10);
        Carry /= 10;
    }

    while (NewReversedResult.empty() == false)
    {
        InReversedResult.push(NewReversedResult.top());
        NewReversedResult.pop();
    }
}

void extraLongFactorials(int n) {
    std::stack<int> ReversedResult;
    ReversedResult.push(1);

    for (int i = 2; i <= n; ++i)
    {
        ProductForFactorial(ReversedResult, i);
    }

    std::stack<int> Result;
    while (ReversedResult.empty() == false)
    {
        Result.push(ReversedResult.top());
        ReversedResult.pop();
    }

    while (Result.empty() == false)
    {
        printf("%d", Result.top());
        Result.pop();
    }
    printf("\n");
}

 

 

2.2-2 큐
  Def) 정의

    먼저 삽입된 데이터가 먼저 제거되는 자료구조.

 

  Note) 장단점

    장점1. 선입선출 한정으로 삽입/삭제에 O(1) 시간복잡도.
    결론. 데이터 스트림, BFS, 이벤트 처리 시에 활용.

  Note) 구현코드

<hide/>

#pragma once

#include <iostream>

template<typename T>
class SQueue 
{
public:
    SQueue(size_t InCapacity = 10u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity) 
        , Size(0u)
        , FrontIndex(0u)
        , RearIndex(0u)
    {
    }

    ~SQueue() 
    {
        delete[] Data;
    }

    void Enqueue(const T& value) 
    {
        if (Full() == true) 
        {
            std::cout << __FUNCTION__ << " Full() == true." << std::endl;
        }
        Data[RearIndex] = value;
        RearIndex = (RearIndex + 1) % Capacity;
        Size++;
    }

    void Dequeue() 
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
        }
        FrontIndex = (FrontIndex + 1) % Capacity;
        --Size;
    }

    T& Front() 
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
        }
        return Data[FrontIndex];
    }

    const T& Front() const 
    {
        if (Empty()) 
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
        }
        return Data[FrontIndex];
    }

    bool Empty() const 
    {
        return Size == 0;
    }

    bool Full() const 
    {
        return Size == Capacity;
    }

    size_t GetSize() const 
    {
        return Size;
    }

private:
    T* Data;           
    
    size_t Capacity;

    size_t Size;

    size_t FrontIndex;
    
    size_t RearIndex;
    
};

 

 

저작자표시 비영리 변경금지

'C++ > 자료구조와 알고리듬' 카테고리의 다른 글

6. Linked list, Hash table  (0) 2022.12.30
5. Dynamic Programming, Backtracking  (0) 2022.12.01
4. Graph, DFS, BFS  (0) 2022.11.22
3. Tree, Binary Search Tree  (0) 2022.11.04
1. Recursive Function, Array  (0) 2022.10.21

관련글

댓글

티스토리툴바