알고리즘/Brute Force7 [DFS] 백준 1182번 부분수열의 합 - Python 파이썬 생각하기 부분 수열을 만들 수 있는 모든 경우를 다 탐색해야 하는 브루트포스 문제이다. 모든 경우를 탐색하면서 S가 될 때를 판단해야 하므로 반복문을 통해 하나씩 하는 건 말이 안된다 DFS를 사용해서 내려가면서 S와 비교를 하면서 개수를 카운트해야겠다고 생각했다 부분수열은 순서는 신경쓰지 않으니 DFS의 전체적인 로직은 시작하는 숫자를 Data의 Idx에따라 계속 바꾸어 나가자는 것! 구현하기 answer 변수를 전역에 선언, 재귀적으로 DFS를 돌면서 answer을 쌓아갈 예정 sum은 매번 DFS를 새로 시작할 때, 시작 포인트에서 첫 숫자로 초기화해준다 각 DFS는 recursive 하게 돌면서 자신이 쌓은 answer을 반환 DFS 메서드 구성 sum이 S와 같은 경우 idx가 마지막 idx인경.. 2021. 10. 19. [Back Tracking] 백준 15649번 - N과 M(1) N과 M모두 8이하의 수이기 때문에 최대 8중 for문으로 돌아간다. 8^8 Brute Force로 풀 수 있는 문제이다 가변하는 여러 겹의 for를 어떻게 만들것인가? -> 재귀함수 사용한다 choose[] = 이미 선택된 것을 나타내는 배열 answer[] = 답을 순서대로 출력하기 위해서 저장해 놓는 배열 만약 세개를 다 선택했다면 loop를 나간다 나갈때, 답을 출력한다. loop를 나가고 나서 다시 2단계로 돌아올 때 끝난 과정의 3단계에서 choose된 것을 false로 바꾸어 준다 추후 다른 2단계에서 선택된 경우에서 써야 한다 (같은 단계에서는 어차피 for문이 다음으로 넘어가기 때문에 상관 없다) #include #include #inclu.. 2021. 1. 22. [Brute Force] 백준 1018번 - 체스판 다시 칠하기 시간 제한 : 2초 시간 제한이 2초 라는 것은 1초에 1억 (10^8)번 계산하는 것의 두배 이므로 2*10^8 이다 하나씩 완전 탐색을 한다고 가정했을 때 (M-8)*(N-8)*8*8 번 걸린다. M Black CASE 2) 왼쪽 상단이 White일 때 (가로index + 세로 index) 가 홀수인 경우 => Black (가로index + 세로 index) 가 짝수인 경우 => White vector로 이차원 배열 만들기 vector arr; vectorarr(M, vector(N,'N')); // 이차원 벡터 'N'으로 초기화 //이차원 벡터 탐색 방법 for(int i=0; i> N; min_num = 64; vector arr(M, vector(N, 'N')); for (int i = 0; i.. 2021. 1. 22. 이전 1 2 다음
