목록백준 (93)

시작이 반

[백준] 9461번(python 파이썬)

삼각형을 계속 이어나가면서 규칙을 찾는 문제이다. 내가 구한 점화식은 f(1) = 1 f(2) = 1 f(3) = 1 f(4) = f(3) + f(1) f(5) = f(4) f(6) = f(5) + f(1) f(7) = f(6) + f(2) f(8) = f(7) + f(3) f(5)부터 규칙을 찾을 수 있었다.. t = int(input()) def padovan(n): dp = [-1] * n for i in range(n): if i < 3: dp[i] = 1 elif i == 3: dp[i] = dp[i-1] + dp[i-2] else: if i-5 < 0: dp[i] = dp[i-1] else: dp[i] = dp[i-1] + dp[i-5] return dp[n-1] for _ in range(t..
알고리즘/백준 2021. 2. 6. 15:44
[백준] 20208번(python 파이썬)

금방 풀릴줄 알았지만 엄청 오래 걸렸다...(항상 이런듯) 처음에 집위치에서 상하좌우 모든 곳을 재귀를 돌려서 체력을 계산하면서 민트 초코가 있는곳 까지 가고 집에 도달하면 return 을 하는 식으로 하였지만 시간 초과가 떴다... 생각해보니 모든 경로를 탐색하기 때문에 갔던곳을 또간다. 이 사실을 알지만 처음 푼 방법에서 어떻게 고쳐야 할지 모르겠어서 다 지우고 처음부터 다시 풀기로 하였다. 첫풀이 n, hp, hp_puls = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] vistied = [[False] * n for _ in range(n)] dx = [-1, 1, 0, 0] dy = [0..
알고리즘/백준 2021. 2. 4. 20:16
[백준] 1759번(python 파이썬)

조합관련 문제이다. itertools의 combinations을 사용해도 되지만 백트래킹으로 풀었다. 사실 간단한 문제인데 문제를 제대로 읽지 않았다.. 처음에 대충 읽고 푼게 모음만 하나 이상이면 된다고 생각하여 풀었는데 오답이 나와서 다시 문제를 보니 자음도 최소 2개 이상 나와야 한다고 적혀있었다. 첫번째 잘못 이해.. 그리고 왠지 모르겠지만 모음이 연속으로 나오면 안된다고 적혀있지도 않는데 연속으로 나오지 않도록 풀었다... 두번째 잘못 이해.. 문제를 꼼꼼히 보자.. l, c = map(int, input().split()) cipher = list(input().split()) visited = [False] * c vowels = ['a', 'e', 'i', 'o', 'u'] cipher.s..
알고리즘/백준 2021. 2. 4. 14:34
[백준] 16968번(python 파이썬)

백트래킹 관련 문제여서 백트래킹으로 풀었는데 생각해보면 경우의 수를 구하는 문제라 백트래킹으로 풀지 않아도 된다 중복 형식일경우 경우의 수를 체크해주면된다.. ex) dd : 10*9 ddd: 10 * 9 * 10 cc : 26 * 25 ccc: 26 * 25 * 26 cdc : 26 * 10 * 26 이런식.... car_number = list(input()) result = 0 def BackTrack(depth, dup): global result if depth == len(car_number): result += 1 return if car_number[depth-1] != car_number[depth]: dup = -1 if car_number[depth] == 'c': temp = [Fa..
알고리즘/백준 2021. 2. 4. 00:07
[백준] 6603번(python 파이썬)

백트래킹의 쉬운 문제이다 숫자가 6개인 조합을 구해주면 된다. K와 S가 합쳐진 list를 입력받는데 이차원 list로 풀어도 되지만 동적 변수명 할당이라는 것을 봐서 이번에 이렇게 풀어봤다. 동적 변수명할당, 사용 i = 1 while True: globals()['lotto{}'.format(i)] = list(map(int, input().split())) if globals()['lotto{}'.format(i)][0] == 0: break globals()['visited{}'.format(i)] = [False] * (globals()['lotto{}'.format(i)][0] + 1) i += 1 lotto1, lotto2, ... visited1, visited2, ... lotto1 ->..
알고리즘/백준 2021. 2. 3. 16:21
[백준] 14889번(python 파이썬)

풀이 먼저 백트래킹을 이용하여 n/2 개의 수를 이루는 조합을 구한다. ex) n = 4 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 백트래킹을 이용하여 쉽게 구할수 있다. 구하는 도중 새로운 숫자가 들어오면 원래 있던 숫자와 S[i][j] + S[j][i]를 구한다. ex) (1) 에서 2가 들어옴 (1, 2) 이때 S[1][2] + S[2][1]를 구해주고 결과값을 매개변수로 넘겨줌 ex) (1, 2) 에서 3이 들어옴 (1, 2, 3) 이때 1,2에 대한 합은 구해줬으니 그 값과 S[1][3] + S[3][1], S[2][3] + S[3][2]을 반복문을 통해 더해줌... (말로 설명하는게 진짜 어려운거같다...) 이렇게 구하면 각 조합별로 구한값이 deque()에 들..
알고리즘/백준 2021. 2. 3. 00:48
[백준] 14888번(python 파이썬)

연산자에 대한 백트래킹 문제이다. 사실 푸는법은 바로 떠올라서 금방 풀었지만 정답이 제대로 나오지 않았다.. 몇시간 동안 디버깅을 한 결과 음수 // 양수 를 하면 정수로 변환되는데 이때 내림을 해서 변환하는거 같다.. -1//3 결과가 -1로 나왔음... -2//3 결과도 -1로 나옴 풀이 연자를 확인하면서 재귀를 실행한다. 중복해서 연산자가 있을경우 해당 연산자에 대해서 한번만 실행해도된다. 처음에 중복해서 실행하니까 실행 시간이 오래 걸렸다... 처음 풀이 n = int(input()) number = list(map(int, input().split())) operator = list(map(int, input().split())) result_max = -1e9 result_min = 1e9 d..
알고리즘/백준 2021. 2. 2. 18:53
[백준] 2580번(python 파이썬)

백트래킹으로 구현할 수 있는 문제이다. 우선 index 0 ~ 80 의 칸을 검사한다. 해당 칸이 빈칸일경우 해당 칸에 들어갈 수 있는 숫자를 구한다. def AbleNumber(n, m): ableNumber = [1, 2, 3, 4, 5, 6, 7, 8, 9] for i in range(9): if graph[n][i] in ableNumber: ableNumber.remove(graph[n][i]) for i in range(9): if graph[i][m] in ableNumber: ableNumber.remove(graph[i][m]) sub_n = n // 3 sub_m = m // 3 for i in range(sub_n * 3, sub_n * 3 + 3): for j in range(sub..
알고리즘/백준 2021. 1. 29. 01:37
이전 Prev 1 ··· 6 7 8 9 10 11 12 Next 다음