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

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 1001;

int N, M; // N: 정점의 개수, M: 간선의 개수
int adj[MAX][MAX] = { 0, }; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

void dfs(int node) {
	for(int i = 1; i <= N; i++)
		if(adj[node][i] == 1 && visited[i] == 0) {
			visited[i] = 1;
			dfs(i);
		}
}

int main(void) {
	cin>>N>>M;

	int x, y; // 인접 행렬 좌표
	for(int i = 0; i < M; i++) {
		cin>>x>>y;
		adj[x][y] = 1;
		adj[y][x] = 1;
	}

	int ans = 0;
	for(int i = 1; i <= N; i++)
		if(visited[i] == 0) {
			dfs(i);
			ans++;
		}

	cout<<ans;

}

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

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

DFS: 깊이 우선 탐색

•시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법

•가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용

BFS: 너비 우선 탐색

시작 정점으로 부터 인접한 정점들을 모두 한 번씩 차례로 방문한 후, 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 1001;

int N, M, V; // N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점
int adj[MAX][MAX] = { 0, }; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

void dfs(int node) {
	cout<<node<<' ';

	for(int i = 1; i <= N; i++)
		if(adj[node][i] == 1 && visited[i] == 0) {
			visited[i] = 1;
			dfs(i);
		}
}

void bfs(int node) {
	queue<int> q;
	q.push(node);
	visited[node] = 1;

	while(!q.empty()) {
		int v = q.front();
		cout<<v<<' ';
		q.pop();

		for(int i = 1; i <= N; i++)
			if(adj[v][i] == 1 && visited[i] == 0) {
				visited[i] = 1;
				q.push(i);
			}
	}
}

int main(void) {
	cin>>N>>M>>V;

	int x, y; // 인접 행렬 좌표
	for(int i = 0; i < M; i++) {
		cin>>x>>y;
		adj[x][y] = 1;
		adj[y][x] = 1;
	}

	visited[V] = 1;
	dfs(V);
	cout<<'\n';


	// 방문 노드 초기화
	for(int i = 0; i <= N; i++) visited[i] = 0;
	visited[V] = 1;
	bfs(V);
}

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

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

#include <iostream>
using namespace std;

int main(void){
	long long n, m;
	cin>>n>>m;

	long long ans5 = 0;
	long long ans2 = 0;
	
	// 5의 개수
	for(long long i = 5; i <= n; i *= 5) ans5 += n / i; // n!
	for(long long i = 5; i <= n - m; i *= 5) ans5 -= (n - m) / i; // (n - m)!
	for(long long i = 5; i <= m; i *= 5) ans5 -= m / i; // m!

	// 2의 개수
	for(long long i = 2; i <= n; i *= 2) ans2 += n / i; // n!
	for(long long i = 2; i <= n - m; i *= 2) ans2 -= (n - m) / i; // (n - m)!
	for(long long i = 2; i <= m; i *= 2) ans2 -= m / i; // m!

	cout<<(ans5 > ans2 ? ans2 : ans5);
}

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

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

#include <iostream>
using namespace std;

int main(void){
	int n;
	cin>>n;

	int ans = 0;

	// 5! = 120
	// 10! = 3,628,800
	// 15! = 1,307,674,368,000

	// 5가 나타날 때마다 0 하나 씩 증가
	for(int i = 1; i <= n; i++) {
		if(i % 5 == 0) ans++;
		if(i % 25 == 0) ans++;
		if(i % 125 == 0) ans++;
	}

	cout<<ans;
}

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

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

#include <iostream>
using namespace std;

int main(void){
	int n;
	cin>>n;

	int ans = 1;

	for(int i = n; i > 0; i--)
		ans *= i;

	cout<<ans;
}

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

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

#include <iostream>
using namespace std;

int main(void){
    int n;
    cin>>n; 

    for(int i = 2; i * i <= n ; i++){
        while(n % i == 0){
			cout<<i<<'\n';
            n /= i;
        }
    }

    if(n>1) cout<<n<<'\n';
}

에라토스테네스의 채를 사용해서도 풀이 가능

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

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

https://ko.wikipedia.org/wiki/%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

c++ 에라토스테네스

#include <iostream>
#include <math.h>
using namespace std;

const int MAX = 1000001;
int prime[MAX]; // 0: 소수,1: 소수x

// 에라토스테네스의 채 
void eratostenes(void){
	for(int i = 2; i * i < MAX; i++) {
		if(!prime[i]) // i가 소수일 경우
			for(int j = i * i; j < MAX; j += i) // i의 배수는 모두 소수가 아님 
				prime[j] = 1;
	}

	prime[1] = 1;
}

int main(void){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 

	int n;
	eratostenes();

	while(1){
		cin>>n;

		if(n == 0) break;

		for(int i = 3; i <= n / 2; i++) {
			if(prime[i] == 0 && prime[n - i] == 0){ 
				cout<<n<<" = "<<i<<" + "<<n - i<<'\n';
				break;
			} else if(i == n / 2)
				cout<<"Goldbach's conjecture is wrong.\n";
		}


	}
}

c++ cn

#include <iostream>
#include <math.h>
using namespace std;

bool cn(int n){
	int m = sqrt(double(n));

	if(n == 1) return false;

	for(int i = 2; i <= m; i++) {
		if(n % i == 0) return false;
	}

	return true;
}

int main(void){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
    
	int n;

	while(1){
		cin>>n;

		if(n == 0) break;

		for(int i = 3; i <= n / 2; i++) {
			if(cn(n - i) && cn(i)){ 
				cout<<n<<" = "<<i<<" + "<<n - i<<'\n';
				break;
			}
			else if(i == n / 2) cout<<"Goldbach's conjecture is wrong.\n";
		}

	}
}

python 에라토스테네스

def eratos(n):
  p=2
  while p*p<=n:
    if prime[p]==True:
      for j in range(p*p, n+1, p):
        prime[j]=False
    p=p+1

if __name__ == "__main__":
  prime=[True for _ in range(1000001)]
  eratos(1000000)

  while True:
    n=int(input())
    if n==0:
      break
    else:
      for i in range(2, n):
        if prime[i]==True and prime[n-i]==True:
          print("%d = %d + %d"%(n, i, n-i))
          break
      else:
        print("Goldbach's conjecture is wrong.")

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

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

2020/05/18 - [백준 알고리즘] - 백준 1978번: 소수 찾기

위의 문제와 동일하게 풀면 된다. 

#include <iostream>
#include <math.h>
using namespace std;

bool cn(int n){
	int m = sqrt(double(n));

	if(n == 1) return false;

	for(int i = 2; i <= m; i++) {
		if(n % i == 0) return false;
	}

	return true;
}

int main(void){
	int m, n; // m 이상, n 이하
	cin>>m>>n;

	for(int i = m; i <= n; i++)
		if(cn(i)) cout<<i<<'\n';
}