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

🌐 동적계획법(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..

🔷 동적계획법(Dynamic Programming)이란? 문제편✅ 정의동적계획법(Dynamic Programming)은 하나의 문제를 더 작은 하위 문제로 나누고, 그 하위 문제의 결과를 저장해 중복 계산을 피함으로써 전체 문제를 효율적으로 해결하는 알고리즘 설계 기법입니다.동적계획법은 동일한 계산을 반복하지 않기 위해 계산 결과를 저장하고 재활용합니다. 이 방식은 특히 하위 문제가 반복적으로 등장하는 문제에서 시간 효율성을 극적으로 높입니다.✅ 등장 배경프로그래밍에서 많은 문제들은 겉보기에 복잡하지만, 내부적으로는 같은 계산이 반복되는 구조를 가지고 있습니다. 이러한 문제를 단순 재귀(recursion)로 해결할 경우, 같은 하위 문제를 여러 번 다시 계산하는 비효율적인 구조가 생깁니다.예를 들어,..

🔷 문제번호: 후보 추천하기 (BOJ 1713) Python✅ 문제설명월드초등학교 학생회장 후보를 추천으로 뽑습니다.추천받은 학생들의 사진을 게시할 사진틀이 있고, 다음 규칙을 따릅니다: 학생이 추천을 받으면 반드시 사진틀에 올라가야 합니다. 이미 게시된 학생이면 추천 수만 증가합니다. 비어있는 자리가 없으면, 추천 수가 가장 적은 학생을, 여러 명이면 게시된 지 가장 오래된 학생을 제거합니다. 새로운 학생이 올라가면 추천 수는 1, 게시 시각은 현재 시간입니다. 마지막에 사진틀에 올라간 학생들을 오름차순으로 출력합니다.✅ 아이디어 추천 수, 게시 시각, 게시 여부를 관리하는 구조체를 각 학생 번호에 연결합니다. 사진틀에 올라간 학생 목록은 따로 배열로 관리합니다. 추천..