Go Gradually - Repository

2025. Maximum Number of Ways to Partition an Array - Streak 8

위 문제에서 정의된 동작을 함수 y=f(x)의 형태로 정의해보자.g(y): 특정 위치 y를 기준으로 나눴을 떄독립변수y: 바꿀 인덱스종속변수양쪽 값의 차이f(x): 특정 자리 k로 바꾸는 함수독립변수x: 바꿀 인덱스종속변수...?상수k의 값양쪽 범위이 f를 정의하기가 어렵다.f를 어떻게 정의해야 할까?이 f의 독립변수의 개수가 현재 2개라, 시간복잡도가 n^2의 형태가 되고 있다.따라서, f의 독립변수의 개수를 하나로 유지해두고 싶다. pivot을 기준으로 좌측 - 우측을 수행하고, 이 값이 0인 것들의 갯수를 "조건을 만족하는 파티션"이라고 하자.이렇게 정의해뒀을 때, 인덱스 i를 k로 바꿀때마다, 파티션 n-1개가 영향받는다.i개의 파티션이 +diff만큼 변하고, n- i - 1개의 파티션이 -dif..

1761. Minimum Degree of a Connected Trio in a Graph - Streak 7

연결된 "트리오"의 최소 차수를 구하는 문제이다. 트리오인걸 알려면, 두 정점은 거쳐봐야 안다. 이어진 두 정점 사이에 같이 알고 있는 정점은 트리오를 형성하므로, 그래프 탐색을 이용하면 찾을 수 있을 것 같다.그 전에, 이전에 방문한 노드를 아는 방법이 필요하다. dfs 로 순회한다고 할 때, 다음과 같이 지나친 정점을 표현해보자.pprevprevnownextpprev == next로 검사하면 된다. pprev가 유일하지 않을 수 있는 문제가 있나?위 그림의 경우, prev, now, next의 사이클이 잡히지 않을 수 있다.확실한건 이전에 방문한 모든 pprev를 아는 것 그렇게 따지면, prev도 유일하지 않다. 그럴거면, 모든 정점에서 각각 2번 이동 후, 서로가 있는지 확인하는게 효율적이다.시간..

1301. Number of Paths with Max Score - Streak 6

DP 로 최댓값을 유지하면 풀 수 있다. 근거: 해당 지점의 최댓값이 바뀌면, 이후는 반드시 그 최댓값 경로를 따라야 한다.따라서, 비교적 간단하게 최적 부분 구조+중복 부분문제를 만족한다. 그럼 남은 문제는, "벽 의 처리를 어떻게 할 것인가?"이다.그냥 초깃값을 매우 낮은 음수로 설정해두면 된다.1만 * 9 = 최대 값 9만이니, 기본 값 초기화를 전부 -10억으로 해두면 벽을 뛰어넘는 값으로 잘못된 값을 리턴하기 어려워진다.class Solution { public int[] pathsWithMaxScore(List board) { int n = board.size(); List> dp = new ArrayList(); for(int i = 0; i tem..

이 문제는 결국 양수와 음수의 조합으로 나타내진다.이를 모듈러 연산으로 나타낼 수 없을까? 여기서 확장 유클리드 호제법이 적용 가능해진다.gcd = 1인 조합이 하나라도 있으면 True이다.근데 우리 문제는, 다음과 같은 형태이다.이걸 확장 유클리드 호제법의 형태로 바꿀 수 없을까?둘을 더하면, 최대공약수는 약수로 남기고, 나머지는 더한 효과가 된다.즉, 둘을 더해도 최대공약수는 무조건 남는다 최대공약수는 이 문제에서 지워야 하는 대상이므로,전체의 최대공약수가 1이면 True이고, 전체의 최대공약수가 1이 아니면 False이다.class Solution { public boolean isGoodArray(int[] nums) { int now = nums[0]; for(in..

비슷한 문제를 풀어본 적이 있다.https://www.acmicpc.net/problem/11066 이 문제와 다른 것은 뭘까?파일 합치기는 반드시 바로 옆칸 1개와 합치기 때문에, 순차대로 순회하기가 쉽다.이 문제는 연속된 k칸끼리 합쳐야 하기 때문에, 추가적인 처리가 필요하다.n%(k-1)==1 이 아니면 -1을 반환해야 한다.연속된 k칸끼리의 합치는 방법을 생각해야 한다.파일 합치기의 경우DP[i][j] = DP[i][k] + DP[k+1][j] + psum[j] - psum[i-1]이 문제는?연속된 k칸을 합쳐야 한다. 점화식 자체가 달라지는건가?dp[i][p] + dp[p][q] + ...k가 커지면 for문의 깊이도 그만큼 커진다.k가 2인 경우를 제외하고,내부가 len % (k-1) == 1..

내 풀이 접근현재 인덱스까지 구할 수 있는 최대 수익을 계산하려면이전 인덱스에 담겨 있는 최대 수익과, 그 인덱스부터 지금까지의 1회 최대 수익을 알고 있어야 한다.이는 카데인 알고리즘과 굉장히 유사하다고 판단했다. 따라서 DP를 이용해 현재 인덱스까지 가장 최적의 이익을 찾도록 했다.class Solution { public int maxProfit(int k, int[] prices) { int[][] dp = new int[prices.length + 1][k+1]; int ret = 0; for(int kk = 1; kk이래도 통과는 한다.하지만, 조건이 빡빡하다면 통과하지 못했을 것이다.좀 더 효율적인 해이전에 구할 수 있는 최대 이익을, 0~i까지 전..