DP16 코드트리 [자바 java] 최장 공통 부분 수열 https://www.codetree.ai/missions/2/problems/longest-common-sequence?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제는 문자열 두 개가 주어지고, 이 두 문자열의 부분 문자열 중 가장 길게 겹치는 문자의 길이를 구해야 한다. ABA ABBA 테스트케이스로 예를 들어보자면, A B B A A 1 1 1 1 B 1 A 1 위 표를 dp라고 보면, 열은 첫번째 문자열, 행은 두번째 문자열을 나타낸다. dp[i][j]는 첫번째 문자열.. 2023. 8. 17. 코드트리 [자바 java] 둘 중 하나 잘 고르기 https://www.codetree.ai/missions/2/problems/choose-one-of-two-points?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 꼭 n개를 뽑아야 한다 같은 유형의 dp를 푸는 방식을 사용했다. 이 문제에서는 n개의 카드 짝이 주어지고, 이 카드들 중 빨강, 파랑 을 정확히 n번 씩 사용했을 때 카드의 합의 최댓값을 구해야 한다. 위와 같이 주어졌다고 가정해보자. 위 4가지 카드 중 빨강, 파랑을 각각 2개씩 뽑아야 한다. 이를 풀기 위해 dp.. 2023. 8. 16. 코드트리 [자바 java] 적절한 옷 고르기 https://www.codetree.ai/missions/2/problems/select-proper-clothes?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제는 다소 복잡해보이는 문제이지만, 막상 풀이를 생각해보면 크게 어렵지는 않다. 문제에서 입력으로 옷 수, 해당 옷들의 화려함, 시작일, 종료일이 주어진다. 이 옷들을 입는 경우들을 적절하게 조합해서 만족도의 최댓값을 구하는 문제이다 . 나는 dp를 이차원배열로 만들고, 해당 일에 해당 옷을 입는 경우 중 가능한 가장.. 2023. 8. 15. 코드트리 [자바 java] 연속 부분 합의 최댓값 구하기 https://www.codetree.ai/missions/2/problems/max-of-partial-sum?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제는 연속된 수들의 합의 최댓값을 구하는 문제이다. dp문제 중에는 현재 탐색하는 지점의 앞에 있는 값을 모두 탐색해야 하는 경우도 많은데, 이 문제는 연속된 값을 구하는 문제이므로 바로 앞 dp값만 계산하면 된다. dp[i]의 값은 앞서 계속 더해왔던 값의 최댓값과 arr[i]를 단독으로 사용했을 때의 값을 비교한 값 중.. 2023. 8. 14. 코드트리 [자바 java] 동전 거슬러주기 https://www.codetree.ai/missions/2/problems/coin-change?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 거슬러줄 금액과 동전의 종류가 나오면, 거슬러줄 수 있는 최소한의 동전 수를 출력하는 문제이다. 이 문제는 dp를 사용했다. 0부터 해당 금액까지의 dp배열을 선언하고, 사용할 수 있는 동전들을 하나 쓰는 방법을 모두 비교하여 최솟값을 넣도록 하였다. import java.util.*; import java.io.*; import java... 2023. 8. 13. 코드트리 [자바 java] 부분수열의 합이 m https://www.codetree.ai/missions/2/problems/the-sum-of-the-subsequences-is-m?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제는 동전문제와 비슷하다. 하지만 이 문제에서 유의할 점은 동전을 오직 한번만 사용해야한다는 것이다. 이를 위해 합으로 만들어야 하는 수만큼 dp 값을 만들고, 뒤에서부터 탐색을 진행한다. 순서는 상관이 없으니 고려하지 않는다. 0 10000 10000 10000 10000 10000 여기서 만약 .. 2023. 8. 12. 이전 1 2 3 다음
