DFS3 [DFS] 백준 14888번 : 연산자 끼워넣기 - Python 파이썬 생각하기 수와 수 사이에 연산자가 있는 구성이다. 근데 연산자들이 한번 사용되면 소진되는 구성이다. 처음에 생각할때는 다익스트라 구현시, visited 배열을 만드는 것과 같이 이미 사용한 연산자를 체크하는 used배열을 선언하여 체크하려고 했다. 하지만 세번째 테스트케이스에서 결과가 나오지 않는 문제가 있어서 다시 생각하게 되었다. 또한 굉장히 코드가 복잡해지는 문제가 있었다. return 시에 다시 used 배열을 FALSE 처리하고 나와야하는 등 코드가 더러워지면 이것은 틀린 것이다! 라는 생각에 다시 생각하게되었다. 입력받은 연산자의 개수 리스트를 그대로 사용할 방법이 없는가 각 연산자의 개수는 정해져 있고 해당 연산자를 사용할 때마다 소진하는 DFS를 생각해보았다. 즉, 연산자에 해당하는 개수가.. 2021. 10. 22. [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. [DP] 백준 6603번 로또 (Python) 생각하기 처음 이 문제를 보고서는 브루트포스 문제라고 생각하고 for문을 중첩하여 풀어야겠다고 생각했다 12345678 이면 678을 67, 68, 78 이렇게 for문으로 처리해야지! 하지만 For문으로 처리하려다 보니까 난리도 아니었다.. 너무 코드가 더러워졌다 더러워지면 질수록 이건 틀린거다..! 그래서 다시 뒤엎고 생각을 했다. 다시한번 잘 보니 이 문제는 DFS 문제였다 사실 어떻게보면 DFS도 모든 경우의 수를 들여다 보는 것이기 때문에 크게 보면 브루트포스에 속하긴한다 브루트포스라고 해서 다 for문 돌리는건 아니다! 구현하기 input으로 들어온 각 수를 돌면서 dfs를 하면 된다 depth : 총 여섯자리까지 구하면 되는 것이기 때문에 Dfs에서 깊이는 6까지만 찍고 올라오면 된다 out.. 2021. 10. 16. 이전 1 다음
