프로그래밍 및 개발 공부하기

📘 백준 1446번: 지름길 C++📌 문제 설명세준이는 매일 아침 고속도로를 타고 학교에 갑니다.이 고속도로는 0번 위치부터 D번 위치까지 이어진 직선 도로입니다.고속도로는 단방향이며, 차는 매 순간 오직 앞으로만 이동할 수 있습니다.그런데 이 고속도로에는 지름길이 존재한다고 합니다.지름길은 특정 위치에서 출발하여, 더 먼 위치로 곧장 이동할 수 있는 특수한 경로입니다.각 지름길은 시작점, 도착점, 그리고 해당 구간을 이동하는 데 드는 거리(비용)가 주어지며,기존의 고속도로보다 비용이 작을 수도 있고, 아닐 수도 있습니다.지름길은 단방향이며, 역주행은 절대 불가능합니다.우리는 이 지름길과 일반 도로를 조합하여,0번 위치에서 D번 위치까지 이동하는 최소 거리를 구해야 합니다.🧾 입력 형식 첫째 줄에..

📘 동적 계획법(Dynamic Programming)이란?해결편: Bottom-Up 방식 (테뷸레이션 Tabulation)⚠️ 메모이제이션의 구조적 문제메모이제이션(Memoization)은 재귀 호출 중복을 방지하기 위해 사용됩니다.한 번 계산한 값을 기록하여,같은 계산이 들어왔을 때 다시 재귀하지 않고 저장된 값을 반환합니다.하지만 구조적으로 보면 다음과 같은 흐름을 갖습니다:F(n) → F(n-1) → F(n-2) → F(n-3) → ... → F(1) → F(0) → F(1) → F(2) → ... → F(n) 계산을 시작하기 위해 F(n)을 호출하면 F(n-1), F(n-2) 등으로 재귀 호출이 분기되..

🌐 동적계획법(Dynamic Programming)이란?🧠 해결편: 메모이제이션🔍 재귀의 문제📌 문제 구조: 계산이 반복된다피보나치 수열을 재귀적으로 구현하면 코드가 다음과 같습니다.int fib(int n) { if (n 이 코드만 보면 단순하고 깔끔합니다.하지만 fib(n)을 계산하기 위해 fib(n-1)과 fib(n-2)를 호출하고,그 둘도 또 각각 재귀로 내려가기 때문에,같은 계산이 여러 번 반복됩니다.🔎 구조적으로 어떤 일이 일어나는가?예를 들어 fib(5)를 호출하면 다음과 같은 구조가 생깁니다.fib(5)├─ fib(4)│ ├─ fib(3)│ │ ├─ fib(2)│ │ │ ├─ fib(1)│ │ │ └─ fib(0)│ │ └─ fib(1)│ └─ fib(2..