N과M2 [백준] 15663. N과 M(9) N과 M문제 중에 이 문제만 정답률이 47%로 낮다. 낮은 이유가 있었다. 중복되는 것에 대해서 트릭이 필요했다. 두 가지 방법을 소개한다. 수열 인덱스를 골라 나갈 것인데 예를 들어 4개중 2개를 골라보자. 4 2 9 7 9 1 2번 예제이다. 0 1 0 2 0 3 1 0 1 2 1 3 2 0 2 1 2 3 3 0 3 1 3 2 이 될것이다. 우선 v에 입력을 순서대로 저장하면 1 7 9 9 가 될 것인데, 저 순서대로 출력한다면, 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 이렇게 될 것이다. 중복되는 수열이 많다. 이것을 제거하는 방법은 해당 depth에서 새로운 인덱스를 고르기전에(for문전에) 이전 값을 기억하는 변수를 만드는 것이다.(before) 따라.. 2019. 10. 19. [백준] 15649 N과 M (1) - 순열 단계별로 풀어보기에서 N과 M 시리즈 4개 중 개인적으로 가장 어렵다고 생각한다. 하지만, dfs와 백트래킹을 알고 있다면, N과 M문제 자체가 그렇게 어려운 편은 아니다. DFS는 그래프에서 깊이 우선 탐색을 의미하지만, 완전 탐색에서 주로 쓰이는 알고리즘으로, 모든 것을 다해보는 브루트포스 알고리즘과도 연관이 있다. 백트래킹은 여기에 조건을 더해주어, 원하는 경로로 탐색할 수 있게 도와주는 장치이다. 구현 코드 2개를 소개하고자 한다. #include using namespace std; int n, m; int a[8]; void swap_(int &a, int &b){ int temp = a; a = b; b = temp; } void rotateR(int start, int end){ int t.. 2019. 9. 19. 728x90 이전 1 다음
