굳건하게

문제 : https://www.acmicpc.net/problem/10773

[알고리즘풀이]

0이 입력으로 들어오면, 가장 최근에 들어온 입력을 삭제해줘야 되는 문제이다.

즉, LIFO( Last In First Out ) 형식의 자료 구조인 스택을 이용하는 문제이다.

0이 아닌 입력을 Stack에 Push하고 0이 들어오면 Stack을 Pop하면 된다.

#include<iostream>
#include<stack>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n;
	stack<int> s;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;
		if (input == 0)
			s.pop();
		else
			s.push(input);
	}
	int answer = 0;
	while (!s.empty()) {
		answer += s.top();
		s.pop();
	}
	cout << answer;
}

문제 : https://www.acmicpc.net/problem/10828

[알고리즘풀이]

자료구조 스택을 선언하고, 입력에 맞춰서 명령을 실행하면 되는 문제입니다.

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

using namespace std;

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

	stack<int> s;
	int t;
	cin >> t;
	while (t--) {
		string input, input2;
		cin >> input;
		if (input == "push") {
			cin >> input2;
			s.push(stoi(input2));
			continue;
		}

		if (input == "pop") {
			if (s.empty()) {
				cout << "-1\n";
			}
			else{
				cout << s.top() << '\n';
				s.pop();
			}
		}
		else if (input == "size") {
			cout << s.size() << '\n';
		}
		else if (input == "empty") {
			if (s.empty())
				cout << "1\n";
			else
				cout << "0\n";
		}
		else if (input == "top") {
			if (s.empty()) {
				cout << "-1\n";
			}
			else
				cout << s.top() << '\n';
		}
		else {
			s.push((int)input[4]);
		}
	}
}

안녕하세요, 여행벌입니다.

오늘은 자료구조 '스택' 과 C++ STL 스택 라이브러리를 이용하는 방법에 대해 다뤄보겠습니다.

1. 스택(Stack)

스택은 LIFO( Last In First Out ) 형식의 자료 구조로, 한쪽 끝에서만 자료를 넣고 뺄 수 있습니다.

즉, 마지막에 들어온 원소가 제일 먼저 나갈 수 있는 자료 구조입니다.

위의 그림과 같이, 스택의 Top 부분에서만 Push 와 Pop이 이뤄질 수 있습니다.

2. C++ STL 스택 라이브러리 기본 명령어

선언
- stack<자료형> 변수명 : 선언한 자료형 변수들을 담는 Stack을 선언.
ex) stack<int> s : int형 변수들을 담는 s라는 이름의 stack을 선언.

추가 및 삭제
- push(element) : top에 원소를 추가
- pop() : top에 있는 원소를 삭제

서칭
- top() : top(스택의 처음이 아닌 가장 끝)에 있는 원소를 반환

기타
- empty() : 스택이 비어있으면 true 아니면 false를 반환
- size() : 스택 사이즈를 반환

더 많은 함수들이 있지만, 위의 기본 명령어들만 잘 익히면 충분히 자료구조 Stack을 활용할 수 있습니다.

그럼 다음 예제를 통해 더 공부해볼까요?

#include<iostream>
#include<stack>

using namespace std;


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

	stack<int> s; // int 형은 담는 s라는 이름의 stack 선언
	for (int i = 1; i <= 10; i++)
		s.push(i); // 1 ~ 10 까지 stack 에 담는다.
	for (int i = 1; i <= 10; i++) {
		cout << "현재 stack의 top : " << s.top() << '\n';
		s.pop();
	}
}

1 부터 10까지 차례대로 Stack에 담고 Pop 을 10번 시행해보겠습니다.

위의 그림과 같이 스택의 아래에서부터 Top까지 1 ~ 10 이 Push 되고, 이를 차례대로 Pop 한다면,

현재 stack의 top : 10
현재 stack의 top : 9
현재 stack의 top : 8
현재 stack의 top : 7
현재 stack의 top : 6
현재 stack의 top : 5
현재 stack의 top : 4
현재 stack의 top : 3
현재 stack의 top : 2
현재 stack의 top : 1

다음과 같이 출력될 것입니다!

오늘은 여기서 포스팅을 마치도록 하겠습니다.

자료구조 스택에 대한 기본적인 설명과 C++ STL Stack Library 기본 명령어를 정리해보았습니다.

안녕하세요, 여행벌입니다.

오늘은 C++로 수행 시간을 측정하는 '시간 초 재기' 코드를 구현해보겠습니다.

#include <ctime>

'ctime' Library를 이용해서 수행 시간을 측정할 수 있습니다.

#include<iostream>
#include<ctime>

using namespace std;

int main(void) {

	clock_t start, end;
	double duration;

	start = clock();
	/* 수행 시간을 측정하고 싶은 코드 */
	end = clock();

	cout << (double)(end - start) / CLOCKS_PER_SEC << '\n';
}

clock_t 변수와 clock() 함수를 활용해서, 시작 시간과 끝 시간을 저장해

서로 빼주면 그 사이의 수행 시간을 측정할 수 있습니다.

코드는 간단하지만 시간 측정은 내 알고리즘과 다른 분들의 알고리즘을 가시적으로 비교할 때 유용하게 사용할 수 있으므로,

익혀두면 좋을 것 같습니다!