목록파이썬 (92)

시작이 반

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

트리형태.. 이런형태의 리스트로 만들 수 있다. triangle[i][j] j i 0 1 2 3 4 0 7 1 3 8 2 8 1 0 3 2 7 4 4 4 4 5 2 6 5 dp[i][j] j i 0 1 2 3 4 0 triangle[i][j] 1 dp[i-1][ j ] + triangle[ i ][ j ] dp[i-1][ j ] + triangle[ i ][ j ] 2 dp[i-1][ j ] + triangle[ i ][ j ] MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ] dp[i-1][ j ] + triangle[ i ][ j ] 3 dp[i-1][ j ] + triangle[ i ][ j ] MAX(dp[i-1][j-1], dp[i-1][ j ]) +..
알고리즘/백준 2021. 2. 8. 01:25
[백준] 9461번(python 파이썬)

현재 선택한 색에 따라 나뉘어 지는 경우의 수가 2가지씩 존재한다. 마찬가지로 다음 상태는 이전상태에서 올 수 있는 경우의 수가 2가지 존재한다. 때문에 다음 상태는 이전 상태(2가지)중 작은 값을 찾아서 더해주면 된다. -> 2차원 배열로 dp를 만들어준다. 첫번째 행은 첫번째 집들의 비용을 넣으면 된다. import copy n = int(input()) cost = [list(map(int, input().split())) for _ in range(n)] dp = [[10001] * 3 for _ in range(n)] def RGB(): for i in range(n): for j in range(3): if i == 0: dp[i][j] = cost[i][j] else: if j == 0: d..
알고리즘/백준 2021. 2. 6. 23:26
[백준] 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
[백준] 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
이전 Prev 1 ··· 7 8 9 10 11 12 Next 다음