본문 바로가기

알고리즘74

[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.
[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.

티스토리툴바