Hey Tech

📝 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 💡 접근법 다이나믹프로그래밍(DP)을 활용하여 해결하였습니다. DFS 알고리즘으로도 해결 가능합니다. 이와 관련한 해설은 이곳을 참고해 주세요. DP를 활용한 풀이는 다음과 같습니다. 저는 근무 가능일이 아닌 퇴사일로부터 근무가 가능한 첫 날까지 역순으로 근무 선택일에 따른 이익을 계산하였습니다. 즉, 퇴사일로부터 \(i\)번째까지 근무한 경우 이익은 \((i+1)\)까지 근무한 경우의 이익과 \((i+t)\)까지 근무한 경우의 이익 중 최댓값을 고르도록 로직을 작성하였습니다. 만일 해당 일에 근무하지 않으면 \(i\)번째 ..

📚 문제 원본: https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 🔥 접근법 문제를 보자마자 전형적인 다이나믹 프로그래밍(Dynamic Programming, DP) 유형의 문제라고 생각합니다. 유사한 접근법을 사용한 DP 문제로서 "최저 비용의 노드만 거쳐 미로를 탈출하는 문제"를 접한 경험이 있습니다. 본 문제의 핵심 전략은 다음과 같습니다. 삼각형 맨 아래부터 2개의 인접한 자식 노드 중 큰 값을 부모 노드에 더해 부모 노드를 업데이트해 나가는 것입니..

본 포스팅에서는 다이나믹(동적) 프로그래밍에 대해 알아봅니다. 📚 목차 1. 다이나믹 프로그래밍이란? 2. 다이나믹 프로그래밍 예제 3. 재귀함수 기반 구현 3.1. 소스코드 3.2. 문제점 3.2.1. 연산 복잡성 3.2.2. 문제 발생의 원인 3.2.3. 문제 해결 방안 4. 다이나믹 프로그래밍 기반 구현 4.1. 탑 다운 방식(재귀함수 활용) 4.1.1. 메모이제이션이란? 4.1.2. 소스코드 4.1.3. 특징 4.2. 바텀 업 방식(반복문 활용) 4.2.1. 소스코드 4.2.2. 특징 1. 다이나믹 프로그래밍이란? 다이나믹(동적) 프로그래밍은 큰 문제를 작은 문제로 나누어 연산 속도와 메모리를 최대한으로 활용하기 위한 기법입니다. 특정 값을 얻기 위해 매번 같은 결과를 반환하는 연산을 굳이 반복해..