Algorithm/DFS (45) 썸네일형 리스트형 (C++) - DFS 유형 DFS는 주로 재귀함수를 사용하며 백트래킹, 브루트 포스에 자주 이용하는 탐색 방법입니다. 고려할 점은 다음과 같은 3가지입니다. 1. 조합으로 뽑을 때 2. 같은 부분 집합을 출력하면 안될 때 3. 순열로 뽑을 때 순서 상관없이 막 뽑을 때 (C++) - 백준(BOJ) 15664번 : N과 M (10) 문제링크 : https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 출력은 무조건 오름차순, 중복 출력하지 않아야 합니다. 풀이방법 1. set으로 중복된 상태를 저장하지 않게 하는 방법 2. 해당 level의 수를 한 번 뽑았다면 뽑지 못하도록 만드는 2차원 배열을 사용하는 방법 Code 1. set으로 푼 코드 #include #include #include #include using namespace std; int n, m; int.. (C++) - 백준(BOJ) 15663번 : N과 M (9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net backtracking 문제였습니다. 풀이방법 1. set을 사용하는 방법 2. 사용하지 않고 level별로 체크하는 배열을 하나 더 두어 중복을 방지하는 방법 Code 1. set사용 #include #include #include #include using namespace std; int n, m; int a[8]; int ck[8]; int tmp[8]; set ans; //중복.. (C++) - 백준(BOJ) 15649번 : N과 M (1) 문제링크 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 백트래킹 문제였습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include using namespace std; int n, m; int a[10]; int ck[10]; void DFS(int t) { if (t == m) { for (int i =.. (C++) - 백준(BOJ) 2252번 : 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬 문제였습니다. 풀이방법 1. 단 방향그래프로 만듭니다. 2. dfs를 수행하면서 모두 호출한 후에는 stack에 정점을 push해줍니다. 3. 모든 원소를 stack pop하면서 출력합니다. Code indegree이용하는 법 #include #include #include using namespace std; int N,M,u,v,ins[320.. 이전 1 ··· 3 4 5 6 다음
