본문 바로가기

알고리즘74

[Brute Force] 백준 16198 : 에너지 모으기 - Python 파이썬 생각하기 브루트 포스를 통해 모든 경우를 다 살펴보고 최댓값을 구할 수 있을 지 생각해보았다 양쪽 끝에 있는 요소들을 고르지 않고 사이에 있는 것들만 recursive 메소드를 통해서 골라간다 시간복잡도 N의 최대가 10이기 때문에 양쪽 끝의 요소들을 고려하지 않고 사이의 것들만 선택하면 8 x 7 x 6 ..... x 2 x 1 이 된다. 8! = 40320 에너지의 최대값을 .. 2021. 11. 1.
[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.

티스토리툴바