Home

개요 인터넷에 유사한 풀이가 없어 해당 문제의 솔루션을 공유합니다. 체크리스트 DP 문제 유형임을 알고 접근했는가? DP 3차원 자료구조로 풀이를 작성했는가? 접근 방법 DP[i][j][k] 는 i행, j열에 왔을 때, 마지막으로 k 방향(0, 1, 2)으로 움직여 도착한 모든 경우의 수 중 최소 비용입니다. 예를 들어 DP[i][j][0] 은 DP[i-1][j+1][1] 과 DP[i-1][j+1][2] 중 더 작은 값과 현재 위치의 비용을 더한 값이 됩니다. (i-1행 j+1열에서 왼쪽으로 이동하여 i행 j열로 도착했기 때문) 솔루션을 간단하게 작성하기 위해 벡터의 크기를 +2 하여 2e9 (int 자료형에 담을 수 있는 정수 중 최댓값 근사값) 을 저장했습니다. 솔루션 #include #include..

개요 대부분 풀이는 모두 DP 1차원 배열을 활용했습니다. 이 문제는 DP 2차원 배열을 통해서도 풀 수 있습니다. 로직 DP 테이블의 각 값은 i번까지의 카드를 조합해서 만들 수 있는 j개 카드 값들 중 최댓값 DP 테이블의 값을 채우는 과정에서 기존 최댓값에서 현재 카드를 추가할 수 있는 경우, 현재 카드를 추가한 경우와 기존 최댓값 사이의 대소 비교를 통해 최댓값이 결정됨을 확인할 수 있음 소스 코드 #include #include using namespace std; int DP[1001][1001]; int P[1001]; int main() { int N; cin >> N; for (int i = 1; i > P[i]; } /* 1 5 6 7 i j 1 2 3 4 개의 카드로 pn까지 활용해서..

요약 처음에 2차원 배열로 풀이를 작성하였지만 시간초과였습니다. 1차원 배열의 Bottom-UP 방식의 배열을 1회 순회하는 코드를 작성하여 문제를 해결하였습니다. 이전 단계에서의 최솟값을 어떠한 값을 기준으로 해야 하는 지 아는 것이 문제의 핵심으로 보입니다. 제가 이전에 풀었던 설탕 배달 문제와 유형이 동일합니다. 솔루션 python3 으로 솔루션을 작성하였습니다. def getMin(n): ''' e.g n==10일때 0 1 2 3 4 5 6 7 8 9 10 0 0 1 2 3 ''' dp = [0 for _ in range(n+1)] dp[1] = 0 for index, value in enumerate(dp): if index == 0 or index == n: continue if index+1

요약 DP bottom-up 방식으로 문제를 풀면 됩니다. 기존 존재하는 값과의 비교를 통해 최솟값을 갱신하는 구조, 문제 풀이에는 크게 문제가 없었지만 index out of range 에러를 방지하기 위한 N 과 i+3, i+5 과의 비교 식을 잘못 작성하였었습니다. 솔루션 def getMinCount(N): dp = [-1 for _ in range(N+1)] if N >= 3: dp[3] = 1 if N >= 5: dp[5] = 1 for i, v in enumerate(dp): if v == -1: continue if N >= i+3: if dp[i+3] == -1 or v+1 = i+5: if dp[i+5] == -1 or v+1 < d..

접근 DFS 또는 BFS로 풀 수 있지만 DFS로 풀었다가는 TLE에 걸릴 수 있다는 점에 명심해야 한다. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/1844 솔루션 def solution(maps): ROW_length = len(maps) COL_length = len(maps[0]) visited = [[False for _ in range(COL_length)] for _ in range(ROW_length)] queue = [[0,0,1]] while queue: ROW, COL, DIST = queue.pop(0) # 조건에 맞지 않는 경우는 모두 추가 탐색하지 않습니다. if ROW ROW_leng..

접근 처음에 O(N^2)로 솔루션을 작성했지만 당연히 TLE 해시 자료구조를 사용하여 문제를 O(N)으로 풀어야 한다. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/178871 솔루션 def solution(players, callings): Hash = {} for index, value in enumerate(players): Hash[value] = index for index, value in enumerate(callings): rank = Hash[value] # swap in players players[rank-1], players[rank] = players[rank], players[rank-1] # swap rank..

접근 stack과 array 탐색을 통해 문제를 해결해야 함을 알았으나 코드를 논리적으로 짜지 못하였음. 효율적인 로직을 짜는 것에 대한 훈련이 필요해 보임 문제 링크 Simplify Path - LeetCode 솔루션 class Solution: def simplifyPath(self, path: str) -> str: stack = [] word = "" for char in path + "/": if char == "/": # if .. -> delete lastest stack if word == "..": if stack: stack.pop() # if none of them and not an empty word, add stack elif word != "" and word != ".": s..

접근 완전탐색이 아닌 DP로 풀어야 하는 문제 DP[0]에 도달하여 True를 리턴하면 되기에 Bottom-up 방식으로 문제를 풀 수 있다. DP 리스트 길이를 s의 길이보다 하나 더 길게 설계하여 부드러운 솔루션을 작성해야 함 문제 링크 https://leetcode.com/problems/word-break/description/ 솔루션 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: s_length = len(s) DP = [False for _ in range(s_length+1)] DP[s_length] = True for i in range(s_length-1, -1, -1): for word in wordD..

접근 완전탐색으로 풀 수 있지만 DP로 푸는 것이 맞는 문제 Bottom-Up으로 풀 수 있는 지 확인해 보았지만 목적지에서 부터 출발지로 가는 경우의 수를 특정할 수 없음 따라서 Top-Down 방식으로 솔루션을 작성하여 해결 예제 1의 DP) 문제 링크 https://leetcode.com/problems/unique-paths/description/ 솔루션 class Solution: def uniquePaths(self, m: int, n: int) -> int: if m == 1 or n == 1: return 1 DP = [[1 for _ in range(n)] for _ in range(m)] for M in range(1, m): for N in range(1, n): DP[M][N] = ..

접근 DP의 기초, 위의 두 값이 아래 값을 결정하는 것을 확인하면 된다. 문제 링크 https://leetcode.com/problems/pascals-triangle/description/ 솔루션 class Solution: def generate(self, numRows: int) -> List[List[int]]: answer = [[1]] for i in range(1, numRows): tmp = [] tmp.append(1) for j in range(1, i): num = answer[i-1][j-1] + answer[i-1][j] tmp.append(num) tmp.append(1) answer.append(tmp) return answer