728x90 반응형 algorithm56 [algorithm] 백준 - N과 M(10) 이 문제는 dfs이다. 이 문제는 N과 M(6)과 N과 M(9)와 연관된 문제이다. 중복되는 수열을 여러번 출력하면 안되며, 수열은 중복된 수로 나열되어있을 수 있다. 포인트는 'N과 M(6) + 재귀 시 중복된 수가 있는지 확인' 이다. N과 M(6)은 조합문제이다. 조합 코드는 두 가지가 있는데, void combination(int target, int index, vector realVector, vector numVector){ if(target == 0){ sort(numVector.begin(), numVector.end()); combinationVector.push_back(numVector); return; } if(index == realVector.size()){ return; } .. 2020. 10. 30. [algorithm] 백준 - N과 M(9) 이 문제는 dfs이다. 중복되는 수열을 여러번 출력하면 안되며, 수열은 중복된 수로 나열되어있을 수 있다. 이 문제는 N과 M(5)와 연관된 문제이다. 포인트는 'N과 M(5) + 재귀 시 중복된 수가 있는지 확인' 이다. N과 M(5) 문제 또한 dfs인데, 순열과 조합이 섞인 문제이다. 즉, N개로 이루어진 자연수 중에서 M개를 고르고 나열하는 문제이다. //백준 N과 M (5) #include #include #include using namespace std; bool selected[9] = {false}; void permutationAndCombination(int target, int index, vector realNumVector, vector numVector){ if(target =.. 2020. 10. 30. [algorithm] 백준 - ABCDE 친구 관계가 4 depth로 이루어져있을 경우 1을, 없을 경우 0을 출력한다. dfs로 4 depth까지 탐색이 완료되면 더이상 탐색을 하지 않는다. 반복문을 통해 정점을 탐색하는데 정점을 탐색할 때 어디서 depth가 4가 나올지 모르기 때문에 방문 기록을 탐색 후 초기화한다. #include #include using namespace std; vector friendVector[2000]; int visited[2000]; int n; bool isFour = false; void initVisited(){ for(int i = 0; i n >> count; for(int i = 0; i > a >> b; friendVector[a].push_.. 2020. 10. 29. [algorithm] 백준 - N과 M (8) 중복 조합으로 풀어야한다! 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것, 중복이 허용된다. 조합과 차이점 중복을 허용하므로 값을 추가했을 때 index에 1을 더하지 않는다. #include #include #include using namespace std; void overlapCombination(int target, int index, vector realVector, vector numVector){ if(target == 0){ for(int i = 0; i target; vector realVector, numVector; for(int i = 0; i > num; realV.. 2020. 10. 29. [algorithm] 백준- N과 M(7) 중복 순열로 풀어야 한다. 서로 다른 n개의 원소에서 r개를 뽑아 한줄로 세우는 경우의 수, 중복도 허용되어 같은 원소를 r개 뽑을 수 있다. 순열과 차이점 중복을 허용하므로 반복문을 도는데 초깃값을 0으로 설정한다. 재귀함수이고, 반복문을 돌며 vector에 값을 추가한다. 값을 반환 후 vector에서 원소를 삭제한다. 순열은 반복문을 돌며 swap하는 특징이 있다. #include #include #include using namespace std; void overlapPermutation(int index, vector numVector, vector realVector, int target){ if(target == index){ for(int i = 0 ; i < numVector.size(.. 2020. 10. 29. [algorithm] 백준 - 모든 순열 nPr 서로 다른 n개의 원소에서 r개를 뽑아 한줄로 세우는 경우의 수 순서가 부여된 집합을 다른 순서로 뒤섞는 연산이다. #include #include #include using namespace std; vector numVector; vector permutationVector; void swap(int a, int b){ int temp = numVector[a]; numVector[a] = numVector[b]; numVector[b] = temp; } void permutation(int size, int index){ if(index == size - 1){ permutationVector.push_back(numVector); } else{ for(int i = index; i < si.. 2020. 10. 29. 이전 1 ··· 5 6 7 8 9 10 다음 728x90 반응형
