본문 바로가기

분류 전체보기107

[Brute Force] 백준 16197번 : 두 동전 - Python 파이썬 생각하기 시간 복잡도 총 10번까지만 버튼이 눌러지는 경우(4가지)를 고려하면 되는 것이기 때문에 4^10 = 2^20 = 1048576번 이므로 1억을 넘지 않으므로 모든 경우를 살펴보면 된다 충분하다 브루트 포스 문제인 것은 확실하고 방법을 생각해보자 처음 문제를 보고 DFS 문제라고 생각했다 한 쪽으로 가게 되면 10번이 넘을 때까지 가서 min_num을 업데이트 하거나 -1로 만드는 것으로 생각했다. 실제로 정직한? DFS 로 구현해 본 결과 결과값 출력까지 꽤 오랜 시간이 걸렸다. BFS로 생각하면서 주변 오/아/왼/위를 한번씩 검사를 하고 거기서 min_num인지 판단하고 return 시키면 좀 더 시간을 줄일 수 있었다. 방법1 import sys input = sys.stdin.readli.. 2021. 11. 1.
[Brute Force] 백준 14500번 - 테트로미노 - Python 파이썬 생각하기 처음에는 테트로미노를 하나씩 N*M 배열위에 배치해서 최대값을 구하는 방식을 생각했지만 아무리봐도 코드가 더러워지고 생각해야할 변수가 많았다 연속하는 인접하는 총4개의 네모 자세히 살펴보다가 아이디어가 하나 떠올랐다 모든 테르미노는 칸이 4개씩이고 변끼리 인접해야 하는 규칙이 있네? 도형기준으로 생각하지 말고 각각의 네모 하나 기준으로 관점을 바꾸어보았다. 이어져있다면 네모가 총 4개가 될때까지 계속 인접한 도형을 먹으면 되지 않을까 하는 생각이 들었다. 줄줄이 소세지처럼 옆의 네모를 타고 그 다음 네모를 타고 그 다음 네모를 타고... 4개까지만 타고 다시 되돌아가면 되는 것이다. 브루트포스 적용시 시간복잡도 브루트포스 문제로 모든 경우를 다 살펴봐도 시간 초과 문제가 안날것은 확인했다. 테트.. 2021. 10. 25.
[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.

티스토리툴바