본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

dp

Algorithm/BOJ 2022. 3. 16. [BOJ] LCS 2(9252) [백준(BOJ)] 9252_LCS 2 JAVA 문제 : BOJ_9252번 LCS 2 문제 설명 두 개의 문자열이 있고, 그 문자열의 공통부분 수열 중 가장 긴 수열을 찾는 것이다. 기존의 LCS 문제와 다른 점은 수열의 길이뿐만 아니라 수열이 어떤 문자열인지 출력해야 한다. Solution DP dp[i][j] = 첫 번째 문자열의 인덱스가 i, 두 번째 문자열의 인덱스가 j 일 때 공통부분 수열의 최댓값 이라고 정의하자. 첫 번째 문자열의 i 번째 문자와 두 번째 문자열의 j 번째 문자가 같다면, dp[i][j] = dp[i-1][j-1] + 1로 dp 값을 할당한다. i와 j의 이전 하나 이전 인덱스의 dp 값에서 두 문자가 같다면 공통부분 수열의 길이가 늘어나므로 1을 더해주는 식이다. 첫 번째 문..

Algorithm/BOJ 2022. 3. 13. [BOJ] 가장 긴 바이토닉 부분 수열(11054) [백준(BOJ)] 가장 긴 바이토닉 부분 수열(11054) C++ 문제 : BOJ_11054번 가장 긴 바이토닉 부분 수열 문제 설명 DP 기존의 증가하는 수열, 감소하는 수열이 합쳐진 문제입니다. 수열이 증가하다가 감소가 되는 경우, 수열이 계속 증가하는 경우, 수열이 계속 감소하는 경우가 모두 바이 토닉 부분 수열입니다. 수열이 감소하다가 증가하는 경우는 해당되지 않습니다. DP를 활용해 해결할 수 있었습니다. Solution 앞서 언급한 세 가지 경우로 나누어서 DP 배열에 갱신해 주어야 합니다. 수열이 계속 증가하는 경우 -> dp[0][현재 인덱스] 수열이 증가하다가 감소가 되는 경우 -> dp[1][현재 인덱스] 수열이 계속 감소하는 경우 -> dp[2][현재 인덱스] 로 만들어 값을 계속 비..

Algorithm/BOJ 2022. 3. 12. [BOJ] LCS(9251) [백준(BOJ)] LCS(9251) C++ 문제 : BOJ_9251번 LCS 문제 설명 DP 최대 1000 글자의 두 단어가 주어지고, 두 단어에서 공통된 부분 수열 중 가장 긴 수열을 찾는 문제입니다. 문제 자체는 간단하지만, 완전 탐색을 이용하면 시간 초과가 나기 때문에 DP를 활용하여 해결해야 하는 문제입니다. Solution 위 표를 참고해서 DP 식을 짜야 합니다. 두 문자열의 길이만큼 2중 for 문을 순회하면서 문자가 같을 때와 다를 때 두 조건으로 dp 식을 세워줍니다. 두 문자열이 같다면, dp[i][j] = dp[i-1][j-1]+1 즉, 위 표에서 대각선의 dp 값 + 1입니다. 두 문자열이 다르다면, dp[i][j] = max(dp[i][j-1], dp[i-1][j]) 즉, 위 표에..

Algorithm/BOJ 2022. 3. 12. [BOJ] 계단 오르기(2579) [백준(BOJ)] 계단 오르기(2579) C++ 문제 : BOJ_2579번 계단 오르기 문제 설명 DP 각 계단마다 점수가 있고, 도착 지점까지 계단을 오르며 점수를 더해서 최댓값이 나와야 합니다. 이때 계단은 한 번에 한 계단이나 두 계단씩 오를 수 있고, 세 개의 계단을 연속해서 밟을 수는 없습니다. 그리고 마지막 도착 지점의 계단은 반드시 밟아야 합니다. Solution dp를 활용하여 해결하였습니다. dp[현재 계단 인덱스][이전 계단과 연속해서 밟았는지의 유무] = 현재 계단까지의 최댓값으로 dp 식을 짜봤습니다. 현재 계단에서 이전 계단과 연속해서 밟지 않았다면, 현재 계단 인덱스-2의 계단에서의 최댓값을 갱신해 주어야 합니다. 이때 현재보다 2가 낮은 인덱스의 계단은 이전 계단과 연속해서 밟..

Algorithm/BOJ 2022. 3. 12. [BOJ] 평범한 배낭(12865) [백준(BOJ)] 평범한 배낭(12865) C++ 문제 : BOJ_12865번 평범한 배낭 문제 설명 DP(냅색 알고리즘) DP 문제 중 유명한 문제인 평범한 배낭 문제입니다. 물품의 수와 배낭에 담을 수 있는 최대 무게가 주어집니다. 이어서 각각 물품의 무게와 가치가 주어지며, 가방 안에 최대 무게를 초과하지 않게 넣었을 때 최대 가치를 출력하는 문제입니다. 이때 주의할 것은 각각의 물품은 하나만 들어갈 수 있으므로, 하나의 물품이 중복되게 들어가는 경우의 수는 피해야 합니다. Solution dp를 이용한 풀이를 해봤습니다. 2차원 dp를 다음과 같이 만들었습니다. dp[i 번째까지 물건을 사용했을 때][무게가 j 일 때] = 최댓값 1~n까지의 물건에서 현재 최댓값을 알고자 하는 무게가 j라고 했을..

Algorithm/BOJ 2022. 3. 9. [BOJ] 오르막 수(11057) [백준(BOJ)] 오르막 수(11057) C++ 문제 : BOJ_11057번 오르막 수 문제 설명 DP DP로 해결할 수 있는 오르막 수입니다. 1부터 1,000의 수 중 하나인 N이 주어지면, N 자리로 이루어진 오르막 수의 개수를 구하는 문제입니다. 여기서 오르막 수란, 가장 큰 자릿수부터 가장 작은 자릿수가 오름차순으로 올라가야 하는데, 이 문제에선 수가 같아도 오름차순으로 인정해 줍니다. 또 특이한 점은 수가 0으로 시작할 수 있습니다. Solution 저는 2차원 dp 배열을 만들어 문제를 해결했습니다. dp[수의 길이][가장 큰 자릿수의 수] -> 만족하는 수의 오르막 수의 개수 우선 N이 1인 경우를 생각해봅시다. 문제의 조건이 '수는 0으로 시작할 수 있다.' 임으로, 0,1,2,3 .....

Algorithm/BOJ 2022. 3. 9. [BOJ] 제곱수의 합(1699) [백준(BOJ)] 제곱수의 합(1699) C++ 문제 : BOJ_1699번 제곱수의 합 문제 설명 DP DP로 풀 수 있는 기본문제 동전 2와 유사한 제곱수의 합 문제입니다. 1부터 10만까지의 수 중 하나가 주어졌을 때, 그 수를 제곱수로 표현할 수 있는 최소항 개수를 구하는 문제입니다. 예를 들어, 11의 경우엔 11 = 2^2 + 2^2 + 1^2 + 1^2 + 1^2 5개 항도 가능합니다. 하지만, 11 = 3^2 + 1^2 + 1^2 의 3개항으로도 표현이 가능하므로 11이 주어지면 3을 출력해야 합니다. Solution 항의 개수를 최소한으로 쓰기 위해 처음 했던 생각은, 단순하게 주어진 수와 최대한 가까운 제곱수를 구하는 것이었습니다. 예를 들어, 145면 12^2, 100이면 9^2과 같이..

Algorithm/BOJ 2022. 3. 9. [BOJ] 동전 2(2294) [백준(BOJ)] 동전 2(2294) C++ 문제 : BOJ_2294번 동전 2 문제 설명 DP DP로 풀 수 있는 기본문제 동전 2입니다. n 개의 동전이 주어지고, 동전마다 값이 주어집니다. 이때 동전들을 조합해서 주어진 k의 값을 최소한의 동전을 써서 맞춰야 합니다. Solution 큰 동전이 항상 작은 동전의 배수임이 보장된다면 그리다 하게 풀 수 있지만, 위 문제는 동전끼리 서로 배수가 아닌 값 들이기 때문에 dp를 이용해 경우의 수를 다 봐줘야 합니다. 1원 ~ k 원을 확인하는 for 문안에 1 ~ n 번째 동전을 이용하는 for 문으로 2중 for 문이 필요합니다. k는 최대 10,000이고 n은 최대 100이므로 최대 for 문이 1,000,000입니다. 동전을 확인할 때, 확인해야 하는..

이전 1 2 다음

티스토리툴바