선형 회귀 및 경사 하강법 구현
데이터 정규화 후 경사 하강법을 사용하여 가중치와 편향을 업데이트하는 문제입니다. 특징은 그래디언트 누적 시 위치를 정확히 파악하여 3 번의 연산이 이루어지도록 해야 한다는 점입니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
cout << fixed << setprecision(2);
int sample_count, iterations;
Real learning_rate;
cin >> sample_count >> iterations >> learning_rate;
const Real INF_VAL = 1E18;
vector<Real> max_vals(3, -INF_VAL), min_vals(3, INF_VAL);
vector<vector<Real>> features(sample_count, vector<Real>(4));
for (int i = 0; i < sample_count; ++i) {
for (int j = 0; j < 4; ++j) {
cin >> features[i][j];
if (j < 3) {
max_vals[j] = max(max_vals[j], features[i][j]);
min_vals[j] = min(min_vals[j], features[i][j]);
}
}
}
// 정규화 과정
for (int j = 0; j < 3; ++j) {
for (int i = 0; i < sample_count; ++i) {
if (min_vals[j] == max_vals[j]) {
features[i][j] = 0;
} else {
features[i][j] = (features[i][j] - min_vals[j]) / (max_vals[j] - min_vals[j]);
}
}
}
Real bias = 0;
vector<Real> weights(3, 0);
for (int iter = 0; iter < iterations; ++iter) {
Real grad_bias = 0;
vector<Real> grad_weights(3, 0);
for (int i = 0; i < sample_count; ++i) {
Real prediction = bias;
Real target = features[i][3];
for (int j = 0; j < 3; ++j) {
prediction += weights[j] * features[i][j];
}
Real error = prediction - target;
grad_bias += error;
for (int j = 0; j < 3; ++j) {
grad_weights[j] += error * features[i][j];
}
}
grad_bias /= sample_count;
for (int j = 0; j < 3; ++j) grad_weights[j] /= sample_count;
bias -= learning_rate * grad_bias;
for (int j = 0; j < 3; ++j) {
weights[j] -= learning_rate * grad_weights[j];
}
}
// 가중치 복원
for (int j = 0; j < 3; ++j) {
if (min_vals[j] == max_vals[j]) {
weights[j] = 0;
} else {
weights[j] /= (max_vals[j] - min_vals[j]);
bias -= weights[j] * min_vals[j];
}
}
cout << bias << " ";
for (int j = 0; j < 3; ++j) {
cout << weights[j];
if (j != 2) cout << " ";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
executeProblem();
}
return 0;
}
K-Means 클러스터링 및 경로 최적화
클러스터 중심점을 업데이트한 후 각 점까지의偏移 거리를 계산합니다. 중심점 갱신 로직과 거리 계산 순서가 중요합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
int k_clusters, n_points, move_speed;
cin >> k_clusters >> n_points >> move_speed;
k_clusters = min(k_clusters, n_points);
vector<pair<Real, Real>> points(n_points);
for (int i = 0; i < n_points; ++i) {
cin >> points[i].first >> points[i].second;
}
auto square = [](Real val) { return val * val; };
vector<int> indices(n_points);
iota(indices.begin(), indices.end(), 0);
// 원점으로부터 거리 기준 정렬
sort(indices.begin(), indices.end(), [&](int a, int b) {
Real distA = square(points[a].first) + square(points[a].second);
Real distB = square(points[b].first) + square(points[b].second);
if (distA == distB) return a < b;
return distA < distB;
});
vector<pair<Real, Real>> centroids(k_clusters);
for (int i = 0; i < k_clusters; ++i) {
centroids[i] = points[indices[i]];
}
auto calcDistSq = [&](int pIdx, int cIdx) {
return square(points[pIdx].first - centroids[cIdx].first) +
square(points[pIdx].second - centroids[cIdx].second);
};
auto calcEuclidean = [&](Real x1, Real y1, Real x2, Real y2) {
return sqrt(square(x1 - x2) + square(y1 - y2));
};
int max_iterations = 50;
Real tolerance = 1e-4;
while (max_iterations--) {
vector<int> cluster_counts(k_clusters, 0);
vector<pair<Real, Real>> new_centroids(k_clusters, {0, 0});
for (int i = 0; i < n_points; ++i) {
vector<int> c_indices(k_clusters);
iota(c_indices.begin(), c_indices.end(), 0);
sort(c_indices.begin(), c_indices.end(), [&](int a, int b) {
return calcDistSq(i, a) < calcDistSq(i, b);
});
int best_c = c_indices[0];
cluster_counts[best_c]++;
new_centroids[best_c].first += points[i].first;
new_centroids[best_c].second += points[i].second;
}
for (int i = 0; i < k_clusters; ++i) {
if (cluster_counts[i] == 0) {
new_centroids[i] = centroids[i];
} else {
new_centroids[i].first /= cluster_counts[i];
new_centroids[i].second /= cluster_counts[i];
}
}
Real shift_sum = 0;
for (int i = 0; i < k_clusters; ++i) {
shift_sum += calcEuclidean(centroids[i].first, centroids[i].second,
new_centroids[i].first, new_centroids[i].second);
}
centroids = new_centroids;
if (shift_sum < tolerance) break;
}
// 최종 중심점 정렬 및 경로 계산
vector<int> c_indices(k_clusters);
iota(c_indices.begin(), c_indices.end(), 0);
sort(c_indices.begin(), c_indices.end(), [&](int a, int b) {
Real distA = square(centroids[a].first) + square(centroids[a].second);
Real distB = square(centroids[b].first) + square(centroids[b].second);
return distA < distB;
});
Real total_dist = 0;
Real curr_x = 0, curr_y = 0;
for (int i = 0; i < k_clusters; ++i) {
int idx = c_indices[i];
total_dist += calcEuclidean(curr_x, curr_y, centroids[idx].first, centroids[idx].second);
curr_x = centroids[idx].first;
curr_y = centroids[idx].second;
}
total_dist += calcEuclidean(curr_x, curr_y, 0, 0);
total_dist = total_dist / move_speed * 3600;
cout << (int)total_dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
executeProblem();
}
return 0;
}
접두사 합을 활용한 분류 정확도 계산
구간을 나누어 각 구간의 라벨 일치 여부를 확인합니다. 접두사 합 배열을 사용하여 효율적으로 카운트합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
int m;
cin >> m;
vector<array<int, 2>> data(m);
for (int i = 0; i < m; ++i) {
cin >> data[i][0] >> data[i][1];
}
sort(data.begin(), data.end());
int target_l, target_r;
cin >> target_l >> target_r;
cout << fixed << setprecision(3);
vector<array<int, 2>> prefix_counts(m);
for (int i = 0; i < m; ++i) {
if (i > 0) prefix_counts[i] = prefix_counts[i - 1];
prefix_counts[i][data[i][1]]++;
}
auto countInRange = [&](int left, int right, int label) {
if (left > right) return 0;
int val = prefix_counts[right][label];
if (left > 0) val -= prefix_counts[left - 1][label];
return val;
};
int max_correct = 0;
for (int split = 0; split <= m; ++split) {
int current = countInRange(0, split - 1, target_l) +
countInRange(split, m - 1, target_r);
max_correct = max(max_correct, current);
}
cout << 1.0 * max_correct / m << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
executeProblem();
}
return 0;
}
확률 기반 동적 계획법
상태 전이 확률을 기반으로 DP 를 수행합니다. 특정 상태에 도달하지 않도록 제외하면서 확률 분포를 업데이트합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
int n_states;
cin >> n_states;
int start_node, trap_node, steps;
cin >> start_node >> trap_node >> steps;
start_node--;
trap_node--;
vector<vector<Real>> trans_prob(n_states, vector<Real>(n_states));
for (int i = 0; i < n_states; ++i) {
for (int j = 0; j < n_states; ++j) {
cin >> trans_prob[i][j];
}
}
vector<Real> current_dist(n_states, 0);
current_dist[start_node] = 1;
for (int k = 0; k < steps; ++k) {
vector<Real> next_dist(n_states, 0);
for (int i = 0; i < n_states; ++i) {
if (i == trap_node) continue;
for (int j = 0; j < n_states; ++j) {
if (j == trap_node) continue;
next_dist[j] += current_dist[i] * trans_prob[i][j];
}
}
swap(next_dist, current_dist);
}
Real total_prob = 0;
for (int i = 0; i < n_states; ++i) total_prob += current_dist[i];
cout << fixed << setprecision(6) << total_prob << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
executeProblem();
}
return 0;
}
이분 탐색을 이용한 작업 스케줄링
NP-hard 문제이므로 최적해 대신 이분 탐색을 통해 가능한 최소 최대값을 찾습니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
int n_workers, m_tasks;
cin >> n_workers >> m_tasks;
vector<int> task_loads(m_tasks);
for (int i = 0; i < m_tasks; ++i) {
cin >> task_loads[i];
}
auto is_possible = [&](int max_load) {
int current_sum = 0;
int workers_needed = 1;
for (int i = 0; i < m_tasks; ++i) {
if (current_sum + task_loads[i] <= max_load) {
current_sum += task_loads[i];
} else {
current_sum = task_loads[i];
workers_needed++;
}
}
return workers_needed <= n_workers;
};
int left = 1, right = 1e9;
while (left < right) {
int mid = (left + right) >> 1;
if (is_possible(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
cout << right << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
executeProblem();
}
return 0;
}
트랜스포머 셀프 어텐션 메커니즘
Q, K, V 행렬 생성 및 어텐션 스코어 계산 과정을 구현합니다. 소프트맥스 적용 후 가중치 합을 구합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
cout << fixed << setprecision(2);
int seq_len, dim;
char sep;
cin >> seq_len >> sep >> dim;
auto parseMatrix = [&](vector<vector<Real>> &mat, int rows, int cols) {
mat.assign(rows, vector<Real>(cols));
string line;
while (true) {
getline(cin, line);
if (!line.empty()) break;
}
string cleaned;
for (char c : line) {
if (c == ',') cleaned += ' ';
else cleaned += c;
}
stringstream ss(cleaned);
double val;
int r = 0, c = 0;
while (ss >> val) {
mat[r][c++] = val;
if (c == cols) { r++; c = 0; }
}
};
vector<vector<Real>> input_data;
parseMatrix(input_data, seq_len, dim);
vector<vector<Real>> Wq1, Wk1, Wv1;
parseMatrix(Wq1, dim, dim);
parseMatrix(Wk1, dim, dim);
parseMatrix(Wv1, dim, dim);
vector<vector<Real>> Wfc1, Bfc1;
parseMatrix(Wfc1, dim, dim);
parseMatrix(Bfc1, dim, 1);
vector<vector<Real>> Wq2, Wk2, Wv2;
parseMatrix(Wq2, dim, dim);
parseMatrix(Wk2, dim, dim);
parseMatrix(Wv2, dim, dim);
vector<vector<Real>> Wfc2, Bfc2;
parseMatrix(Wfc2, dim, dim);
parseMatrix(Bfc2, dim, 1);
auto multiply = [&](const vector<vector<Real>> &A, const vector<vector<Real>> &B) {
int n = A.size(), m = B[0].size(), k = A[0].size();
vector<vector<Real>> C(n, vector<Real>(m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int t = 0; t < k; ++t) {
C[i][j] += A[i][t] * B[t][j];
}
}
}
return C;
};
auto attention = [&](const vector<vector<Real>> &X,
const vector<vector<Real>> &Wq,
const vector<vector<Real>> &Wk,
const vector<vector<Real>> &Wv) {
auto Q = multiply(X, Wq);
auto K = multiply(X, Wk);
auto V = multiply(X, Wv);
Real scale = sqrt((Real)dim);
vector<vector<Real>> scores(seq_len, vector<Real>(seq_len, 0));
for (int i = 0; i < seq_len; ++i) {
for (int j = 0; j < seq_len; ++j) {
for (int k = 0; k < dim; ++k) {
scores[i][j] += Q[i][k] * K[j][k];
}
scores[i][j] /= scale;
}
}
for (int i = 0; i < seq_len; ++i) {
Real max_val = *max_element(scores[i].begin(), scores[i].end());
Real sum_exp = 0;
for (int j = 0; j < seq_len; ++j) {
scores[i][j] = exp(scores[i][j] - max_val);
sum_exp += scores[i][j];
}
for (int j = 0; j < seq_len; ++j) {
scores[i][j] /= sum_exp;
}
}
return multiply(scores, V);
};
auto h1 = attention(input_data, Wq1, Wk1, Wv1);
auto out1 = multiply(h1, Wfc1);
for (int i = 0; i < seq_len; ++i) {
for (int j = 0; j < dim; ++j) {
out1[i][j] += Bfc1[j][0];
}
}
auto h2 = attention(out1, Wq2, Wk2, Wv2);
auto out2 = multiply(h2, Wfc2);
for (int i = 0; i < seq_len; ++i) {
for (int j = 0; j < dim; ++j) {
out2[i][j] += Bfc2[j][0];
}
}
for (int i = 0; i < seq_len; ++i) {
for (int j = 0; j < dim; ++j) {
cout << out2[i][j];
if (!(i == seq_len - 1 && j == dim - 1)) cout << ",";
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
executeProblem();
}
return 0;
}
Adam 옵티마이저 시뮬레이션
모멘텀 및 분산 보정을 포함한 Adam 알고리즘의 업데이트 과정을 단계별로 구현합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
int n;
cin >> n;
vector<Real> feat1(n + 1), feat2(n + 1), target(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> feat1[i] >> feat2[i] >> target[i];
}
vector<vector<Real>> params(n + 1, vector<Real>(3));
vector<vector<Real>> grads(n + 1, vector<Real>(3));
vector<vector<Real>> m_vec(n + 1, vector<Real>(3));
vector<vector<Real>> v_vec(n + 1, vector<Real>(3));
Real beta1 = 0.9, beta2 = 0.999, lambda_reg = 0.01, alpha = 0.001, eps = 1e-8;
Real B1 = 1, B2 = 1;
for (int i = 1; i <= n; ++i) {
Real pred = params[i - 1][0] * feat1[i] + params[i - 1][1] * feat2[i] + params[i - 1][2];
Real err = pred - target[i];
grads[i][0] = 2.0 * err * feat1[i];
grads[i][1] = 2.0 * err * feat2[i];
grads[i][2] = 2.0 * err;
for (int j = 0; j < 3; ++j) {
m_vec[i][j] = beta1 * m_vec[i - 1][j] + (1 - beta1) * grads[i][j];
v_vec[i][j] = beta2 * v_vec[i - 1][j] + (1 - beta2) * grads[i][j] * grads[i][j];
}
B1 *= beta1;
B2 *= beta2;
vector<Real> m_hat(3), v_hat(3);
for (int j = 0; j < 3; ++j) {
m_hat[j] = m_vec[i][j] / (1 - B1);
v_hat[j] = v_vec[i][j] / (1 - B2);
}
for (int j = 0; j < 3; ++j) {
params[i][j] = params[i - 1][j] - alpha * (m_hat[j] / (sqrt(v_hat[j] + eps)) + lambda_reg * params[i - 1][j]);
}
}
cout << fixed << setprecision(6);
for (int j = 0; j < 3; ++j) {
cout << params[n][j];
if (j != 2) cout << " ";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
executeProblem();
}
return 0;
}
DAG 위상 정렬 및 최장 경로
방향성 비순환 그래프에서 위상 정렬을 수행하며 동적 계획법으로 최장 경로를 계산합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
string input_line;
while (true) {
getline(cin, input_line);
if (!input_line.empty()) break;
}
string cleaned;
for (char c : input_line) {
if (c == ',') cleaned += ' ';
else cleaned += c;
}
stringstream ss(cleaned);
int val;
vector<int> rank_vals;
while (ss >> val) {
rank_vals.push_back(val);
}
int n = rank_vals.size();
vector<int> in_degree(n, 0);
vector<vector<int>> graph(n);
for (int i = 0; i < n - 1; ++i) {
if (rank_vals[i] <= 0) continue;
if (rank_vals[i] < rank_vals[i + 1] && rank_vals[i + 1] > 0) {
graph[i].push_back(i + 1);
in_degree[i + 1]++;
} else if (rank_vals[i] > rank_vals[i + 1] && rank_vals[i + 1] > 0) {
graph[i + 1].push_back(i);
in_degree[i]++;
}
}
queue<int> q;
vector<int> dp_len(n, 0);
for (int i = 0; i < n; ++i) {
if (in_degree[i] == 0) {
q.push(i);
dp_len[i] = 1;
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
dp_len[v] = max(dp_len[v], dp_len[u] + 1);
if (--in_degree[v] == 0) {
q.push(v);
}
}
}
int total_len = 0;
for (int i = 0; i < n; ++i) {
if (rank_vals[i] > 0) total_len += dp_len[i];
}
cout << total_len << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
executeProblem();
}
return 0;
}