Approach 문제를 잘 보면 전체적으로 이전의 결과가 이후의 결과에 계속 영향을 주는 것을 알 수 있고 해당하는 경향성을 점화식을 통해 일반화해서 나타낼 수 있음을 쉽게 파악할 수 있다. 이 지점에서 DP문제를 떠올려 주면 된다. 다만, 이 문제에서 어느 블록을 이전에 썼는지를 파악해야 경우의 수를 더할 수 있으므로 각 타일의 종류마다 따로 DP를 할당해서 점화식을 세워주면 된다. 에를 들어 dp[i][1], dp[i][2], dp[i][3]을 각각 i번째 가로에 1 x 2, 2 x 1, 2 x 2 블럭을 사용했을 때의 경우의 수라고 하면 점화식을 다음과 같이 나타낼 수 있다. $$ dp[i][1] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]$$ $$dp[i][2]..

Approach 아래쪽으로 내려갈 때, 2가지 가능성이 존재한다. 대각선 왼쪽, 대각선 오른쪽 그런데 인덱스를 잘 생각해보면 자신이랑 같은 인덱스이거나 1개 더 작은 값이라는 것을 쉽게 파악할 수 있다. 이 점을 이용해보면, 점화식을 세울 수 있다. 추가적으로 자신보다 큰 index의 값은 필요가 없으므로 슬라이딩 윈도우 기법을 활용해서 Space complexity를 조금 더 낮출 수 있기는 하지만 생략.. dp[i][j]를 i번째 줄 j번째 index가 가지는 값의 최대값이라고 가정하자. 그러면 점화식은 다음과 같다. $$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + v \mbox{ (단, i는 줄 넘버, j는 몇번 째 수)$$ Code #include #de..

Approach Let dp[i] : Continuous maximum sum considering i'th element If dp[i - 1] value is negative, dp[i] could be maximize by throwing previous continuous sum. On the oher hand, dp[i] could be maximized by along previous continuous sum. So, Recurrence relation could be represented by $$ dp[i] \begin{cases} v[i] & \mbox{(if dp[i - 1] is negative)} \\ v[i] + dp[i - 1] & \mbox{(if dp[i - 1] is po..

접근 방법 계속해서 이전 값들을 더해나가는 경향성 자체를 몇 번 시도하다보면 쉽게 파악할 수 있다. 또한 더하는 숫자들의 기준이 반복되는 것을 통해 점화식으로 이 문제를 쉽게 해결할 수 있음을 파악할 수 있다. 이전 포스트에서도 계속 언급한 것처럼 점화식 형태로 표현되는 것들은 일반적으로 DP를 활용해서 풀어줄 수 있다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; int main(void){ fastio; ll dp[101]; dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2; dp..

접근 방법 일단, 어차피 카드 묶음이 1개씩 지워지는 상황이므로 무조건 큰 숫자가 나중에 묶이는 것이 유리하다. 그렇지 않으면 반복해서 묶이게 되어 숫자가 더 커지기 때문이다. 따라서, 숫자가 작은 것을 먼저 선택하기 위한 자료 구조가 필요하므로 우선순위 큐 자료구조를 활용해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; pq.push(temp); } int res..

접근 방법 우선순위 큐에 N만큼의 크기를 유지시키면서 pq의 최솟값을 갱신시켜주면 결과적으로 전체 세트의 N번째 최댓값을 쉽게 구할 수 있다. Priority queue 사용 느낌에 대해서 다시 한번 정리하는 용도로 정리해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; if(pq.size() < n) pq.push(..

Linear equation Linear equation은 $$\hat{y} = \theta_0 + \theta_1x_1 + \theta_2x_2+ \cdots +\theta_nx_n$$로 나타낼 수 있다. (단, $\hat{y}$는 예측값, $n$은 특성의 수, $x_i$는 i번재 특성값, $\theta_j$는 j번째 모델 파라미터) 수식이 표현된 형태를 잘 보면, 2개의 vector의 dot product형태로 표현할 수 있음을 쉽게 관찰할 수 있다. 따라서 조금 더 간단하게 해당 수식을 표현하면 다음과 같다. $$\hat{y} = h_{\theta}(x) = \theta \cdot x$$ 그런데, $\theta$와 $x$는 모두 열벡터끼리의 dot product이므로 Linear mathematic..

Linear Regression 특성이 하나인 경우 어떤 직선을 학습하는 알고리즘이다. KNN의 경우 새로운 샘플이 훈련 세트의 범위를 벗어나면 엉뚱한 값을 예측할 수 있었는데, Linear Regression의 경우 만족하는 직선을 학습하는 것이므로 해당 문제를 해결할 수 있다. 사용 방법은 다음과 같다. from sklearn.linear_model import LinearRegression # Fitting lr = LinearRegression() lr.fit(train_input, train_target) # Model evaluation target_score = lr.score(train_input, train_target) test_score = lr.score(test_input, tes..