
이번 글의 목적은 피보나치같은 대표적인 예시로 다이나믹 프로그래밍에 대해 뜯어보기 위함이 아닌저만의 접근(풀이)방식에 대해서 정리한 글입니다. 도움이 되셨다면 좋겠네요.도입부알고리즘 문제를 조금 풀어본 사람의 경우, 문제를 풀다보면 “DP로 풀어야하나?” 라는 감이 올 때가 있습니다.예를 들자면, 완전 탐색을 요구하는 문제인데 입력이 굉장히 클 경우, 일반적인 DFS, BFS로 풀 수가 없다고 느꼈을 때입니다. 아마 동전, 배낭문제와 같이 잘 알려진 문제들에 대해서는 곧바로 풀이를 할 수 있겠지만, 이러한 문제들은 코딩테스트에서 잘 나오지 않죠. 심지어 “DP로 풀어야하나?”라는 생각도 들지않게 나올 때도 있습니다.“DP로 풀어야겠다!”라고 생각을 해도 좀처럼 풀리지 않을텐데, 이유는 문제마다 공식이 제..
![[PS] 백준17485 : 진우의 달 여행 (Large)(Java)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FUNQ1R%2FbtsKgDmtGxV%2FKDiYoKgYtJ0NxulWePKso0%2Fimg.png)
문제https://www.acmicpc.net/problem/17485 풀이다이나믹 프로그래밍 풀이접근법처음에는 다익스트라로 최소비용 구하면 되는 것 아냐? 라는 생각을 잠깐 했지만 출발지점이 1000개가 될 수 있기에 DP로 풀었다. 문제 조건해당 문제에서 각 원소의 위치에서 할 수 있는 행동은 3가지다.왼쪽 아래중간오른쪽 아래또 다른 조건으로는 이전 행동과 같은 행동을 취하지 못한다. dp로 풀이를 하기로 했으니 각 원소의 위치의 최선의 값을 어떻게 찾을지 생각하는 것 뿐이다.간단하게 생각하면 dp[i][j]는 3가지 이전해 + 현재값 중 최소값을 선택하면 될 것으로 보인다. 그러나 다음해를 구하기 위해서 이전해가 어떤 방향에서 진행된 값인지 알 필요가 있다.이를 위해 3차원 배열로 dp배열을 구성했..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42897#qna 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이다이나믹 프로그래밍 풀이접근법나는 보통 DP 문제를 풀 때 각 원소에서 선택할 수 있는 최선의 값을 고르는 점화식을 생각한다.이 문제도 동일한 방식으로 접근했고, i번째 집을 털 경우와 털지 않는 경우 두 가지 중 최대값을 선택하는 점화식을 생각했다. 처음 생각한 점화식은 다음과 같다.DP[i] = Math.max(DP[i-1], DP[i-2] + money[i]) DP[i-1]의 경우..
개요관계형 데이터베이스 관리 시스템데이터를 테이블(관계) 형태로 관리행(Row)과 열(Column)로 구성테이블 간 관계를 통해 데이터를 조작하고 검색주로 SQL을 사용SQLRDBMS에서 데이터를 관리하기 위한 표준화된 언어로, 주로 데이터 정의(DDL), 데이터 조작(DML), 데이터 제어(DCL), 트랜잭션 관리(TCL) 명령어로 구성됩니다.DDL (Data Definition Language): 데이터베이스와 테이블 구조를 정의하는 언어예시: CREATE, ALTER, DROPDML (Data Manipulation Language): 데이터를 삽입, 수정, 삭제, 조회하는 언어예시: SELECT, INSERT, UPDATE, DELETEDCL (Data Control Language): 데이터베이..