선입선출 구조이다.

 

 

구현 사항

push : O(1)

pop : O(1)

front : O(1)

 

 

코드

더보기 
template <typename _Ty>
class MyQueue {
public:
	explicit MyQueue() : lst_() {}
	
	~MyQueue() {}

public:
	inline void push(const _Ty& _val)
	{
		lst_.push_back(_val);
	}

	inline void push(_Ty&& _val)
	{
		lst_.push_back(std::move(_val));
	}

	inline void pop()
	{
		lst_.pop_front();
	}

	inline _Ty& front()
	{
		return lst_.front();
	}

	inline bool empty() const { return size() == 0; }

	inline const int& size() const { return lst_.size(); }

private:
	MyLinkedList<_Ty> lst_;
};
저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Stack  (0) 2023.02.13
Linked List  (0) 2023.02.13
Divide & Conquer  (0) 2023.02.10
Recursion Basics  (0) 2023.02.09
Bit Manipulation  (0) 2023.02.09

후입선출 구조이다.

 

구현 사항

push : O(1)

pop : O(1)

top : O(1)

 

 

코드

더보기 
#pragma once

#include "GlobalDefine.h"
#include "MyVector.h"

template <typename _Ty>
class MyStack {
public:
	explicit MyStack() : vec_() {}

	~MyStack() {}

public:
	inline void push(const _Ty& _val)
	{
		vec_.push_back(_val);
	}

	inline void push(_Ty&& _val)
	{
		vec_.push_back(std::move(_val));
	}

	inline void pop()
	{
		vec_.pop_back();
	}

	inline _Ty& top()
	{
		return vec_.back();
	}

	inline bool empty() const { return size() == 0; }

	inline const int& size() const { return vec_.size(); }

private:
	MyVector<_Ty> vec_;
};

 

 

Stock Span

BOJ 2493 탑 https://www.acmicpc.net/problem/2493

위의 문제와 같은 개념이다.

요점은 입력된 값마다 인덱스를 붙이고, 현재 입력된 값보다 큰 값을 찾을때까지 pop을 수행한다.

pop되는 값이 추후 입력되는 값보다 작더라도 어차피 현재 입력된 값보다 작기 때문에 pop을 해도 상관없다.

일종의 그리디 알고리즘이다.

 

코드

더보기 
#include <iostream>
#include <stack>
using namespace std;

void stockSpan(int price[], const int& n, int span[]) {
	stack<pair<int,int>> st;

	for (int i = 0; i < n; ++i) {
		while (!st.empty() && st.top().second < price[i])
			st.pop();

		if (st.empty())
			span[i] = 1;
		else
			span[i] = i - st.top().first;

		st.push({ i, price[i] });
	}
}

int main() {
	int price[] = { 100, 80, 60, 70, 60, 75, 85 };
	int n = sizeof(price) / sizeof(int);
	int span[1000] = {};

	stockSpan(price, n, span);

	for (int i = 0; i < n; ++i)
		cout << span[i] << ' ';

	return 0;
}
저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Queue  (0) 2023.02.15
Linked List  (0) 2023.02.13
Divide & Conquer  (0) 2023.02.10
Recursion Basics  (0) 2023.02.09
Bit Manipulation  (0) 2023.02.09

시퀀스 컨테이너이지만 vector와 다르게 배열이 아닌 노드 기반으로 구현되어있다. 즉, 연속된 메모리 공간이 아니다.

 

 

구현 사항

 

 

코드

더보기 
#include "GlobalDefine.h"

template<typename T>
class MyLinkedList {
private:
    struct Node {
    public:
        Node() = delete;

        explicit Node(const T& d) :
            data(d),
            prev(nullptr),
            next(nullptr)
        {
            std::cout << "왼값 노드 생성" << std::endl;
        }

        explicit Node(T&& d) noexcept :
            data(std::move(d)),
            prev(nullptr),
            next(nullptr)
        {
            std::cout << "오른값 노드 생성" << std::endl;
        }

        explicit Node(const Node& _node) :
            data(_node.data),
            prev(nullptr),
            next(nullptr)
        {
            std::cout << "노드 복사" << std::endl;
        }

        explicit Node(Node&& _node) noexcept :
            data(std::move(_node.data)),
            prev(nullptr),
            next(nullptr)
        {
            std::cout << "노드 이동" << std::endl;
        }
        
        ~Node() { SAFE_DELETE(next) }

    public:
        Node& operator=(const Node& _node)
        {
            data = _node.data;
            prev = nullptr;
            next = nullptr;
        }

        Node& operator=(Node&& _node)
        {
            data = std::move(_node.data);
            prev = std::move(_node.prev);
            next = std::move(_node.next);

            _node.data = 0;
            _node.prev = nullptr;
            _node.next = nullptr;
        }

    public:
        T data;
        Node* prev;
        Node* next;
    };

public:
    explicit MyLinkedList() : 
        head_(nullptr),
        tail_(head_),
        current_(head_),
        size_(0)
    {}

    explicit MyLinkedList(const MyLinkedList& list) :
        head_(nullptr),
        tail_(head_),
        current_(head_),
        size_(0)
    {
        this->operator=(list);
    }

    explicit MyLinkedList(MyLinkedList&& list) noexcept :
        head_(list.head_),
        tail_(list.tail_),
        current_(head_),
        size_(list.size_)
    {
        this->operator=(std::forward<MyLinkedList>(list));
    }

    ~MyLinkedList() { SAFE_DELETE(head_); }

public:
    MyLinkedList& operator=(const MyLinkedList& list) {
        std::cout << "왼값 복사 연산" << std::endl;
        Node* node = list.head_;

        while (node) {
            push_back(node->data);
            node = node->next;
        }

        return *this;
    }

    MyLinkedList& operator=(MyLinkedList&& list) noexcept {
        std::cout << "오른값 이동 연산" << std::endl;
        head_ = list.head_;
        tail_ = list.tail_;
        current_ = list.current_;
        size_ = list.size_;

        list.head_ = nullptr;
        list.tail_ = nullptr;
        list.current_ = nullptr;
        list.size_ = 0;

        return *this;
    }

public:
    void push_front(const T& data) {
        Node* newNode = new Node(data);

        if (!head_) {
            head_ = tail_ = newNode;
        }
        else {
            newNode->next = head_;
            newNode->prev = nullptr;
            head_->prev = newNode;
            head_ = newNode;
        }
        ++size_;
    }

    void push_front(T&& data) noexcept {
        Node* newNode = new Node(std::move(data));

        if (!head_) {
            head_ = tail_ = newNode;
        }
        else {
            newNode->next = head_;
            newNode->prev = nullptr;
            head_->prev = newNode;
            head_ = newNode;
        }
        ++size_;
    }

    void push_back(const T& data) {
        Node* newNode = new Node(data);

        if (!tail_) {
            head_ = tail_ = newNode;
        }
        else {
            newNode->next = nullptr;
            newNode->prev = tail_;
            tail_->next = newNode;
            tail_ = newNode;
        }
        ++size_;
    }

    void push_back(T&& data) noexcept {
        Node* newNode = new Node(std::move(data));

        if (!tail_) {
            head_ = tail_ = newNode;
        }
        else {
            newNode->next = nullptr;
            newNode->prev = tail_;
            tail_->next = newNode;
            tail_ = newNode;
        }
        ++size_;
    }

    void pop_front() {
        Node* temp = head_;

        if (head_ != tail_) {
            head_->next->prev = nullptr;
            head_ = head_->next;
        }
        else {
            head_ = tail_ = nullptr;
        }

        temp->prev = nullptr;
        temp->next = nullptr;
        SAFE_DELETE(temp);
        --size_;
    }

    void pop_back() {
        Node* temp = tail_;

        if (tail_ != head_) {
            tail_->prev->next = nullptr;
            tail_ = tail_->prev;
        }
        else {
            head_ = tail_ = nullptr;
        }

        temp->prev = nullptr;
        temp->next = nullptr;
        SAFE_DELETE(temp);
        --size_;
    }

    void insert(const T& d)
    {
        if (!current_ || !current_->next) {
            push_back(std::forward<T>(d));
        }
        else {
            Node* temp = new Node(d);

            temp->next = current_->next;
            temp->prev = current_;
            current_->next->prev = temp;
            current_->next = temp;
            ++size_;
        }
    }

    void remove(const T& d)
    {
        Node* target = this->find(d);

        if (!target) return;

        if (!target->prev) {
            pop_front();
        }
        else if (!target->next) {
            pop_back();
        }
        else {
            target->prev->next = target->next;
            target->next->prev = target->prev;

            target->prev = nullptr;
            target->next = nullptr;

            SAFE_DELETE(target);
            --size_;
        }
    }

    T& front() {
        if (!head_) abort();
        return head_->data;
    }

    T& back() {
        if (!head_) abort();
        return tail_->data;
    }

    inline const int& size() const { return size_; }

private:
    Node* find(const int& data) {
        Node* n = head_;

        while (n && n->data != data)
            n = n->next;

        return n;
    }

private:
	Node* head_;
	Node* tail_;
    Node* current_;

	int size_;
};
저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Queue  (0) 2023.02.15
Stack  (0) 2023.02.13
Divide & Conquer  (0) 2023.02.10
Recursion Basics  (0) 2023.02.09
Bit Manipulation  (0) 2023.02.09

Merge Sort(병합 정렬)

배열을 충분히 작은 크기까지 반으로 계속 쪼개고 합치는 과정에서 정렬을 수행한다.

 

void merge(vector<int>& arr, const int& start, const int& end) {
    int i = start;
    int mid = (start + end) / 2;
    int j = mid + 1;
    
    vector<int> temp;    
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j])
            temp.emplace_back(arr[i++]);
        else
            temp.emplace_back(arr[j++]);
    }
    
    while (i <= mid) temp.emplace_back(arr[i++]);
    while (j <= end) temp.emplace_back(arr[j++]);
    
    int k = 0;
    for (int idx = start; idx <= end; ++idx)
        arr[idx] = temp[k++];            
}

void merge_sort(vector<int>& arr, const int& start, const int& end) {
    if (start >= end) return;
    
    int mid = (start + end) / 2;
    merge_sort(arr, start, mid);
    merge_sort(arr, mid + 1, end);

    merge(arr, start, end);
}

 

 

먼저 전체 배열 길이의 절반에 해당되는 인덱스 mid를 구하고 start~mid, mid+1~end 2개의 구간으로 나누어 재귀적으로 분할한 뒤에 합친다.

 

공간 복잡도는 O(N), 시간 복잡도는 O(NlogN)이다.

 

 

Quick Sort(퀵 정렬)

병합 정렬과 마찬가지로 분할 정복 알고리즘이지만 분할이 균일하게 이루어지지 않는다.

pivot값을 기준으로 대략적인 정렬이 이뤄진 후에 pivot값의 위치가 확정되며 그 위치를 기준으로 분할된다.

 

// 원래 알고있는 코드
void quick_sort(vector<int>& arr, const int& start, const int& end) {
    if (start >= end) return;

    int pivot = arr[start];
    int left = start + 1;
    int right = end;

    while (left < right) {
        while (pivot >= arr[left]) left++;
        while (pivot < arr[right]) right--;

        if (left < right) swap(arr[left], arr[right]);
    }

    swap(pivot, arr[right]);

    quick_sort(arr, start, right -1);
    quick_sort(arr, right + 1, end);
}

 

// 강의에서 제시한 코드
int partition(vector<int>& arr, const int& start, const int& end) {
    int pivot = arr[start];
    int i = start - 1;
    
    for (int j = start; j < end; ++j) {
        if (arr[j] < pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    
    swap(arr[i+1], arr[end]);
    return i+1;
}

void quick_sort(vector<int>& arr, const int& start, const int& end) {
    if (start >= end) return;
    
    int p = partition(arr, start, end);
    quick_sort(arr, start, p-1);
    quick_sort(arr, p+1, end);
}
저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Stack  (0) 2023.02.13
Linked List  (0) 2023.02.13
Recursion Basics  (0) 2023.02.09
Bit Manipulation  (0) 2023.02.09
Vector Data Structure  (0) 2023.02.08

배열의 정렬 여부 확인

bool isSorted(int arr[], int n) {
    if (n==1 || n==0) return true;
    if (arr[0] < arr[1] && isSorted(arr+1, n-1)) return true;
    return false;
}

배열의 시작위치와 크기를 1씩 감소시켜가며 맨 앞쪽을 계속 비교해나간다.

시간복잡도는 O(n)이지만 콜스택을 생각하면 n이 어느정도 커지면 실행이 안될것이다.

 

 

DP와 재귀는 Bottom-up, Top-down 여부에 차이가 있을 뿐 접근 방식은 거의 동일하다.

저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Linked List  (0) 2023.02.13
Divide & Conquer  (0) 2023.02.10
Bit Manipulation  (0) 2023.02.09
Vector Data Structure  (0) 2023.02.08
Pointers & Dynamic Memory  (0) 2023.02.07

+ Recent posts

티스토리툴바