본문 바로가기
728x90
반응형

전체 글77

[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.
728x90
반응형

티스토리툴바