Will the Guru

Category: Problems

  • (KOR) 가장 긴 증가하는 부분 수열 5

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/14003 Solution Key Points (KOR) 가장 긴 증가하는 부분 수열와 같은 방법으로 풀이하면 시간초과가 발생한다. 이는 해당 풀이가 O(N^2) 의 시간복잡도를 가지고 있기에, 인풋값이 몇만이 되는 경우 시간초과를 리턴하게 된다. 풀이 방법 solve() – 주어진 배열을 순회하면서 새로운 배열에 정렬된 순서로 저장하는 것을 기본으로, 이진 탐색을 이용하여 새로운…

  • (KOR) 가장 긴 증가하는 부분 수열 3

    Problem – ⭐️ https://www.acmicpc.net/problem/12738 Solution Key Points (KOR) 가장 긴 증가하는 부분 수열 2 와 풀이 방법 똑같다

  • (KOR) 가장 긴 증가하는 부분 수열 2

    Problem – ⭐️⭐️ https://www.acmicpc.net/problem/12015 Solution Key Points (KOR) 가장 큰 증가 부분 수열 와 같은 방법으로 풀이하면 시간초과가 발생한다. 이는 해당 풀이가 O(N^2) 의 시간복잡도를 가지고 있기에, 인풋값이 몇만이 되는 경우 시간초과를 리턴하게 된다. 풀이 방법 주어진 배열을 순회하면서 새로운 배열에 정렬된 순서로 저장하는 것을 기본으로, 이진 탐색을 이용하여 새로운 수가…

  • (KOR) 가장 긴 감소하는 부분 수열

    Problem – ⭐️ https://www.acmicpc.net/problem/11722 Solution Key Points (KOR) 가장 큰 증가 부분 수열 의 반대 문제. 풀이 방법은 똑같다.

  • (KOR) 가장 큰 증가 부분 수열

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/11055 Solution Key Points (KOR) 가장 긴 증가하는 부분 수열 문제와 매우 유사. 단, DP 배열에 들어가는 값들이 이 문제에서는 길이가 아니라 해당 값들의 합이 들어가므로 차이가 존재한다. 풀이 방법 기본적으로 dp 배열에는 본인, 즉 arr[i]의 값이 들어가야한다. 이는 가장 base case일 때, 수열의 길이가 1인 경우 수열의…

  • (KOR) 가장 긴 바이토닉 부분 수열

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/11054 Solution Key Points (KOR) 가장 긴 증가하는 부분 수열 문제와 매우 유사. 풀이 방법은 거의 똑같다고 보면 된다. 풀이 방법 바이토닉 수열은 문제에 설명되어 있듯이, 특정 수를 기준으로 나눴을 때, 왼쪽 수열은 점점 증가하는 수열, 오른쪽 수열은 점점 감소하는 수열이 된다. 점점 감소하는 수열은 점점 증가하는 수열을…

  • (KOR) 가장 긴 증가하는 부분 수열

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/11053 Solution Key Points LIS(Longest Increasing Subsequence) 문제로, 다이내믹 프로그래밍에서 자주 출제되는 문제 유형이다. 참고: https://www.youtube.com/watch?v=fV-TF4OvZpk&feature=emb_rel_pause Thinking process에 대해 잘 설명해놓은 유튜브 영상 크기가 1(인덱스 0-1)인 배열에 숫자 하나(인덱스 2) 추가되었을 때 dp가 어떻게 변하는지, 크기가 2(인덱스 0-2)인 배열에 숫자 하나(인덱스 3) 추가되었을 때 dp가 어떻게 변하는지,크기가…

  • (KOR) 포도주 시식

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2156 Solution Key Points 계단오르기 문제와 비슷해보였으나, 마지막 잔을 반드시 선택할 필요가 없었던 점에서 차이가 있었다. 풀이방법 dp[n][k] = n번째 와인잔을 골랐을 때, 그것이 k번 연속되었을 경우 마실 수 있는 최대 포도주 양. dp[n][2] 가 아닌 dp[n+1][3]으로 설정한 이유는, dp[i][1]를 구할 때 i-2를 참조해야하므로 dummy 값을 추가해준…

  • (KOR) 쉬운 계단 수

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/10844 Solution Key Points 2차원 배열을 이용한 다이나믹 프로그래밍이 핵심이였던 문제. 점화식이 바로 떠오르지 않을 경우, f(1), f(2), f(3), .. 하나씩 직접 해보면서 점화식을 도출해내는 것이 좋다. 풀이 방법 dp[n][k] = 끝자리가 k 인 n 자리 수 끝자리가 0, 9 인 경우는 예외적인 경우로 따로 핸들링해준다 int…

  • (KOR) 계단 오르기

    Problem – ⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2579 Solution Key Points 점화식을 떠올리는 과정이 핵심이였던 문제. f(0), f(1)에서 시작해서 f(n)까지 점차 규칙을 찾는 과정이 필요했다. 풀이방법 f(n, k) = n번째 계단에 오를 때 얻을 수 있는 최대 점수. 이 때, n번째 계단은 k번 연속된 계단을 오른 경우이다. g(n) = n번째 계단의 점수 f(n, 0)…