본문 바로가기

전체 글107

[DFS] 재귀적 깊이 우선 탐색 메서드(함수)의 구성 - Python 파이썬 DFS 깊이 우선 탐색을 할 때, 늘 메서드를 구성하는데에 많은 시간을 들이는 것 같다 (아직 알고리즘 초보라는 소리다..) 백준 강의를 들으며 DFS 메서드 필수 구성 요소를 정리해보고자 한다 def DFS(매개변수): 1. 정답을 찾은 경우 2. 순환이 불가능한 경우 3. 순환이 가능한 경우 다음의 경우를 어떻게 호출할 것인지 브루트 포스 문제인 경우 모든 경우를 탐색하면 되기 때문에 3번 사항에 대해서 크게 고민하지 않아도 된다 다음으로 계속 revursive하게 탐색을 하고 모든 경우의 수만 찾으면 된다 그 외에 특정 조건의 탐색이 있는 경우 특정 경우에서 탐색의 경로를 바꾸어 주어야 하기 때문에 3번 사항에 대해 조건을 정해주어야 함 2021. 10. 18.
[DP] 백준 6603번 로또 (Python) 생각하기 처음 이 문제를 보고서는 브루트포스 문제라고 생각하고 for문을 중첩하여 풀어야겠다고 생각했다 12345678 이면 678을 67, 68, 78 이렇게 for문으로 처리해야지! 하지만 For문으로 처리하려다 보니까 난리도 아니었다.. 너무 코드가 더러워졌다 더러워지면 질수록 이건 틀린거다..! 그래서 다시 뒤엎고 생각을 했다. 다시한번 잘 보니 이 문제는 DFS 문제였다 사실 어떻게보면 DFS도 모든 경우의 수를 들여다 보는 것이기 때문에 크게 보면 브루트포스에 속하긴한다 브루트포스라고 해서 다 for문 돌리는건 아니다! 구현하기 input으로 들어온 각 수를 돌면서 dfs를 하면 된다 depth : 총 여섯자리까지 구하면 되는 것이기 때문에 Dfs에서 깊이는 6까지만 찍고 올라오면 된다 out.. 2021. 10. 16.
[DP] 백준 20500번 - Ezreal 여눈부터 가네 - Python 파이썬 생각하기 처음에는 일차원 배열의 DP로 접근을 했었다. N=1,2,3일떄를 써놓고 규칙을 찾아보려해도 아무런 답이 나오지 않았다... 결국 검색을 통해 아이디어를 얻어낼 수 있었다... (아이디어만 봤다.. 아직 실력이 많이 부족.. ㅠ) 1과 5만 사용하기 때문에 기존 숫자에 맨 앞에 1혹은 5를 조합하는 방식이다 예를 들어 1의 자리라면 1, 5가 있을 텐데 앞에 11, 15, 51, 55가 되는 방식! 그렇게 되면 10과 50을 더해주는 것인데 15의 나머지는 10의 나머지 더하기 5의 나머지를 더한 15가 된다 -> 그래서 15는 15의 배수인것이다 (당연한 얘기지만 나머지 관점에서 봤을 떄 15잖아) 두수를 더할 때 두수의 나머지를 더한값과 더한 값의 나머지는 같다 -> 나머지 더한값이 15를 .. 2021. 10. 15.
[DFS] 프로그래머스 고득점킷 네트워크 - Python 파이썬 생각하기 연결되어 있는 노드들의 뭉치를 찾는 것이기 떄문에 깊이 우선 탐색을 솔루션 알고리즘으로 생각했다 한개의 노드를 찾으면 연결되어 있는 노드를 타고 다음 연결되어 있는 노드로 흘러가듯이 타고 내려가는 방법이다 구현하기 visited 배열을 통해 한번 방문한 노드는 다시 방문했을 때 더이상 로직을 진행할 필요가 없도록 한다 computers 배열의 모든 부분을 돌면서 visited를 검사하며 DFS 알고리즘을 실행한다 장애물 사항 computers 배열에서 row와 col이 같은 것은 결국 자기 자신이니까 for 문을 돌때 생략해도 된다고 생각했다. 하지만 생각하지 못한 예외가 있다 아무 노드랑 연결되지 않은 홀로 있는 노드다! 이런 경우 네트워크로 확인할 수 없기 때문에 row==col 인 것도 포.. 2021. 10. 11.

티스토리툴바