bdfgdfg

스택 LIFO(Last In First Out). 후입 선출방식의 자료구조이다. 앞서 재귀함수를 공부할 때도 자기 자신을 호출하면서 빠져나올 땐 역순으로 빠져나오는 스택의 방식. 간단하게 설명하면 쌓여있는 상자를 생각하면 쉽다. 상자를 밑에서부터 위로 하나하나 차곡차곡 쌓고 뺄 때는 위에서부터 아래로 하나하나씩 뺀다. 이것이 스택의 구조 간단하니 바로 코드를 통해 확인한다. #pragma once template class Stack { public: Stack(); ~Stack(); inline T GetTop() const; inline bool Push(const T& item); inline bool Pop(); inline bool Empty() const; private: enum { MAX ..

원형 연결리스트 원형 연결리스트는 기존의 연결리스트에서 맨 마지막 노드가 첫 번째 노드를 가리키는 형태를 이루는게 원형 연결리스트. 원형 연결리스트는 꼬리(마지막노드)포인터 변수가 따로 없더라도 맨 마지막에 노드를 추가할 수 있다. 다만 헤드보단 꼬리 포인터변수를 통해 원형 연결리스트를 구현하는것이 훨씬 간단하다. 앞서 단순 연결리스트를 구현할때 변경되는것은 앞(머리) 뒤(꼬리)쪽에도 추가할 수 있게 기능을 추가하고 탐색의 경우 원형으로 계속 돌 수 있는 형태이니 다음 노드의 nullptr을 저장하지 않게만 하면 된다. 양방향 연결리스트 단순 연결리스트는 노드가 내 다음에 존재하는 노드만을 가리켰다면 양방향 연결리스트는 내 다음 노드뿐만 아니라 내 이전의 노드도 가리킨다. (노드 클래스에 포인터변수 한개..

재귀함수. 재귀함수는 나(함수)자신을 재 호출하는 함수를 이야기한다. void Recursive() { pritnf("Recursive Call"); Recursive(); } (위의 경우는 탈출조건이 없는 재귀함수) 재귀함수는 함수의 호출순서를 스택으로 쌓고 탈출조건이 완료되면 마지막에 호출되었던 녀석이 역순으로 종료되는 구조. 이 재귀함수는 탈출조건이 존재한다. 매개변수에 인자로 넘겨온 수가 0보다 작게되면 종료. 그림을 보면 호출의 순서와 반환의 순서는 역순이다. 재귀함수를 쓸 수 있는 간단한 예제를 본다. #include int Factorial(int num) { if(num == 1) return 1; else return num * Factorial(num - 1); } int main() ..

시간 복잡도와 공간 복잡도 앞서 자료구조를 살펴보았을 때 앞으로 배워야할 자료구조의 종류는 다양했다. 그 이유는 데이터를 표현하는 방법에서 그냥 만능키와 같은 자료구조와 알고리즘은 존재하지 않기 때문이다. 그렇기에 우리는 어떤 상황에서 자료구조/알고리즘을 선택해야하는지를 판단할 수 있어야한다. 1. 어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가? 2. 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰는가? 이렇듯 알고리즘을 평가하는데에 크게 두 가지 요소가 존재하는데 하나는 '속도'와 관련된 이야기이며 다른 하나는 '공간'에 관한 이야기이다. 속도에 관한 아록리즘의 수행시간 분석결과를 가리켜 '시간 복잡도' 라 하고 메모리 사용량에 대한 분석결과를 가리켜 '공간 복잡도' 라 한다. ..