BOJ
BOJ 15656 · N과 M (7)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 중복 가능하게 M개를 뽑는 문제다. N과 M (3) 문제의 소스코드를 조금 수정하면 된다. C++ 소스코드 #include #include #include using namespace std; int n, m; int a[8]; vector v; void solve(int cnt) { if (cnt == m) { for (auto k : v) printf("%d ", k); printf("\n"); return; } for (int i=0; i
BOJ 15655 · N과 M (6)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 오름차순으로 뽑는 문제다. N과 M (2) 문제의 소스코드를 수정하면 된다. C++ 소스코드 #include #include #include using namespace std; int n, m; int a[8]; vector v; void solve(int index, int cnt) { if (cnt == m) { for (auto k : v) printf("%d ", k); printf("\n"); return; } for (int i=index; i
BOJ 15654 · N과 M (5)
알고리즘 분류 : 브루트 포스 N개의 숫자를 입력받고, 그 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (1)의 소스코드를 살짝 수정하면 된다. N과 M (1)에서는 1~N까지의 숫자를 사용했으니, 이번에는 배열에 있는 N개의 숫자를 사용하면 된다. C++ 소스코드 #include #include #include using namespace std; int n, m; int a[8]; bool check[8]; vector v; void solve(int cnt) { if (cnt == m) { for (auto k : v) printf("%d ", k); printf("\n"); return; } for (int i=0; i
BOJ 15652 · N과 M (4)
알고리즘 분류 : 브루트 포스 N개의 숫자 중에서 M개를 뽑는 문제다. 단, 같은 수를 여러 번 뽑아도 되며, 고른 숫자는 비내림차순이어야 한다. N과 M (2) 문제의 코드에서 시작 지점을 수정하면 된다. 시작 지점은 이전에 뽑은 숫자이다. 재귀 함수 호출에 전달할 값을 사용한 숫자와 똑같이 보내면 된다. C++ 소스코드 #include #include using namespace std; int n, m, x; vector a; void solve(int index, int cnt) { if (cnt == m) { for (auto i : a) printf("%d ", i+1); printf("\n"); return; } for (int i=index; i
BOJ 15651 · N과 M (3)
알고리즘 분류 : 브루트 포스 N개의 숫자 중에서 M개를 뽑는 문제다. 숫자를 뽑을 때 같은 수를 여러번 골라도 된다. 이 문제는 N과 M (1) 문제의 소스코드에서 check 배열만 사용하지 않으면 된다. C++ 소스코드 #include #include using namespace std; int n, m, x; vector a; void solve(int cnt) { if (cnt == m) { for (auto i : a) printf("%d ", i+1); printf("\n"); return; } for (int i=0; i
BOJ 15650 · N과 M (2)
알고리즘 분류 : 브루트 포스 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. 단, 중복된 수열이 없어야 하고, 오름차 순으로 출력해야 한다. N과 M (1)의 코드에서 for문의 시작 지점을 수정하면 된다. 시작 지점은 이전에 뽑은 숫자+1 이다. 숫자+1을 다음 재귀 함수 호출에 전달하면 된다. C++ 소스코드 #include #include using namespace std; int n, m, x; vector a; void solve(int index, int cnt) { if (cnt == m) { for (auto i : a) printf("%d ", i+1); printf("\n"); return; } for (int i=index; i
BOJ 15649 · N과 M (1)
알고리즘 분류 : 브루트 포스 N개의 숫자 중에서, M개만 뽑아서 출력하는 문제다. 재귀 함수를 이용하여 구현할 수 있다. 사용 여부를 확인할 배열 check를 N 사이즈로 만들어둔다.1부터 N까지 재귀 함수를 호출한다. 숫자 X를 사용했으면, check[X]를 true로 한다.check가 true라면 재귀 함수를 호출하지 않고 넘어간다.사용한 숫자를 리스트에 담아두고, 리스트의 길이가 M이 되면 리스트를 출력한다. C++ 소스코드 #include #include using namespace std; int n, m; bool check[8]; vector a; void solve(int cnt) { if (cnt == m) { for (auto i : a) printf("%d ", i+1); print..
BOJ 16234 · 인구 이동
알고리즘 분류 : DFS 인접한 국가 간의 연합을 통해 인구 이동을 하는 문제다. 연합은 인접한 두 국가 간의 인구 차이가 L 이상, R 이하일 때만 가능하다. 인구 차이가 이 범위를 벗어난다면 연합을 할 수 없고, 인구 이동을 할 수 없다. 이 문제는 그래프에서 연결 요소 개수를 찾는 문제와 비슷하다. DFS를 통해 연합 가능한 국가가 몇 개인지 찾는다. (1, 1)부터 (N, N)까지 전체 국가를 탐색하면서 방문하지 않은 국가라면 DFS를 호출한다.DFS 탐색을 진행하면서 연합 가능한 국가가 있다면, 연합 국가 개수를 카운트하고, 인구 수의 합을 저장한다.또한 DFS 탐색을 하면서 별도로 연합 국가의 경로를 기록해둔다. 아래 소스코드에서는 moving 이라는 이름의 배열을 사용했다.한 번의 DFS 탐..