티스토리

Ahranah

검색하기

블로그 홈

Ahranah

ahranah.tistory.com/m

아란정 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

[백준 12865][dp] 배낭: knapsack 드디어 기대하고 기대하던 배낭문제다. 이 문제를 만나고 나서야 DP의 의미를 이해할 수 있게 되었다. DP는 a, b, c, d가 있을 때 abc, abd, acd ... 이런 조합을 만드는 문제가 아니었다.a를 넣었을 때와 넣지 않았을 때 두 개로 나뉜 경우에 대해 각각이 b를 넣었을 때와 넣지 않았을 때로 나누는 방식으로 풀었어야 했다. 헐랭~ https://youtu.be/rhda6lR5kyQ?si=wVKtxIhe4A9wsj81DP는 초깃값 설정이 중요하다. 우리가 구하고자 하는 값은 가치의 최댓값이고, 입력값은 항목의 개수와 각 항목당 무게와 가치가 주어진다. dp의 data는 value 의 sum이다. 가질 수 있는 value의 최대값을 구하는 문제이므로 n 번째 항목까지의 value sum을 .. 공감수 0 댓글수 2 2024. 6. 30.
[프로그래머스][dp] 땅따먹기 프로그래머스 알고리즘 강좌가 dp 이해에 도움이 됐다는 글을 보고 '땅따먹기'를 시도했다. 직접 짜보고 dp 코드와 비교하니까 dp의 느낌이 확 와닿는다. dp는 모든 경우의 수를 확인하는데, 각 요소가 있고, 없고에 따라 경우를 만든다. 문제와 함께 보자 문제ㅎ. 하지만 나는 어제 dp를 정리해 놓고도 전혀 떠오르지 않아서 풀리는 대로 풀었다. (이해가 덜 됐다ㅜ)내 풀이 방법1. 현재 index(j)를 이전 max의 index와 비교해 같지 않은 경우에만 들어간다. - if ( i == 0 ) 인 예외를 주는 데 시간이 오래 걸렸다. 다시 생각해 보니 첫 열은 index가 뭐든 관계없으니까 preindex 처음 선언할 때 preindex = -1; 했으면 됐겠다. 2. index가 같지 않은 경우.. 공감수 0 댓글수 0 2024. 6. 26.
[백준 1106] DP 동적프로그래밍 동적 프로그래밍(Dynamic programming)이란 과거에 사용한 값을 중복해서 사용하는 경우에서 사용할 알고리즘을 말한다. 대표적으로 배낭 문제, 피보나치 수열이 있다. 이전에 구해놓은 값을 재사용하기 때문에 재귀함수를 이용해야 한다. 재귀함수를 naive하게 사용하게 되면 시간, 공간복잡도가 폭발적으로 증가한다.부분 문제에 대한 값을 미리 계산해놓고 한 번에 이용하는 것이 시공간 관점에서 효율적이다. 따라서 Memoization(메모이제이션)을 활용한다.같은 문제의 풀이를 재활용하는 방식인데, 재귀의 방법이 있다. 부분 문제에 대한 경우의 수를 모두 구할 건데, 이 때 재귀를 사용한다. 부분 문제를 넣고(1), 빼고(0) 에 대한 경우의 수를 구하는 것이다.dp의 memoization은 하향식으.. 공감수 0 댓글수 0 2024. 6. 25.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.