컴퓨터공학 & 정보통신/알고리즘 문제 풀이41 [백준] 17485 진우의 달 여행 (Large) c++ 개요 인터넷에 유사한 풀이가 없어 해당 문제의 솔루션을 공유합니다. 체크리스트 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.. 2023. 11. 17. [백준] 11052 카드 구매하기 c++ 문제 풀이 개요 대부분 풀이는 모두 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까지 활용해서.. 2023. 8. 26. [백준] 1463 1로 만들기 요약 처음에 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 2023. 7. 7. [백준] 2839 설탕 배달 요약 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.. 2023. 7. 2. [프로그래머스] 게임 맵 최단거리 접근 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.. 2023. 4. 16. [프로그래머스] 달리기 경주 접근 처음에 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.. 2023. 4. 15. 이전 1 2 3 4 5 ··· 7 다음
