브루트포스6 [Back Tracking] 백준 9663번 : NQueen - Python 파이썬 생각하기 각 row에는 하나의 퀸만 있고 각 col에는 하나의 퀸만 있어야 한다 그리고 왼쪽 아래 대각선과 오른쪽 아래 대각선을 모두 고려해야 함 오른쪽 아래 대각선은 row idx - col idx + N -1 이 모두 같은 칸이고 왼쪽 아래 대각선은 col idx - row idx 이 모두 같은 칸이다 이를 고려하여 recursive를 돌리면 된다 처음에는 plus_mem 과 minus_mem을 리스트로 선언하여 append하였지만 이는 시간초과를 가져오는 결과를 보였다 import sys import copy input = sys.stdin.readline N = int(input()) cnt = 0 def search(row, col_mem, plus_mem, minus_mem): global c.. 2021. 11. 2. [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. [DFS] 백준 14888번 : 연산자 끼워넣기 - Python 파이썬 생각하기 수와 수 사이에 연산자가 있는 구성이다. 근데 연산자들이 한번 사용되면 소진되는 구성이다. 처음에 생각할때는 다익스트라 구현시, visited 배열을 만드는 것과 같이 이미 사용한 연산자를 체크하는 used배열을 선언하여 체크하려고 했다. 하지만 세번째 테스트케이스에서 결과가 나오지 않는 문제가 있어서 다시 생각하게 되었다. 또한 굉장히 코드가 복잡해지는 문제가 있었다. return 시에 다시 used 배열을 FALSE 처리하고 나와야하는 등 코드가 더러워지면 이것은 틀린 것이다! 라는 생각에 다시 생각하게되었다. 입력받은 연산자의 개수 리스트를 그대로 사용할 방법이 없는가 각 연산자의 개수는 정해져 있고 해당 연산자를 사용할 때마다 소진하는 DFS를 생각해보았다. 즉, 연산자에 해당하는 개수가.. 2021. 10. 22. 이전 1 2 다음
