Ribbon Kingdom (Programming)

  • 홈
  • 태그
  • 방명록

알고리즘/15. DP (Dynamic Programming) 1

[DP] 2차원 배열에서 시작점 (0, 0)부터 도착점 (3, 3)까지의 최소 경로 합

⭐ 문제 설명arr = [ [1, 3, 5, 8], [4, 2, 1, 7], [4, 3, 2, 3], [5, 6, 1, 2]]주어진 2차원 배열 arr에서,오른쪽 또는 아래쪽으로만 이동할 수 있다(0, 0)에서 시작해서 (3, 3)까지 이동할 때지나는 경로 상의 값들을 모두 더했을 때 가장 작은 합을 구하는 것이 목적 ⭐ 핵심 아이디어dp[i][j]는 (0, 0)에서 (i, j)까지 이동했을 때의 최소 비용(합) 을 의미한다.dp[0][j] 와 dp[i][0]은 경로가 한 방향(오른쪽 혹은 아래)으로만 가능하므로 누적합으로 초기화하기.그 외의 나머지 위치에 대해서는,위와 같이 왼쪽에서 오는 경우와 위쪽에서 오는 경우 중 작은 값을 선택해서 arr[i][j]를 더함.dp[i][j] =..

알고리즘/15. DP (Dynamic Programming) 2025.04.17
이전
1
다음
더보기
프로필사진

  • 분류 전체보기 (1099)
    • TIL (18)
      • IT 컨퍼런스 (4)
      • 감사일기 (5)
      • 배울점 찾기 (5)
      • 선배와의 만남 (0)
      • 다른 개발자분들에게 배우기 (4)
      • 아이디어 (0)
    • Game AI & Unity (155)
      • Unity (17)
      • 유니티를 이용한 달리기 게임 제작 (0)
      • Procedural Landmass Generat.. (50)
      • Java Steering game (36)
      • L-system algorithm (25)
      • concepts (27)
    • 알고리즘 (34)
      • 코딩테스트 후기 (2)
      • 알고리즘 개념 (1)
      • 1. DAT (Direct Address Tabl.. (2)
      • 2. Binary Search (4)
      • 3. Two Pointer, Sliding Win.. (3)
      • 4. Greedy (0)
      • 5. Prefix Sum (0)
      • 6. Priority Queue (3)
      • 7. Backtracking (0)
      • 8. DFS (8)
      • 9. BFS (2)
      • 10. Flood Fill (0)
      • 11. Dijkstra (1)
      • 12. Floyd Warshall (0)
      • 13. Union Find (3)
      • 14. MST(Minimum spanning tr.. (1)
      • 15. DP (Dynamic Programming.. (1)
      • 16. Hash_Map, Unordered Ma.. (0)
      • 17. Balanced BST_TreeMap,Ma.. (0)
      • 18. Segment Tree (0)
      • 19. 기타 (3)
    • WEB (584)
      • HTML (10)
      • CSS_ concepts (48)
      • SpringBoot (20)
      • Bootstrap (5)
      • CSS_구획 나누기 (Grid System,Flo.. (20)
      • Django concept (114)
      • Django prac (181)
      • 웹 호스팅, 배포 (19)
      • Django를 활용한 웹사이트 제작 (0)
      • 학원 홈페이지 만들기 (2)
      • Neflang 홈페이지 만들기 (1)
      • JavaScript (78)
      • Vue.js (76)
      • Node.js (4)
      • React.js (6)
    • python으로 게임 만들기 (0)
      • 테트리스 (27)
      • 도넛 먹기 게임 (4)
      • pygame (12)
    • 인공지능, 머신러닝 (1)
      • PyTorch (1)
      • Matlab (0)
      • Concepts (19)
      • 논문 리뷰 (0)
      • Chat- GPT3 (1)
      • 구글 이미지 데이터 크롤링 (4)
      • Marion AI competition (0)
      • Django + DataScience (6)
      • Django + Crawling (9)
    • DataBase (54)
      • SQL (32)
      • MariaDB (5)
      • DB concept (2)
      • ADsP (9)
      • Programmers SQL 고득점 키트 (0)
      • SQLD (6)
    • 기타 (18)
      • Git (4)
      • 정처기 (3)
      • 라즈베리파이 (0)
      • SSAFY mini Projects (2)
      • IDE (2)
      • CS (6)

Copyright © Kakao Corp. All rights reserved.

티스토리툴바