# dynamic programming

332개의 포스트

1949. 우수 마을

시간 제한: 2초메모리 제한: 128MBNaive 하게 각 마을을 포함시키거나 빼면서 모든 경우를 조사하여 풀 수 있다. 그러나 시간 복잡도는 O(2^N)이다. 대신, xxoxA oxoxA 두 순서로 이루어진 경우가 존재할 때, 뒤에 A 순서는 중복되므로 다시 계산해

4일 전
·
0개의 댓글
post-thumbnail

[BOJ] 구간 합 구하기 4 with node.js

JavaScript를 이용한 백준 11659 구간 합 구하기 4 문제를 풀이한 글입니다.수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주

5일 전
·
0개의 댓글
post-thumbnail

Longest Increasing Path in a Matrix

리트코드 추천으로 처음 접하게 된 문제이다. 난이도가 Hard 여서 상당히 걱정을 하고 문제를 읽게 됐는데 생각보다 할만해 보였고 Memoization 을 이용한 DP 방식으로 쉽게 풀수있을거라고 생각했다. Matrix가 주어졌을때 각 원소를 탐색하면서 원소가 커지는

6일 전
·
0개의 댓글

BOJ 15989 1, 2, 3 더하기 4 실버1

15989 1, 2, 3 더하기 4 실버1

6일 전
·
0개의 댓글

2213. 트리의 독립집합

시간 제한: 2초메모리 제한: 128MBNaive 하게 풀려면, 다음과 같이 DFS를 진행하면서, 각 node를 포함시킬 때와 포함시키지 않을 때를 모두 조사하여 가능한 최대를 구하면 된다. 그러나, 이 경우 시간 복잡도는 O(2^N)이다.이때, 각 node에서의 최대

2022년 5월 15일
·
0개의 댓글
post-thumbnail

[ BOJ / Python ] 14925번 목장 건설하기

이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 맨 처음에는 브루트포스를 통해 문제를 파악하였고, N, M의 범위가 1000까지기 때문에 당연히 시간 초과가 발생할 것이라 생각하였다. 그래서 다이나믹 프로그래밍으로 접근하였고, 다음과 같이 점화식을 구할 수 있었다.

2022년 5월 9일
·
0개의 댓글
post-thumbnail

[Leetcode]787. Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights\[i] = $from_i$, $to_i$, $price_i$ indicates that

2022년 5월 8일
·
0개의 댓글
post-thumbnail

Jump Game II

다시 한번 풀어보는 Jump Game 문제이다. 사실 이 모든 문제들은 GP에서 한번씩 봤던 경험은 있었지만 전부 다 이해하지는 못했었고. 애초에 컴퓨터나 주변환경이 많이 다르기때문에 조용하게 집에서 큰 화면이랑 좋은 노래 들으면서 풀고있기 때문에 훨씬 더 집중이 잘되

2022년 5월 3일
·
0개의 댓글
post-thumbnail

Jump Game

리트코드에서 상당히 유명한 시리즈인 Jump Game 문제를 풀었다. Jump Game 같은 경우에는 DP를 활용한 시리즈가 굉장히 많은데 이 문제 또한 DP를 활용한 정말 유명한 문제중 하나이다. DP에서 사용되는 Memorization 기법이란 반복되는 계산을 방지

2022년 5월 3일
·
0개의 댓글
post-thumbnail

Delete and Earn

이 문제 또한 GP 에서 처음 접했던 문제였고, 당시에 문제를 봤을때는 많이 혼란스러웠다. 이 전 DP 문제들을 풀면서도 아직 DP의 개념이 많이 헷갈리는 상태였는데 이 문제를 다시 보자니 또 어지러웠고 어떻게 해야할지 고민이 많이 갔었다. 하지만 문제를 천천히 다시

2022년 5월 3일
·
0개의 댓글
post-thumbnail

House Robber

예전에 GP에서 풀어봤었던 House Robber 이라는 문제이다. 미국에 있었을때 DP 공부를 좀 했었는데 아마 가장 이해가 안됐었던 유형의 문제중 하나였을거같다. 다시 풀어봤을때도 사실 감이 하나도 안왔고 재귀 과정이 너무 헷갈렸어서 어지러웠지만 DP 유형의 문제들

2022년 5월 2일
·
0개의 댓글
post-thumbnail

Climbing Stairs

아마 내 블로그에 올라오는 첫 easy 레벨의 리트코드 문제라고 생각하지만 DP에 대한 이해도를 효율 높고 빠르게 터득할수있도록 이런 기초부터 다지면서 문제를 계속 풀어볼 생각이다. Climing Stairs 문제는 계단을 1개 혹은 2개까지 올라갈수있는데 n만큼의 계

2022년 5월 2일
·
0개의 댓글
post-thumbnail

Coin Change

오랜만에 사회에서 풀어보는 문제이다. 확실히 코딩 문제 푸는 기간을 오래 쉬었던만큼 부족한 부분이 많이 느껴졌고. 어떤 문제를 올릴까 고민을 많이 했는데 이 문제가 되게 좋은 문제라는걸 느껴서 올리고싶었다. 예전에 한참 고민을 많이 했었던 2022 SK ICT Fami

2022년 4월 30일
·
0개의 댓글

1103. 게임

문제 시간 제한: 2초 메모리 제한: 512MB Problem Analysis Algorithm Data Structure 결과 other

2022년 4월 28일
·
0개의 댓글
post-thumbnail

[BOJ] 1912 연속합

https://www.acmicpc.net/problem/1912아이디어max( dp\[i-1] + arr\[i] , arr\[i] ) : 이전 max 값에 i번째를 더한 것(연속)과 i번째부터 새로 시작하는 것(연속 중단)을 비교하여 dp에 담았다.dp\[]

2022년 4월 24일
·
0개의 댓글
post-thumbnail

[BOJ] 9095 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095아이디어가지고 있는 숫자가 1, 2, 3 이므로n-1 만드는 방법 + 숫자 1 사용하기 && n-2 만드는 방법 + 숫자 2 사용하기 && n-3 만드는 방법 + 숫자 3 사용하기와 같은 방법으로

2022년 4월 23일
·
0개의 댓글
post-thumbnail

[백준] 1463 - 1로 만들기

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

2022년 4월 22일
·
0개의 댓글
post-thumbnail

백준 9252, LCS 2 - DP

https://www.acmicpc.net/problem/9252dp\[i]\[j]: str1\[i] 문자까지와 str2\[j] 문자까지에 대한 LCS 문자열출력, LCS 문자열: dp\[str1.length()]\[str2.lenength()]2중 for문으

2022년 4월 22일
·
0개의 댓글