전체 글(219)
-
14888번 - 연산자 끼워넣기*
DFS 예시 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I'] {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'G', 'H', 'I'], 'D': ['B', 'E', 'F'], 'E': ['D'], 'F': ['D'], 'G': ['C'], 'H': ['C'], 'I': ['C', 'J'..
2022.04.08 -
Dynamic Programming(DP) - 정수 삼각형[1932]
Idea 제일 위에서 부터 아래로 범위를 넓히면서 모든 경우의 덧셈을 더하고 최종 말단에 왔을때 최댓값을 구하면 된다. 이때, 인덱스 1부터 idx-1 까지는 더할 수 있는 수의 후보가 이전의 idx번째 수와 idx-1번째 수 총 2개가 있다. 따라서 최댓값을 구하는 문제이므로 큰 값만 뽑아서 현재 idx번째 수에 더해주면 된다. N = int(input()) fibo = [] for i in range(N): nList = list(map(int, input().split())) fibo.append(nList) for fidx in range(1, N): for idx in range(len(fibo[fidx])): if idx == 0: fibo[fidx][idx] += fibo[fidx-1][0]..
2022.04.07 -
Dynamic Programming(DP) - RGB거리[1149]
초기 실패 소스코드 import copy N = int(input()) nRGB = [] for i in range(N): RGB = list(map(int, input().split())) nRGB.append(RGB) result = [] for i in range(3): temp = [] idx = i copyRGB = copy.deepcopy(nRGB) sumResult = copyRGB[0][i] for RGB in copyRGB[1:]: RGB[idx] = 1000 temp.append(min(RGB)) sumResult += min(RGB) idx = RGB.index(min(RGB)) result.append(sumResult) print(min(result)) 앞의 색과 겹치지 않는 나머..
2022.04.06 -
Dynamic Programming(DP) - 2×n 타일링[11726]
n = int(input()) dp = [0, 1, 2] if n >= 3: for i in range(3,n+1): next = dp[i-1] + dp[i-2] dp.append(next) print(dp[n] % 10007) 이번 문제의 규칙을 찾다보면 피보나치 수열을 따른다는 것을 알 수 있다. 이것만 찾으면 큰 무리 없이 구할 수 있는 문제다. n = 2 n = 3 n = 4 n = 5 n = 6
2022.04.05 -
Dynamic Programming(DP) - 1, 2, 3 더하기[9096]
m = int(input()) result = [] for _ in range(m): n = int(input()) dp = [0, 1, 2, 4] if n >= 4: for i in range(4, n+1): nextDP = dp[i-1] + dp[i-2] + dp[i-3] dp.append(nextDP) result.append(dp[n]) for i in result: print(i) Idea 규칙을 찾는 것이 Point 1, 2, 3 만으로 연산을 하여 해당 숫자를 만들 수 있는 경우의 수를 구해야했기 때문에 아래처럼 규칙이 나타났다. A(n) = A(n-1) + A(n-2) + A(n-3) A(1) A(2) A(3) A(4) A(5) A(6) 1 1+1 1+1+1 (A(2)+ 1) 1+1+1+1..
2022.04.04 -
Dynamic Programming(DP) - 1로 만들기[1463]
조건 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. Idea DP (Bottom-Up 방식) : 결과 저장용 리스트인 DP 테이블을 통해 1부터 N까지 순차적으로 1을 만들기 위한 최소 연산 횟수를 저장 # 여기서 만든 로직은 제일 작은 수인 1부터 순차적으로 최소 연산 횟수로 1을 만드는 방법을 저장하면서 N까지 도달하는 것 N = int(input()) dp = [0] * (N+1) # 1은 아무런 연산을 하지 않아도 되므로, 2부터 시작 for i in range(2, N+1): # +1 = 일단 -1 연산을 했을때의 경우를 카운팅한 것 dp[i] = dp[i-1]+1 # -1 연산을 한 경우와 3 으로 나누는 경우 중에서 횟수가 더 적은 것을..
2022.04.03