반응형
#include <bits/stdc++.h>
using namespace std;

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

	int n;
	cin >> n;
	vector<int> arr(n+1), dy(n+1);
	
	dy[0]=1;
	dy[1]=1;
	
	for(int i=1; i<=n; i++){
		cin>> arr[i];
	}
	for(int i=2; i<=n; i++){
		int maxx = 0;
		for(int j=i-1; j>=1; j--){
			if(arr[j]<arr[i]){
				maxx = max(dy[j], maxx);
			}
		}
		dy[i] = maxx+1;
	}
	
	int ans=0;
	
	for(int i=1; i<=n;i++){
		ans = max(ans, dy[i]);
	}
	
	cout << ans;
	
	
	
}
반응형
반응형

C++ cout 소수점 n표시 방법

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	double x = 3.333333333;
	
	cout << x << '\n';

}

일반적으로 아무 설정 없이 소수점을 표시하면

3.33333

이런 식으로 표시된다.

 

하지만 알고리즘 문제를 풀거나, 특정한 목적으로 소수점 표시를 적절하게 

 

소수 n번째 자리까지 표시해야 하는 경우가 있다.

 

만약 소수 3번째 자리까지 표시를 하려면

 

cout 이전에

cout << fixed;

cout.precision(3);을 추가해주어야한다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	double x = 3.333333333;
	
	cout << fixed;
	cout.precision(3);
	cout << x << '\n';
}
3.333

 

 

소수점 n번째 자리까지 출력할 때

cout << fixed;
cout.precision(n);
cout << x << '\n';

 

만약 cout<<fixed;를 쓰지 않는다면

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	double x = 3.333333333;
	
	cout.precision(3);
	cout << x << '\n';
}

결과

3.33

소수 3번째자리까지 표시가 아니라

숫자 갯수를 3개까지만 표시한다.

cout.precision(n)은 숫자 n개를 표시한다고 생각하면 편하다.

 

 

 

근데 한번 이렇게 설정할 경우

이 코드 밑에 있는 모든 출력에서 n번 째 자리까지만 출력하게 된다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	double x = 3.333333333;
	
	cout.precision(3);
	cout << x << '\n';
	cout << 1.234567 <<'\n';
}
3.33
1.23

그래서 이 설정을 변경할 필요성이 있다.

 

 

 

설정을 변경 해주려면

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	double x = 3.333333333;
	double y = 1.234567;
	

	cout.precision(3);
	cout << x << '\n';
	cout << y <<'\n';
	
	
	cout.precision(6);
	cout << x << '\n';
	cout << y <<'\n';
	
	
}
3.33
1.23
3.33333
1.23457

다시 출력하기전 위에 코드를 추가해주면 된다.

 

만약 cout.fixed를 초기화 하고 싶다면

cout.unsetf(ios::fixed)를 추가해주면 된다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	double x = 3.333333333;
	double y = 1.234567;
	
	cout << fixed;
	cout.precision(3);
	cout << x << '\n';
	cout << y <<'\n';
	
	cout.unsetf(ios::fixed);
	cout << x << '\n';
	cout << y <<'\n';
	
	
}
3.333
1.235
3.33
1.23

cout.unsetf(ios::fixed) 해서 숫자에서 총 3자리가 출력된다.

cout << fixed 상태에서는 소수점 3자리까지 출력되었다.

 

 

 

cout.precision(n) 소수점 반올림이 되는 문제

 

#include <bits/stdc++.h>
using namespace std;

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

	double y = 1.77777777;
	
	cout << fixed;
	cout.precision(3);
	cout << y <<'\n';

	cout.precision(5);
	cout << y <<'\n';
	
	
}
1.778
1.77778

간혹가다 백준에서 소수를 출력해야하는 문제가 있다.

 

이런 경우 오차범위가 주어진다. 만약 소수점 자리수를 너무 적게 표시할 경우

 

오차범위에 걸려서 문제를 틀릴 수 있다.

 

이럴 경우를 대비해서 소수점 n번째까지 출력을 하라고 명시가 되지 않은 경우에는

 

그냥 소수점 자리수를 길게 출력하면 편하다.

 

소수는 컴퓨터로 계산할 때 항상 오차가 있다.

 

그래서 애초에 정답에 대해서 오차범위를 명시하고

 

오차범위 안에만 들어가면 답이 맞는다.

 

 

예를 들어 절대/상대 오차 10-2까지 허용한다고 하면

 

소수 5번째자릿수 까지 출력해버리면 편하다.

 

반응형
반응형

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

 

4386번: 별자리 만들기

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일

www.acmicpc.net

1. 문제 설명

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며,
최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

 

 

별이 n개 주어지고 별들의 각각 좌표가 주어진다.

 

모든 별을 이용해서 최소 거리, 비용으로 별자리를 만들어야한다.

 

 

2. 접근 방법[알고리즘]

최소 비용으로 모든 별을 이어야 하므로 최소스패닝트리, 최소 신장 트리(MST)를 만들어야한다.

 

크루스칼 알고리즘이나 프림 알고리즘을 사용해서 만들면 된다.

 

나는 크루스칼 알고리즘을 이용했다.

 

 

 

 

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int unf[10001];

struct Edge{
	int v1;
	int v2;
	double val;
	Edge(int a, int b, double c){
		v1=a;
		v2=b;
		val=c;
	}
	bool operator<(const Edge &b) const{
		return val>b.val;
	}
};

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a] = b;
}

double dist(pair<double, double> &a , pair<double, double> &b){
	return sqrt(pow(a.first-b.first,2) + pow(a.second - b.second,2));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	priority_queue<Edge> Q;
	double res=0;
	int n;
	vector<pair<double, double> > star;
	
	cin >> n;
	for(int i=0; i<n; i++){
		double x,y;
		cin >> x >> y;
		star.push_back(make_pair(x,y));
	}
	
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			Q.push(Edge(i,j, dist(star[i],star[j])));
		}
	}
	
	for(int i=0; i<n; i++){
		unf[i] = i;
	}
	
	
	while(!Q.empty()){
		int node_a = Q.top().v1;
		int node_b = Q.top().v2;
		double d = Q.top().val;
		Q.pop();
		
		if(Find(node_a)!=Find(node_b)){
			Union(node_a, node_b);
			res += d;
		}		
	}
	cout << fixed;
	cout.precision(3);
	cout << res ;
	
	
}

문제에서 출력을 절대/상대 오차 10-2까지 허용한다고 해서

 

아예 소수 세번째 자리까지 출력했다.

 

출력과정에서 반올림이 될 수도 있다고 생각해서 널널하게 세번째까지 출력했다.

 

input을 star에 입력해주었다.

 

그리고 모든 star 요소에 대해서 각 거리를 구해 우선순위 큐(최소힙)에 넣고

 

두 별 사이의 거리가 최소인 Edge를 최소힙에서 꺼내서 Union&Find 알고리즘을 이용하여

 

이미 두 별이 연결되어 있으면 넘어가고, 연결되어 있지 않으면 연결해주고

 

그 두 별 사이의 거리를 res 변수에 더해주었다.

 

최소스패닝트리를 구하는 걸 연습하기 좋은 문제다.

 

반응형
반응형
#include <bits/stdc++.h>
using namespace std;

int dy[101];
int DFS(int n){
	if(dy[n]>0) return dy[n];
	if(n==1 || n==2) return n;
	else return dy[n]=DFS(n-1) + DFS(n-2);	
}

int main(){
//	freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	cout << DFS(n);
	return 0;
	
}
반응형

'Algorithm > etc' 카테고리의 다른 글

냅색 문제  (0) 2022.01.26
LIS 최대 부분 증가수열 - DP  (0) 2022.01.25
라이언 킹 심바 BFS 문제  (0) 2022.01.24
미로 최단거리 BFS 활용  (0) 2022.01.22
피자 배달 거리 문제 - DFS 활용 , 순열 조합 활용  (0) 2022.01.22
반응형

1. ios::sync_with_stdio(false), cin.tie(0) 은 무엇인가?

보통 백준, 프로그래머스 같은 온라인 저지 사이트에서 C++을 이용하여 알고리즘 문제를 풀 때

 

시간초과를 방지하기 위해서 이 두 줄을 추가해줍니다.

 

	ios::sync_with_stdio(false);
	cin.tie(0);

 

기존 입출력을 cin, cout, printf, scanf 함수를 이용해 했다가

 

cin과 cout만을 이용하고

 

이렇게 두 줄만 추가해주면 시간초과로 인해 틀렸던 문제가

 

맞는 경우가 종종 있습니다.

 

그 이유는 문제에서 입출력 양이 굉장히 많아지면,

 

입출력하는데 소모시간이 많아져서 시간초과가 발생하기 때문입니다.

 

위 코드를 작성하면 입출력 속도가 빨라지고, 그로인해 시간초과로 틀렸던 문제가 맞게 됩니다.

 

그렇다면 이 두줄의 의미는 무엇일까요?

 

 

 

1-1. ios::sync_with_stdio(false)

이 코드는 C와 C++ 표준 stream의 동기화를 비활성화합니다.

 

동기화가 활성화 되어있을 땐 C 스타일과 C++스타일의 입출력을 혼합해도 문제가 없습니다.

예를 들어 C스타일(printf scanf) C++스타일(cin cout)을 혼합하여 사용해도 문제가 없습니다.

 

하지만 이 코드를 작성하면 C 스타일과 C++ 스타일이 혼합할 수 없는 대신에,

C++ 스타일 코드만 사용하면 기존 동기화 과정에서 필요하던 시간이 절약되어

입출력 속도가 빨라지는 효과가 있습니다.

 

즉 알고리즘 문제를 풀 때는 표준 stream의 동기화는 필요없고 시간이 절약되는 게 우선이니

ios::sync_with_stdio(false)를 사용하여 입출력 시간을 절약할 수 있습니다.

 

다만 이 코드를 사용하면 기존 C의 표준 입출력인

scanf, printf, getchar 함수를 사용하면 오류가 발생할 수 있습니다.

C++의 입출력인 cin, cout만 사용하도록 주의해야합니다.

 

 

 

1-2. cin.tie(null)

cin.tie는 평소 cin과 cout을 묶어줍니다. 

cout << "Write your name, please \n" <<;
cin >> name;

이런 코드가 있다면

 

평소에는 cin과 cout이 하나로 묶어져 있어서 

"Write your name, please \n" 가 반드시 먼저 출력된 후 이름을 입력할 수 있습니다.

 

그러나 cin.tie(0)이나 cin.tie(null) 코드를 추가해 주면

"Write your name, please \n" 출력이 되기 전에 이름을 입력할 수 있습니다.

내부적으로 cin과 cout을 묶어주는 과정을 수행하지 않기 때문에 시간이 절약됩니다.

 

다른 프로그램에서 이렇게 사용한다면 이름을 입력해달라고 요구하기 전에

입력을 할 수 있는 자연스럽지 못한 프로그래밍일 수 있습니다.

 

그러나 알고리즘 문제를 풀 때는 크게 상관이 없고,

입출력 시간을 절약할 수 있기 때문에 cin.tie(0) 코드를 많이 사용합니다.

 

 

2. ios::sync_with_stdio(false), cin.tie(0) 사용 효과

입출력 시간을 백준에서 비교한 글이 있습니다.

 

백준 입력속도비교
백준 출력 속도 비교

 

확실히

 

	ios::sync_with_stdio(false);
	cin.tie(0);

이 코드를 사용하여 입출력을 하면

 

보다 빠른 속도로 입출력을 할 수 있는 것을 알 수 있습니다.

 

출처입니다.

https://www.acmicpc.net/blog/view/56

 

입력 속도 비교

여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일

www.acmicpc.net

 

 

3. scanf, printf vs cin, cout

scanf printf 와 cin cout을 비교하면

 

일반적으로 scanf printf가 cin cout보다 속도가 빠르지만,

	ios::sync_with_stdio(false);
	cin.tie(0);

이 코드를 추가하고 cin cout을 사용하면 기존의 scanf printf 속도보다 빨라집니다.

 

코테나 알고리즘 문제를 풀 때 입출력 시간을 절약하기 위해서

 

위 코드와 함께 cin cout을 이용해서 프로그래밍 하는 것이 좋습니다.

 

 

etc

입출력할 때 개행을 하려면 

endl 대신 '\n' 을 사용해야 시간을 절약할 수 있습니다.

 

std::cout<<ans<<std::endl;
std::cout << ans << '\n';

 

 

 

stackoverflow 사이트에 게시된

ios::sync_with_stdio(false),  cin.tie(0)와 관련한 글입니다.

 

이 글의 답변 내용 중

 

"The two calls have different meanings that have nothing to do with performance; the fact that it speeds up the execution time is (or might be) just a side effect. You should understand what each of them does and not blindly include them in every program because they look like an optimization."

 

"두 호출은 성능과 아무 관련이 없는 다른 의미를 갖습니다.

실행 시간을 단축한다는 사실은 단지 부작용일 뿐입니다.

최적화처럼 보이기 때문에 각각의 기능을 이해하고

모든 프로그램에 맹목적으로 포함하지 않아야 합니다."

 

즉 이 코드는 웬만하면 알고리즘 문제를 풀 때 시간절약하기 위해서 사용하는 것이지,

모든 프로그램에 입출력 시간을 절약하기 위해서 사용하는 올바른 방법은 아님

말하고 있습니다.

 

참고하셔서 사용하면 좋을 것 같아요.

 

https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull

 

Significance of ios_base::sync_with_stdio(false); cin.tie(NULL);

What is the significance of including ios_base::sync_with_stdio(false); cin.tie(NULL); in C++ programs? In my tests, it speeds up the execution time, but is there a test case I should be worried...

stackoverflow.com

 

 

읽어주셔서 감사합니다.

반응형

'C++' 카테고리의 다른 글

[C2512 Error]no appropriate default constructor available C++ 오류  (0) 2022.01.25
cout 소수점 표시, 소수점 n자리까지 표시하기  (0) 2022.01.24
C++ map STL 사용법  (0) 2022.01.24
C++ 반올림  (0) 2022.01.10
C++ 2차원 벡터 선언  (0) 2022.01.10
반응형

map 자료 구조를 통해 특정 문자나 단어의 등장횟수를 쉽게 셀 수 있다.

 

1. 알파벳 등장 횟수 출력하기

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	map<char, int> ch;
	map<char, int>::iterator it;
	
	char a[100];
	cin >> a; 
	
	for(int i=0; i<a[i]!='\0'; i++){
		ch[a[i]]++;
	}
	
	for(it=ch.begin(); it!=ch.end(); it++){
		cout << it->first << " " << it->second<<'\n';
	}
	


}

map 자료구조를 이용할 때는 자료에 대해

 

이터레이터로 접근할 수 있다.

 

input

aaaabbbcdcdcaa

 

output

a 6
b 3
c 3
d 2

 

 

 

2. 단어 등장 횟수 출력하기

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	map<string, int> ch;
	map<string, int>::iterator it;
	string s;
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin>>s;
		
		ch[s]++;
	}
	
	
	for(it=ch.begin(); it!=ch.end(); it++){
		cout << it->first << ' '<<it->second << '\n';
		
	}
	
	

}

input---

7
book
dog
cat
dog
cat
book
cat

 

 

output----

book 2
cat 3
dog 2

반응형
반응형
#include <bits/stdc++.h>
using namespace std;

int n, arr[30][30],ch[30][30],res;


int dx[4] = {-1,0,1,0};
int dy[4] = {0, -1,0, 1};


struct State{
	int x,y,dis;
	
	State(int a, int b, int c){
		x = a;
		y = b;
		dis = c;
	}
	bool operator<(const State &bb) const{
		if(dis==bb.dis){
			if(x==bb.x) return y>bb.y;
			else return x>bb.x;
		}
		else return dis>bb.dis;
	}
	
};

struct Lion{
	int x,y, size=2, eat=0;
	
	void sizeup(){
		size++;
		eat=0;
	}
};

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	Lion Simba;
	
	scanf("%d",&n);
	priority_queue<State> Q;
	for(int i=0; i<n; i++){
		for(int j=0; j<n;j++){
			int tmp;
			scanf("%d",&tmp);
			if(tmp==9){
				Simba.x = i;
				Simba.y = j;
			}
			else{
				arr[i][j] = tmp;
			}
		}
	}
	// 심바현재위치에서 갈수 있는 점들 탐색 
	// 갈수 있는 점들 우선순위 큐에 넣어준다.
	// 우선순위큐에서 우선순위 가장 높은 방문할 정점(지나갈 수 있는 것)을 뽑는다.
	// 그 정점이 먹을 수 있으면 먹고 , 심바 위치를 그 정점으로 바꿔준다. 
	// 큐는 먹이 정점을 모두다 방문 하면 끝난다.
	 
	
	
	Q.push(State(Simba.x, Simba.y, 0));
	while(!Q.empty()){
		int cur_x = Q.top().x;
		int cur_y = Q.top().y;
		int cur_dis = Q.top().dis;
		Q.pop();
		if(arr[cur_x][cur_y]!=0 && arr[cur_x][cur_y]<Simba.size){
			Simba.x=cur_x;
			Simba.y=cur_y;
			Simba.eat++;
			if(Simba.eat >= Simba.size) Simba.sizeup();
			arr[cur_x][cur_y] = 0;
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					ch[i][j]=0;
				}
			}
			while(!Q.empty()) Q.pop();
			res = cur_dis;
		}
		
		for(int i=0; i<4; i++){
			int nx = cur_x+dx[i];
			int ny = cur_y+dy[i];
			
			if(nx<0||nx>=n||ny<0||ny>=n||ch[nx][ny]>0) continue;
			if(arr[nx][ny] > Simba.size) continue;
			ch[nx][ny] = 1;
			Q.push(State(nx,ny,cur_dis+1));
				
		}	
		
	}
	
	printf("%d",res);
	

}
반응형
반응형
#include <bits/stdc++.h>
using namespace std;

struct Node{
	int row, col;
	Node(int a, int b){
		row=a;
		col=b;
	}
	
};

int arr[7][7];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	queue<Node> Q;

	for(int i=0; i<7; i++){
		for(int j=0; j<7; j++){
			scanf("%d",&arr[i][j]);
			if(arr[i][j]==1) arr[i][j] = -1;
		}
	}
	arr[0][0] = 1;
	Q.push(Node(0,0));
	while(!Q.empty()){
		int x = Q.front().row;
		int y = Q.front().col;
		Q.pop();
		
		if(x==6 && y==6) break;
		
		
		for(int i=0; i<4; i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx<0||nx>6||ny<0||ny>6) continue;
			if(arr[nx][ny]==-1 || arr[nx][ny]>0) continue;
			
			arr[nx][ny] = arr[x][y]+1;
			Q.push(Node(nx,ny));
		}
	}
	
	printf("%d",arr[6][6]-1);
}

장애물을 -1로 두고

 

거리를 양수로 표기하면서 BFS를 돌면 편하다.

 

첫 시작점도 방문했다는걸 표기하기 위해 1로 둔다.

 

나중에 답을 구할 땐 1을 다시 빼준다.

반응형

+ Recent posts