알고리즘매일매일

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

N의 범위가 (1 ≤ N ≤ 8) 이므로 다음 순열을 구해서 모든 순열을 구할 수 있다.

java에서는 next permutaion함수를 직접 구현해줬어야 했는데

c++은 라이브러리가 있어서 좋다...ㅠㅠ

그냥 next_permutation을 써주면 된다...!!

next_permutation을 사용할 때는 do while로 사용해줘야 한다. 무조건 한 번은 실행되어야 하기 때문.

그리고 넥퍼뮤 돌릴 자료구조는 벡터를 사용한다.

넥퍼뮤 while문이 돌아갈 때마다 현재 배열을 순차적으로 출력해주면 끝!

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

DP로 푸는 문제이긴 하지만 n이 11보다 작은 양수이기 때문에 완전 탐색으로도 풀어줄 수 있다.

방법의 수를 구하는 문제이므로, 1, 2, 3을 더한 경우를 모두 구해서 더한 값이 n이 될 때마다 ans 값을 증가시키고 return

n값을 넘어가버려도 return 해준다.

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

문제에서 n의 범위는 (6 ≤ n ≤ 1000000)이다.

골드바흐의 추측은 10의 18 제곱까지는 증명되었다고 하므로

두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에 "Goldbach's conjecture is wrong."을 출력하라고 문제에 나와있지만

안 해줘도 될 것 같다.

소수는 에라토스테네스의 체를 이용해서 n의 범위만큼 미리 구해서 배열에 저장한다.

n이 두 소수 p와 q로 이루어져 있다고 했을 때,

p + q = n

n - p = q

이므로 n에서 소수를 뺀 값이 소수이면 답을 바로 출력한다.

참고로 c++에서

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

를 써주면 입출력 속도를 높일 수 있다고 한다.

대신에 printf, scnaf 등은 사용하면 안 된다.

#include <iostream>
using namespace std;
const int MAX = 1000000;
int prime[MAX];
int cnt;
bool check[MAX+1];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //소수를 구해준다.
    for(int i=2; i*i<=MAX; i++) {
    	//이미 소수가 아닌걸로 체크되어 있는 경우
        if(check[i] == true) continue;

		//위의 조건에 걸리지 않았다면 소수이므로 소수 배열에 추가
        prime[cnt++] = i;
        
        //현재 소수의 배수들은 소수가 아니므로 체크해준다.
        for(int j=i+i; j<=MAX; j+=i) {
            check[j] = true;
        }

    }

    while(true) {
        int n;
        cin >> n;
        if(n == 0) break;
        for(int i=1; i<cnt; i++) {
            if(check[n-prime[i]] == false) {
                cout << n << " = " << prime[i] << " + " << n-prime[i] <<  "\n";
                break;

            }
        }
    }

    return 0;
}

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

최대공약수는 유클리드 호제법을 사용한 gcd 함수를 사용한다.

gcd 함수는 아래 코드와 같이 구현하면 된다.

최소공배수는 a와 b를 곱한 값에 최대공약수로 나누어주면 구할 수 있다.

#include &ltiostream&gt
using namespace std;

//최대공약수를 구하는 함수
int gcd(int a, int b) {
    if(b== 0) return a;
    else return gcd(b, a%b);
}

int main() {
    int a, b;
    cin >> a >> b;
    
    int g = gcd(a,b);
    cout << g << '\n' << a*b/g << '\n';
    
    return 0;
}

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

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다.

고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구한다

-> BFS로 풀면 되겠다.

->BFS로 물이 차는 시간을 먼저 구해서 배열에 저장하고 고슴도치를 이동해야겠다.

풀이

1. 입력을 받으면서 고슴도치, 비버의 좌표를 저장하고 물인 경우에는 바로 큐에 넣어준다.
2. 물이 차는 시간을 먼저 구해서 BFS를 먼저 실행한다.
3. 그 다음 고슴도치의 이동 시간을 계산해주기 위해 고슴도치의 위치를 큐에 넣어주고 BFS를 실행한다.
4. 고슴도치의 이동시간과 물이 차는 시간을 비교해가며 이동한다.

import java.util.*;

public class Main {
	static class Pair {
		int x;
		int y;
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int dx[] = {1, -1, 0, 0};
	static int dy[] = {0, 0, 1, -1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int c = sc.nextInt();
		char map[][] = new char[r][c];
		int waterTime[][] = new int[r][c];
		int hedgehogTime[][] = new int[r][c];
		int destX=0;
		int destY=0;
		int sX=0;
		int sY=0;
		Queue<Pair> q = new LinkedList<Pair>();
		sc.nextLine();
		
        //초기화
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				waterTime[i][j] = -1;
				hedgehogTime[i][j] = -1;
			}
		}
		
		for(int i=0; i<r; i++) {
			String s = sc.nextLine();
			for(int j=0; j<c; j++) {
				map[i][j] = s.charAt(j);
				if(map[i][j] == 'S') {
					sX = i;
					sY = j;
				}
				else if(map[i][j] == '*') {
					q.offer(new Pair(i,j));
					waterTime[i][j] = 0;
				}
				else if(map[i][j] == 'D') {
					destX = i;
					destY = j;
				}
			}
		}
		
        //물이 차는 시간을 먼저 구해준다.
		while(!q.isEmpty()) {
			Pair p = q.remove();
			int x = p.x;
			int y = p.y;
			for(int k=0; k<4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if(nx < 0 || ny <0 || nx >= r || ny >= c) continue;
				if(map[nx][ny] == 'D') continue; //물은 비버굴로 못간다.
				if(map[nx][ny] != 'X' && waterTime[nx][ny] == -1) {
					q.offer(new Pair(nx, ny));
					waterTime[nx][ny] = waterTime[x][y] + 1;
				}
			}
		}
	
    	//고슴도치 이동 시간 구해준다.
		q.offer(new Pair(sX, sY));
		hedgehogTime[sX][sY] = 0;
		while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
                    continue;
                }
                if (hedgehogTime[nx][ny] != -1) continue;
                if (map[nx][ny] == 'X') continue; //돌 있는 곳 못감
                
                //다음 이동할 곳의 물이 차는 시간이 고슴도치의 이동시간이 같거나 작으면 가지 못한다.
                //물이 차지 않은 곳인 경우(-1) 가 아님.
                if (waterTime[nx][ny] != -1 && hedgehogTime[x][y]+1 >= waterTime[nx][ny]) continue;
                
                hedgehogTime[nx][ny] = hedgehogTime[x][y] + 1;
                q.offer(new Pair(nx, ny));
            }
        }
		
		if(hedgehogTime[destX][destY] != -1)
			System.out.println(hedgehogTime[destX][destY]);
		else
			System.out.println("KAKTUS");
	}
}

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

 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 

라고 나와있지만 정확한 좌표가 중요한 것은 아니라서 그냥 신경안쓰고 풀었다.

풀이

1. 사각형의 좌표를 입력받아서 사각형을 칠해준다.(1로 채운다)
2. 직사각형 내부를 제외한 나머지 부분을 구해야 하므로 값이 0인 곳에 대해서 DFS를 실행했다.
3. 연결요소를 구분하기 위해 연결된 부분들에 번호를 붙여준다.
4. 각 번호가 붙여진 곳들의 개수를 세서 cnt 배열에 넣어준후 출력.

import java.util.*;

public class Main {
	static int dx[] = {0, 0, 1, -1};
	static int dy[] = {1, -1, 0, 0};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		int ans[][] = new int[n][m];
		int arr[][] = new int[n][m];
        
		for(int i=0; i<k; i++) {
			int lx = sc.nextInt();
			int ly = sc.nextInt();
			int rx = sc.nextInt();
			int ry = sc.nextInt();
			for(int j=lx; j<rx; j++) { //사각형 채우기
				for(int l=ly; l<ry; l++) {
					arr[l][j] = 1;
				}
			}
		}
        
		int count=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(arr[i][j] == 0 && ans[i][j] == 0){
					dfs(i,j,arr, ans, ++count, n, m); //dfs가 실행될때마다 count값 증가
				}
			}
		}	
		
		System.out.println(count);
		int cnt[] = new int[count];
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(ans[i][j] != 0) {
					cnt[ans[i][j]-1] +=1;
				}
			}
		}
        
		Arrays.sort(cnt);
		for(int i=0; i<count; i++) {
			System.out.print(cnt[i]+" ");
		}
	}
    
	static void dfs(int i, int j, int[][] arr, int[][] ans, int count, int n, int m) {
		ans[i][j] = count; //번호 붙여준다
		for(int k=0; k<4; k++) {
			int x = i+dx[k];
			int y = j+dy[k];
			if(x >=0 && y>=0 && x < n && y < m) {
				if(arr[x][y] == 0 && ans[x][y] == 0) {
					dfs(x, y, arr, ans, count, n, m);
				}
			}
		}
	}
}

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

풀이

1. 1번 컴퓨터에 연결된 컴퓨터들을 구하면 되는 연결 요소 문제이다. BFS로 풀어주면 될 것 같다.
2. 먼저 컴퓨터들의 연결 정보를 인접리스트로 구현해준다.
3. 1번 컴퓨터를 먼저 큐에 넣고 1번 컴퓨터와 연결된 컴퓨터들을 모두 방문 체크한다.
4. 방문한 컴퓨터(감염된 컴퓨터) 수를 출력 (1번 컴퓨터 제외).

import java.util.*;

public class Main {
	
	static ArrayList&ltInteger>[] list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int connect = sc.nextInt();
		list = (ArrayList[]) new ArrayList[n];
		for(int i=0; i < n; i++) {
			list[i] =  new ArrayList();
		}	
		for(int i=0; i < connect; i++) {
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			list[u].add(v);
			list[v].add(u);
		}
		boolean[] check = new boolean[n];
		Queue q = new LinkedList();
		q.add(0);
		check[0] = true;
		while(!q.isEmpty()) {
			int u = q.remove();
			for(int i=0; i < list[u].size(); i++) {
				int v = list[u].get(i);
				if(check[v]) continue;
				q.add(v);
				check[v] = true;
			}
		}
		int ans = -1;
		for(int i=0; i < n; i++) {
			if(check[i]) ans++;
		}		
		System.out.println(ans);
	}

}

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

DFS나 BFS를 사용해서 연결 요소를 구하는 문제이다.

1. 땅이고 아직 방문하지 않은 곳을 DFS를 통해서 모두 방문해줬다.
2. 새로 DFS를 실핼해줄때마다 count값을 증가시킨다.

import java.util.*;

public class Main {
	static int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int w = sc.nextInt();
			int h = sc.nextInt();
            
			if(w ==0 && h ==0) //종료 조건
				break;
			
            int count = 0;
			int square[][] = new int[h][w];
			boolean check[][] = new boolean[h][w];
            
			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {
					square[i][j] = sc.nextInt();
				}
			}
            
			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {
					if(square[i][j] == 1 && check[i][j] == false){ //땅인데 아직 방문하지 않았다.
						dfs(i, j, square, check, h, w);	
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}
	static void dfs(int i, int j, int[][] square, boolean[][] check, int h, int w) {
		check[i][j] = true; //방문 체크
		for(int k=0; k<8; k++) {
			int x = i+dx[k];
			int y = j+dy[k];
			if(x >= 0 && y >= 0 && x &lt h && y &lt w)
				if(square[x][y] == 1 && check[x][y] == false) //땅인데 방문하지 않은 곳 방문
					dfs(x, y, square, check, h, w);
		}
	}

}