본문 바로가기

백준28

[Back Tracking] 백준 2580번 : 스도쿠 파이썬 생각하기 0인 칸에 대해서 이 칸에 스도쿠 룰에 맞는 숫자를 넣고 다음 0인 칸에 대해서 룰에 맞는 숫자를 넣는 식으로 생각을 했다. 조건이 안맞으면 바로 이전으로 가서 다시 한번 숫자를 넣어보는 식으로 생각을 했다 prunning 조건 검사 해당 0이 있는 row에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 해당 0이 있는 col에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 0이 속한 아홉개의 섹션 안에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 위의 세가지 조건을 0자리에 들어갈 1 ~ 9까지에 대해서 검사를 하고 맞으면 recursive하게 다음으로, 틀리면 backtracking을 진행한다 9*9를 검사하지 않고 0인 것들만 보기 입력을 받을 때, 0인 칸의 row idx와 col.. 2021. 11. 6.
[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.

티스토리툴바