파파비의 블로그

여기서 포인트는, 언제 새로 연속을 끊어야 하는가? 이다. 음수 값이 나온다고 무조건 끊고 다시 생각해야하게 아니다. 예제 2번을 보면 -4 > 3 > 4 이다. 저 3개의 합은 +3으로, -4가 나오더라도. 연속 수에서 count를 끊고, 다시 새는 순간은 여태 누적합이 음수가 되는 순간이다. 그래서 난 이 문제를 풀 때, 누적합과 dp 배열을 각각 만들어서 dp[i]의 값은 sum[i]와 dp[i-1] 중 비교를 통해 선택했다. (Data)10 -4 3 1 5 6 -35 12 21 -1 (Sum)10 6 9 10 15 21 -14 12 33 32 (DP)10 10 10 10 15 21 21 21 33 33 dp[i]의 값은 i까지 연속합중 최고의 값을 말한다. 저기 표 가운데를 보면, 음수일 때는 그..

LCS -> 최장 공통 부분 수열/문자열 이라고 한다. 약간의 차이는 있으나 사실상 원리는 같다. www.youtube.com/watch?v=P-mMvhfJhu8&feature=youtu.be 해결하는 알고리즘이다. DP를 활용한 방식으로, 이중배열로 해결하게 되며, 원리는 2개의 문자열을, 각각 부분문자열을 만들어서, 동시에 하나씩 char를 추가하면서, 이전 값(부분문자열에 대한 LCS)을 비교하면서 구해나가는 방식이다. 예를 들어, ASDASD 라는 문자열과 ABDABD 라는 문자열의 LCS를 구해본다면, 1) 맨 처음 A와 A를 비교 (제일 작은 부분문자열) >> 값은 1 2) AS와 A & AB와 A를 비교 >> 똑같이 1(하지만 값이 달라질 수 있음) >> 그래서 AS AB의 값은 더 둘 중 ..

Sort는 보통 가장 빠른게 nlogn 이라는 것은 들어봤을 것이다. 그러나 특정 조건에 한해서는 더 줄여질 수 있는데, Count Sort를 활용하면 n으로 줄일 수 있다. Count Sort에서 조건이라면, data의 범위가 될 것이다. Count Sort에 대해 자세히 알아보려면 아래 동영상을 참고하면 된다. www.youtube.com/watch?v=7zuGmKfUt7s 먼저 해당 data가 가능한 범위의 크기 만큼 array를 만들고, 한번 쭉 data를 훑으면서, 어떤 값이 나오면 그 값을 index로 보고 list[index]의 값을 +1 해준다. 이렇게 되면 어떤 값이 몇번 나왔는지 알게되고 나중에 리스트를 처음부터 훑으면서 순서대로 다시 쭉 써주면 된다. n + 데이터의 범위가 time ..