#문제 15663번: N과 M (9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #접근방법 N개의 자연수 중에서 M개를 고른 수열을 출력하면 된다. 단, 중복되는 수열을 여러 번 출력하면 안된다. 모든 경우의 수를 구하는 백트래킹 기법을 사용하면서 적절한 조건문을 추가하면 풀 수 있다. #풀이 #include #include using namespace std; int n,m; int arr[10]; int num[10]; int che..
#문제 11725번: 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 루트가 1인 트리에서 n-1개의 엣지가 주어질 때, 2 ~ n번 노드의 부모를 찾는 문제이다. 두 노드를 입력 받을 때, 두 노드가 서로 연결되어 있다는 표시를 하고 dfs(깊이 우선 탐색)으로 각 노드의 부모를 구해주면 된다. #풀이 #include #include using namespace std; vector v[100005]; int ans[100005]={1}; void dfs(int x){ for(..
#문제 11053번: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #접근방법 수열에서 가장 긴 증가하는 부분 수열을 구하려면 이중 반복문을 돌면서 동적계획법으로 풀면 된다. #풀이 #include int arr[1005]; int dp[1005]; int main(){ int n; int ans = 0; scanf("%d",&n); f..
#문제 15657번: N과 M (8) https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net #접근방법 n개의 자연수가 주어졌을 때 오름차순이며 같은 수를 여러 번 골라도 된다. 입력값으로 랜덤의 숫자가 주어지므로 sort함수로 오름차순 정렬을 한 뒤, 모든 수열을 출력하기 위해 백트래킹 기법을 사용하면 된다. #풀이 #include #include using namespace std; int n,m; int arr[10]; int num[1..
#문제 15654번: N과 M (5) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net #접근방법 n개의 자연수가 주어졌을 때 오름차순이며 중복되는 수열을 여러 번 출력하면 안된다. 입력값으로 랜덤의 숫자가 주어지므로 sort함수로 오름차순 정렬을 한 뒤 중복을 체크하기위해 check 배열을 만들고, 모든 수열을 출력하기 위해 백트래킹 기법을 사용하면 된다. #풀이 #include #include using namespace std; i..
#문제 15652번: N과 M (4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #접근방법 이 문제는 어제 푼 문제 15652번 : N과 M (2)와 매우 유사한 문제이다. 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열을 비내림차순이어야 한다. 위 조건을 만족하는 수열은 같은 수를 허용하는 오름차 순의 길이가 M인 수열이다. 재귀함수로 백트래킹기법을 사용하여 모..
#문제 15650번: N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #접근방법 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 위 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제이다. 재귀함수로 백트래킹기법을 사용하여 모든 조합을 구하면 된다. #풀이 #include int n,m; int arr[10]; void seq(int x,int len..
#문제 2407번: 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net #접근방법 조합을 구하는 식 (nCm = n-1Cm-1 + n-1Cm)을 이용하고, long long 범위를 벗어나는 조합값이 있으므로 string 자료형으로 큰 수 덧셈으로 조합값을 구하면 된다. #풀이 #include using namespace std; string arr[105][105]; string add(string num1, string num2){ string num = ""; int sum = 0; int size = max(num1.size(),num2.size());..
