알고리즘/DFS6 [DFS] 백준 14888번 : 연산자 끼워넣기 - Python 파이썬 생각하기 수와 수 사이에 연산자가 있는 구성이다. 근데 연산자들이 한번 사용되면 소진되는 구성이다. 처음에 생각할때는 다익스트라 구현시, visited 배열을 만드는 것과 같이 이미 사용한 연산자를 체크하는 used배열을 선언하여 체크하려고 했다. 하지만 세번째 테스트케이스에서 결과가 나오지 않는 문제가 있어서 다시 생각하게 되었다. 또한 굉장히 코드가 복잡해지는 문제가 있었다. return 시에 다시 used 배열을 FALSE 처리하고 나와야하는 등 코드가 더러워지면 이것은 틀린 것이다! 라는 생각에 다시 생각하게되었다. 입력받은 연산자의 개수 리스트를 그대로 사용할 방법이 없는가 각 연산자의 개수는 정해져 있고 해당 연산자를 사용할 때마다 소진하는 DFS를 생각해보았다. 즉, 연산자에 해당하는 개수가.. 2021. 10. 22. [DFS] 재귀적 깊이 우선 탐색 메서드(함수)의 구성 - Python 파이썬 DFS 깊이 우선 탐색을 할 때, 늘 메서드를 구성하는데에 많은 시간을 들이는 것 같다 (아직 알고리즘 초보라는 소리다..) 백준 강의를 들으며 DFS 메서드 필수 구성 요소를 정리해보고자 한다 def DFS(매개변수): 1. 정답을 찾은 경우 2. 순환이 불가능한 경우 3. 순환이 가능한 경우 다음의 경우를 어떻게 호출할 것인지 브루트 포스 문제인 경우 모든 경우를 탐색하면 되기 때문에 3번 사항에 대해서 크게 고민하지 않아도 된다 다음으로 계속 revursive하게 탐색을 하고 모든 경우의 수만 찾으면 된다 그 외에 특정 조건의 탐색이 있는 경우 특정 경우에서 탐색의 경로를 바꾸어 주어야 하기 때문에 3번 사항에 대해 조건을 정해주어야 함 2021. 10. 18. [DFS] 프로그래머스 고득점킷 네트워크 - Python 파이썬 생각하기 연결되어 있는 노드들의 뭉치를 찾는 것이기 떄문에 깊이 우선 탐색을 솔루션 알고리즘으로 생각했다 한개의 노드를 찾으면 연결되어 있는 노드를 타고 다음 연결되어 있는 노드로 흘러가듯이 타고 내려가는 방법이다 구현하기 visited 배열을 통해 한번 방문한 노드는 다시 방문했을 때 더이상 로직을 진행할 필요가 없도록 한다 computers 배열의 모든 부분을 돌면서 visited를 검사하며 DFS 알고리즘을 실행한다 장애물 사항 computers 배열에서 row와 col이 같은 것은 결국 자기 자신이니까 for 문을 돌때 생략해도 된다고 생각했다. 하지만 생각하지 못한 예외가 있다 아무 노드랑 연결되지 않은 홀로 있는 노드다! 이런 경우 네트워크로 확인할 수 없기 때문에 row==col 인 것도 포.. 2021. 10. 11. [DFS] 프로그래머스 고득점킷 타켓넘버 - Python 파이썬 DFS 깊이 우선 탐색 주어진 numbers를 트리 형식으로 구성하여 탐색해나간다 트리에서 각 stage는 주어진 number의 순서 탐색해 나갈 때, 하나를 끝까지 파고들어서 더한 후에 target과 같은지 확인한다 -> 깊이 우선 탐색을 실시 numbers 리스트 아이템을 마이너스로 어떻게? numbers 리스트의 마이너스들을 저장하기 위한 minus 리스트를 따로 만들어서 관리한다. 기존 numbers에 있는 아이템들은 plus라는 리스트에 복사해 놓은 다음 numbers 리스트 요소들에 -1을 곱해주어서 minus 리스트에 넣어준다. 즉, plus 리스트와 minus 리스트의 인덱스는 서로 같은 numbers의 요소에서 나왔다고 할 수 있다. 처음 시작이 Plus가 될수 있고 Minus가 될수 있.. 2021. 9. 27. 이전 1 2 다음
