DP

난이도 : 골드 4유형 : BFS / DFS / DP링크 : https://www.acmicpc.net/problem/12869구현 시간 : 30분     문제 풀이 이 문제는 BFS / DFS 알고리즘의 유형으로, 뮤탈리스크는 한 번의 공격에서 세 개의 SCV에 각각 9, 3, 1의 피해를 줄 수 있으며, 세 개의 공격 순서를 자유롭게 선택할 수 있습니다.즉, 모든 가능한 공격 순서를 고려하여 최소 공격 횟수를 찾아야 하는 문제입니다. 얼핏 보면 SCV 체력을 내림차순으로 정렬하고, 9 -> 3 -> 1 순서로 공격하면 쉽게 해결할 수 있지 않나? 싶지만아래 예제를 보면 그리디하게 문제를 해결할 수 없다는 것을 알 수 있습니다.SCV의 체력이 (12 , 10, 4)일 때첫번째 공격 -> 1, 3, 2 ..

난이도 : 실버 2유형 : 동적 계획법 / LIS링크 : https://www.acmicpc.net/problem/18353구현 시간 : 30분    문제 풀이이 문제는 ‘가장 긴 감소하는 부분 수열’을 찾는 문제로, LIS(가장 긴 증가하는 부분 수열) 알고리즘을 변형해서 해결할 수 있습니다.DP 테이블은 각 위치에서 끝나는 가장 긴 감소하는 부분 수열의 길이를 저장합니다. 예를 들어, dp[i]는 i번째 숫자를 마지막으로 포함하는 가장 긴 감소하는 부분 수열의 길이를 의미합니다.각 숫자를 기준으로 그 이전 숫자들과 비교합니다.만약 현재 숫자(arr[i])가 이전 숫자(arr[j])보다 작다면, 이전 숫자를 포함하는 감소하는 수열에 현재 숫자를 추가할 수 있습니다.이 경우, dp[i]를 dp[j] + ..

난이도 : 골드 3유형 : 위상 정렬 / 동적 계획법링크 : https://www.acmicpc.net/problem/1005구현 시간 : 1시간 (못품)        문제풀이위상 정렬 알고리즘을 공부하고 나서 처음으로 풀어본 문제이다. 노드의 방문 순서를 구현하는건 쉬웠지만, 특정 건물마다 필요한 최대 시간을 구하는 방법을 생각해내지 못했다 ㅜ indegree[] 배열을 이용해 노드의 진입 차수를 저장하고, 방문마다 해당 노드의 진입 차수를 차감하여 위상 정렬을 구현했다. BFS에서 탐색 레벨마다 날짜를 계산했었던 토마토 문제가 기억이 나서 위상 정렬에도 반복마다 최대 시간을 누적하는 방식으로 최대 시간을 저장했다. 하지만 이 방법은 이전 단계에서 소요된 시간을 다음 단계에 반영하지 못하므로, 특정 노..

난이도 : 실버 1유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/2156구현 시간 : 1시간     문제풀이이 문제를 풀기 위해 DP의 Bottom-Up 방식을 사용하며, 9465번 스티커 문제와 같이 이전 선택에 따라 다음 선택이 제한된다.연속 세 잔의 포도주를 마실 수 없기 때문에 마지막 잔의 앞 잔, 앞앞 잔의 값이 크다면 마지막 잔을 마시지 않을 수도 있다는 점도 고려해야 한다. 따라서 N 번째 잔의 최대값을 구하려면 아래와 같은 경우를 고려해야 한다.N 번째 잔을 마시지 않는다. N 번째 잔을 마신다.N - 3 -> N - 1 -> N 번째 잔을 마신다.N - 2 -> N 번째 잔을 마신다. 위 경우를 고려해서 표현한 점화식은 아래와 같다.DP[i]..

난이도 : 실버 1유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/9465구현 시간 : 30분       문제풀이이 문제를 풀기 위해 DP의 Bottom-Up 방식을 사용하며, 문제 해결의 핵심은 이전 선택에 따라 다음 선택이 제한된다는 점이다.특정 행의 스티커를 선택할 때, 바로 이전 행의 대각선 방향 스티커만 선택 가능하고, 따라서 N 번째 행의 스티커를 선택할 경우, 이전 선택 결과를 고려해야 최대값을 얻을 수 있다. 나는 이차원 배열을 선언하여 N번째 행의 스티커를 선택했을 때 최대값을 DP 테이블로 저장해서 구현하는 방식을 선택했다. 점화식은 아래와 같다.DP[i][0] = max(DP[i-1][1], DP[i-2][1]) + sticker[i][0]..

난이도 : 실버 3유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/2193구현 시간 : 30분      문제풀이위 문제는 전형적인 DP 문제 유형이다. 풀이는 반복문을 사용한 Bottom-Up 방식으로 해결하였다. 이 문제를 해결하기 위해서는 이친수의 규칙을 파악해야 한다.이진수가 0으로 끝나는 수는 다음 자리 숫자일 때, 0과 1로 생성되고, 1로 끝나는 수는 0으로 생성된다. 예를 들면, 10010 이라는 이진수는 다음 6자리수에서 10010 + 0, 10010 + 1 로 생성된다.또한, 10001 이라는 이진수는 다음 6자리수에서 10001 + 0 으로 생성된다. 따라서 N 번째 자리수에서 0으로 끝나는 이친수와, 1로 끝나는 이친수의 점화식은 다음과 같..

난이도 : 실버 3유형 : DP(동적 계획법)링크 : https://www.acmicpc.net/problem/7569구현 시간 : 30분     문제풀이위 문제는 전형적인 DP 문제 유형이다. 풀이는 반복문을 사용한 Bottom-Up 방식으로 해결하였고, Top-Down 방식은 다른 분들의 코드를 참조하여 작성했다. 우선 위 문제를 풀기 위해서는 점화식을 정의해야한다. DP[i] 번째의 최대 점수를 구하기 위해서는 DP[i-2] (두 개의 계단 전의 최대 점수) 와 DP[i-3] + stair[i-1] (세 개의 계단 전의 최대 점수 + 직전 계단의 점수) 간의 최대 값과 stair[i] (i 번째 계단의 점수) 를 더하면 구할 수 있다. A(i) = max(A(i-2), A(i-3) + K(i-1))..