알고리즘/Brute Force7 [Brute Force] 백준 2529번 : 부등호 - 파이썬 Python 생각하기 최대와 최소를 구하면 되므로 최대와 최소를 나누어서 brute force 하기로 생각한다 최대인 경우 앞자리가 제일 높은 수 (9) 부터 내려오면서 모든 경우를 대입한다 최소인 경우 앞자리가 제일 낮은 수 (0) 부터 올라가면서 모든 경우를 대입힌다. recursive한 메소드를 사용하여 각각의 경우에 대해 검증한다. 최대 구하는 경우 flag가 False 인 경우 return step이 k+2인 경우 flag를 False로 세팅하고 출력 그리고 return 최대 수부터 아래로 부등호에 맞게 숫자를 넣어가면서 recursion 최소 구하는 경우 flag가 False 인 경우 return step이 k+2인 경우 flag를 False로 세팅하고 출력 그리고 return 최소 수부터 위로 부등호에 .. 2021. 11. 9. [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. 이전 1 2 다음
