반응형 [코딩테스트] 2주차: 동적 프로그래밍 (Dynamic Programming) 동적 프로그래밍 (Dynamic Programming)학습 주제:동적 프로그래밍의 기초 (Memoization, Tabulation)대표적인 DP 문제 풀이 (피보나치 수열, 배낭 문제, 최대 부분합 문제)학습 목표:동적 프로그래밍의 개념과 기초적인 구현 방법을 이해하고 적용할 수 있다.대표적인 동적 프로그래밍 문제를 해결하여 문제 해결 능력을 향상시킬 수 있다.학습 자료:동적 프로그래밍 개요와 원리피보나치 수열 (Top-Down, Bottom-Up) 구현 방법배낭 문제와 최대 부분합 문제 설명 및 구현실습 문제:1. 피보나치 수열 구현 (Top-Down, Bottom-Up)주어진 정수 n에 대해 피보나치 수열의 n번째 값을 구하는 함수를 작성하세요.# Top-Down Approach with Memoi.. 2024. 6. 4. [알고리즘] Week 3: 기하학적 동적 프로그래밍과 문자열 관련 동적 프로그래밍 Day 1: 기하학적 동적 프로그래밍 소개강의 내용:기하학적 동적 프로그래밍의 개념기하학적 문제를 해결하기 위한 동적 프로그래밍의 응용기하학적 문제의 특성 및 응용 사례기하학적 동적 프로그래밍의 기본 원리문제 분할 및 점진적 접근시간 복잡도 분석기하학적 동적 프로그래밍의 복잡도 및 효율성실습:파이썬을 사용한 간단한 기하학적 동적 프로그래밍 예제# 예제: 다각형의 최소 삼각분할 (Minimum Triangulation of Polygon)def min_triangulation(points): n = len(points) dp = [[0] * n for _ in range(n)] def cost(i, j, k): return abs(points[i][0] * points[j][1.. 2024. 6. 2. [알고리즘] Week 3: 고급 동적 프로그래밍 기법과 예제 Day 1: 고급 동적 프로그래밍 기법 소개강의 내용:동적 프로그래밍 복습동적 프로그래밍의 기본 개념과 원리메모이제이션과 테이블화 방법 (Top-down vs Bottom-up)고급 동적 프로그래밍 기법상태 압축 (State Compression)비트마스크 (Bitmasking)공간 복잡도 최적화 기법실습:간단한 동적 프로그래밍 문제 복습# 기본 동적 프로그래밍 예제: 피보나치 수열def fibonacci(n, memo={}): if n in memo: return memo[n] if n Day 2: 상태 압축 (State Compression)강의 내용:상태 압축의 개념상태 압축이란 무엇인가?상태 압축을 통해 공간 복잡도를 줄이는 방법상태 압축을 활용한 예제예제: 최소 비용 경.. 2024. 6. 2. [알고리즘] Week 8: 동적 프로그래밍 - 개념과 예제 Day 1: 동적 프로그래밍의 개념강의 내용:동적 프로그래밍의 정의와 중요성동적 프로그래밍(DP)이란 무엇인가?동적 프로그래밍의 기본 원리 (중복 부분 문제, 최적 부분 구조)동적 프로그래밍의 장점 및 활용 사례동적 프로그래밍과 분할 정복의 차이메모이제이션 (Top-down) vs. 테이블화 (Bottom-up)실습:간단한 동적 프로그래밍 문제 예제 설명# 피보나치 수열의 메모이제이션을 사용한 동적 프로그래밍 예제def fibonacci_memo(n, memo={}): if n in memo: return memo[n] if n Day 2: 피보나치 수열 (Bottom-up 방식)강의 내용:Bottom-up 방식의 개념테이블화 방법 (Bottom-up) 소개피보나치 수열의 Bot.. 2024. 6. 2. 이전 1 다음 반응형
