본문 바로가기

전체 글107

[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.
[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.
[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.

티스토리툴바