시간복잡도와 STL (20190412)

1. 시간복잡도

우리의 코드에 대해 시간복잡도를 항상 구해보는 연습을 해야한다.

현재 백준서버의 1초는 10^7~10^8의 반복이라고 생각하자.

for(int i=1; i<=N; i<<=1){
    if (N&i) cnt++;
}

 

뭐하는 코드일까? : i는 자리를 지정해주는 마스크. N을 2진수로 바꿨을 때 1의 개수를 세주는 코드.

시간 복잡도는? : O(log2(N))

 

2. STL(Standard Template Library)

표준 라이브러리

cplusplus.com 에 가면 complexity 등 자세한 정보를 알 수 있음. 구글보단 여기로 ㄱㄱ

 

pair<int,int>

vector<int>

stack<int>

queue<int>

priority_queue<int>

set<int>

map<int,int>

이런게 대표적.

 

struct MyStruct{

    int val;

}

여기서 자료형을 추가하려면 또다른 구조체를 세워야함. 그래서 C++로 넘어올 때

template<typename T>

를 만듬. 이걸 사용하면

struct MyStruct{

    T val;

}

이런식으로 사용된다.

MyStruct<int> asdf;

MyStruct<double> dasdf;

또다른 구조체를 세우는게 귀찮아서 만든거라고 생각하자.

 

(0) using namespace std;

안쓰면 컴파일에러. ㅎㅎㅎ 안쓰고싶으면 std::pair<int,int> 이러면 됩니다 ㅎㅎㅎㅎ 귀찮죠?

 

(1) pair

#include <utility>

자료형 두개를 묶어놓은 것. 묶어서 처리를 할 일이 생길 때 사용.

pair<long long, int> P;

왼쪽에는 배열의 값, 오른쪽에는 배열의 인덱스 이런식으로 용이하게 저장 가능.

첫 번째 자료형은 P.first, 두 번째 자료형은 P.second로 접근 가능.

 

(2) stack

선언 : stack<typename T> name;

연산 : 

  push() : name.push(2) : 스택에 2를 넣음.

  pop() : name.pop() : 꼭대기에 있는 데이터 지움.

  top() : name.top() : 꼭대기에 있는 값 리턴.

  size() : name.size() : 스택 사이즈 리턴.

 

스택이 뭘까? 한쪽이 막혀있고, 한쪽으로만 접근이 가능한 자료형. 중간에 있는 값들은 접근 못함.

백준 문제 : 10828번 스택

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

10828번: 스택

풀이 : 

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
stack<int> st;
int main(){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; ++i){
		char arr[10];
		scanf("%s", arr);
		if(!strcmp(arr, "push")){
			int a;
			scanf("%d", &a);
			st.push(a);
		}
		else if(!strcmp(arr, "top")){
			if(st.empty()) printf("-1\n");
			else printf("%d\n", st.top());
		}
		else if(!strcmp(arr, "size")){
			printf("%d\n", st.size());
		}
		else if(!strcmp(arr, "pop")){
			if(st.empty()) printf("-1\n");
			else {
				printf("%d\n", st.top());
				st.pop();
			}
		}
		else{
			if(st.empty()) printf("1\n");
			else printf("0\n");
		}
	}
}

(3) queue

연산 : 

  push()

  pop()

  front()

  size()

  empty()

 등등..

큐가 뭘까? 양쪽이 뚫려있지만 값을 집어넣는 부분과 값을 빼내는 부분이 다름.

백준 문제 : https://www.acmicpc.net/problem/10845

10845번: 큐

풀이코드 : 

#include <iostream>
#include <string>
#include <queue>
using namespace std;
queue<int> q;
string s;
int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; ++i){
		cin >> s;
		if(!s.compare("push")){
			int a;
			cin >> a;
			q.push(a);
		}
		else if(!s.compare("front")){
			if(q.empty()) cout << "-1" << '\n';
			else cout << q.front() << '\n';
		}
		else if(!s.compare("back")){
			if(q.empty()) cout << "-1" << '\n';
			else cout << q.back() << '\n';
		}
		else if(!s.compare("size")){
			cout << q.size() << '\n';
		}
		else if(!s.compare("pop")){
			if(q.empty()) cout << "-1" << '\n';
			else{
				cout << q.front() << '\n';
				q.pop();
			}
		}
		else if(!s.compare("empty")){
			cout << q.empty() << '\n';
		}
	}
}

 

오늘의 문제 : 괄호 https://www.acmicpc.net/problem/9012

9012번: 괄호

코드 1 : 

#include <iostream>
#include <stack>
#include <string>
using namespace std;


int main(){
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		string s;
		bool k=true;
		stack<int> st;
		cin >> s;
		for(int i=0; i<s.size(); ++i){
			if(s[i]=='('){
				st.push(1);
			}
			else{
				if(st.empty()){
					cout << "NO" << '\n';
					k=false;
					break;
				}
				else st.pop();
			}
		}
		if(k){
			if(st.empty() && k) cout << "YES" << '\n';
			else cout << "NO" << '\n';
		}
	}
}

 

코드 2 : 

#include <iostream>
#include <stack>
#include <string>
using namespace std;



int main(){
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		int st=0;
		string s;
		bool k=true;
		cin >> s;
		for(int i=0; i<s.size(); ++i){
			if(s[i]=='('){
				st++;
			}
			else{
				if(st==0){
					cout << "NO" << '\n';
					k=false;
					break;
				}
				else st--;
			}
		}
		if(k){
			if(st==0 && k) cout << "YES" << '\n';
			else cout << "NO" << '\n';
		}
	}
}