okayoki

#문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

#작성 코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N, M, V;
vector<int> node[1001];	// 정점 최대 1000개
// dfs와 bfs에서 사용할 방문여부 체크 배열 
bool visitDfs[1001]={ false, };

queue<int> bfsQ;		// bfs결과를 순서대로 저장하기위한 큐 
bool visitBfs[1001]={ false, }; 

void dfs(int v, int cnt){
	int x=v;
	visitDfs[v] = true;
	printf("%d ", x);
	
	// N개 노드 모두 방문했다면 dfs함수 종료 
	if( cnt==N ){
		return;	
	}

	// node[v]에 연결된 노드 중 방문하지 않았던 노드들 반복적으로 방문. 
	for(vector<int>::iterator i=node[v].begin(); i<node[v].end(); i++){
		if( visitDfs[*i]==true ) continue;
		dfs(*i, cnt+1);
	}	
} 
void bfs(int v){
	// 처음에 방문하는 정점을 큐에 넣는다. 
	visitBfs[v] = true;
	bfsQ.push(v);
	
	// 큐가 빌 때까지 반복 
	while( !bfsQ.empty()){
		int x = bfsQ.front();		// 큐의 front에 있는 정점 정보 저장, 출력하고 pop 
		printf("%d ", x);
		bfsQ.pop();
		// 큐의 front에 있던 정점에 연결된 정점들 중 방문하지 않은 정점을 숫자가 작은 순서대로 큐에 저장 
		for(vector<int>::iterator i=node[x].begin(); i<node[x].end(); i++){
			int y = *i;
			if( visitBfs[y]==false ){
				bfsQ.push(y);
				visitBfs[y] = true;
			}
		}
	}
}
int main(){
	// 정점개수, 간선개수, 탐색 시작할 정점 번호 
	scanf("%d %d %d", &N, &M, &V);
	for(int i=1; i<=N; i++){
		node[i].push_back(i);
	}
	for(int i=1; i<=M; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		node[a].push_back(b);
		node[b].push_back(a);
	}
	// 각 노드의 연결상태 오름차순으로 정렬(맨 앞: 부모) 
	for(int i=1; i<=N; i++){
		sort(node[i].begin(), node[i].end());
	} 
	dfs(V,0);
	printf("\n");
	bfs(V);
	return 0;
}

##

N : 정점. 최대 1000개 입력 가능 하므로 vector<int> node[1001] 생성. 인덱스 1~1000까지 사용한다.

M : 간선. 최대 10000개 입력 가능.

#문제

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

#작성 코드

#include <cstdio>

int T, N;
long long int memo[101];
long long int pn(int n){
	if( n==1 ) return 1;
	if( n==2 ) return 1;
	if( n==3 ) return 1;
	if( n==4 ) return 2;
	if( n==5 ) return 2;
	if( n==6 ) return 3;
	if( n==7 ) return 4;
	if( n==8 ) return 5;
	
	if( memo[n]!=0 ) return memo[n];
	return memo[n] = pn(n-1)+pn(n-5);
}
int main(){
	scanf("%d",&T);
	for(int i=0; i<T; i++){
		scanf("%d", &N);
		printf("%lld\n", pn(N));
	}
} 

##

P(1) ~ P(6)까지는 주어진 수열을 그대로 사용하고,

 P(7)부터 P(N) = P(N-1)+P(N-5) 라는 규칙이 생긴다.

#문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

첫 번째 줄에 자연수 N이 주어진다.(N ≤ 1,000,000)

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

#작성 코드

#include <cstdio>
int N;
int memo[1000001];
int binary(int n){
	if( n==1 ) return 1;
	if( n==2 ) return 2;
	
	if( memo[n]!=0 ) return memo[n];
	// 15746으로 나눈 나머지를 출력하는 것이 목표이므로
	// 처음부터 15746으로 나눈 나머지를 저장해준다. 
	return memo[n] = (binary(n-1)+binary(n-2))%15746;
}

int main(){
	scanf("%d", &N);
	printf("%d", binary(N));
	return 0;
}

##

n=1 -> 1

n=2 -> 11, 00

n=3 -> 111, 001 100

n=4 -> 1100, 0000 / 1111, 0011, 1001

             n=2결과에 00 붙인것 / n=3결과에 1 붙인것

n=5 -> 11100, 00100, 10000 / 11001, 0001, 11111, 00111, 10011

              n=3결과에 00 붙인것 / n=4결과에 1 붙인것

위와 같은 규칙성을 찾을 수 있다.

=> tile(n) = tile(n-1)+tile(n-2)라고 점화식을 세울 수 있다.

#문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

#작성 코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

int N;
int S[20][20];
bool visit[20]={false,};
int minS=987654321;

void makeTeam(int n, int cnt){
	if( cnt == N/2 ){
		vector<int> start, link;
		 
		for(int i=0; i<N; i++){
			if( visit[i]==true )
				start.push_back(i);		// visit한 선수들은 start팀 
			else
				link.push_back(i);		// 다른 선수들은link팀. 
		}
		
		// 두 팀의 능력치 차이 구하기. 
		int teamStart=0, teamLink=0;
		for(int i=0; i<start.size(); i++){
			for(int j=i+1; j<start.size(); j++){
				int startX = start[i], startY = start[j];
				int linkX = link[i], linkY = link[j];
				teamStart+=S[startX][startY]+S[startY][startX];
				teamLink+=S[linkX][linkY]+S[linkY][linkX];
			}
		}
		minS = min(minS, abs(teamStart-teamLink));
		return;
	}
	
	// n번째 선수부터 탐색한다. 
	for(int i=n; i<N; i++){
		if(visit[i]==true) continue;
		visit[i] = true;
		makeTeam(i+1, cnt+1);
		// 선수 한명을 뽑고 그 선수를 뽑은 상황에서 재귀적을 다음 선수 찾기 
		// makeTeam(i+1, cnt+1)으로 호출할 경우 for문 내부의 if문 실행을 하나 줄일 수 있다. 
		visit[i] = false;
	}
}

int main(){
	scanf("%d", &N);
	
	// 입력 
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			scanf("%d", &S[i][j]);
		}
	}
	// 능력치합의 차 최소값 구하기
	makeTeam(0,0);
	printf("%d", minS);
	
	return 0;
}

##

주어지는 선수의 수는 최대 20명이므로,

능력치를 저장할 배열 S[20][20];

이 선수를 뽑았는지 체크하는 배열 visit[20] = {false, };

각 팀의 능력치 합 teamStart=0, teamLink=0;

능력치 합의 차 최솟값을 저장할 minSum = 987654321; 으로 초기화.

Start팀에 갈 선수 N/2명만 뽑으면 Link팀 선수들은 자동으로 나머지 선수들이 된다.

#작성 코드

#include <cstdio>

int T;	// 테스트 케이스의 개수 
int n;
long long int memo[41];
long long int fibo(int i){
	if( i==0 ){
		memo[i] = 0;
		return 0;	
	}
	if( i==1 ){
		memo[i] = 1;
		return 1;	
	} 
	
	if( memo[i]!=0 ) return memo[i];
	return memo[i]= fibo(i-1)+fibo(i-2);
}

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		if( n==0 )
			printf("1 0\n");		// fibo(0)에 대해서만 예외 출력 
		else
			printf("%d %d\n", fibo(n-1), fibo(n));
	} 
	return 0;
}

##

fibo(0) = 0

fibo(1) = 1

fibo(2) = fibo(1) + fibo(0) = 1

fibo(3) = fibo(2) + fibo(1) = 2*fibo(1) + fibo(0) = 2

fibo(4) = fibo(3) + fibo(2) = 3*fibo(1) + 2*fibo(0) = 3

...

fibo(n)을 호출했을 때 fibo(0)은 fibo(n-1)번 호출되고, fibo(1)은 fibo(n)번 호출됨을 알 수 있다.

#작성 코드

#include <cstdio>

int n;
long long int memo[91];
long long int fibo(int i){
	if( i==0 ) return 0;
	if( i==1 ) return 1;
	
	if( memo[i]!=0 ) return memo[i];
	return memo[i] = fibo(i-1)+fibo(i-2);
} 

int main(){
	scanf("%d", &n);
	printf("%lld", fibo(n));
		// 최대 90번째 피보나치수 출력할수있으므로 
		// 아주 큰 수 출력에 대비해야한다! 
	return 0;
}

##

최대 90번째 피보나치수를 출력해야하므로 출력값은 아주 큰 수가 된다. 따라서 계산한 값을 저장할 memo배열의 자료형과, 피보나치 수를 계산하는 함수의 리턴 자료형을 long long int로 해야했다.