-
[잡담] 내가 알고리즘을 공부하는 방법
요즘 ps 공부하는 방법 포스팅하는 게 유행인 것 같더라구요. 그래서 저도 빠르게 탑승합니다 하하하하하하 관련글 subinium: PS를 공부하는 방법 (How to study Problem Solving?) koosaga: 내가 문제풀이를 연습하는 방법 baactree: 알고리즘 공부, 어떻게 해아하나요? 들어가기 전에 제가 이 포스팅에서 다룰 내용은 Problem Solving(이하 PS)을 공부하는 방법이며, 나아가서는 Competitive Programming(이하 CP) 즉 경시 대회를 공부하는 방법이고, 정확하게는 욱제가 대회를 준비하는 방법에 대해 다룹니다. 이 글이 코딩테스트에 도움이 되는가? 하면 잘 모르겠습니다. 코딩테스트는 literally 코딩 능력을 평가하는...
-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...
-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...
-
[BOJ] 2812 : 크게 만들기
2812 : 크게 만들기 풀이 토막 나며 부서진 나의 여러 기대는 공중에 날려 사라져가고 딱딱한 구름 밑에서 벅찬 무게를 견디며 혼자 그렇게 작아져 갔다 코드 #include <cstdio> int n, k, pos; char s[500005]; int main() { scanf("%d %d %c", &n, &k, &s[0]); pos = 1; for (int i = 1; i < n; i++) { scanf("%c", &s[pos]); while (k && pos && s[pos-1] < s[pos]) { s[pos-1] = s[pos]; s[pos] = 0; k--; pos--; }...
-
[BOJ] 1541 : 잃어버린 괄호
1541 : 잃어버린 괄호 풀이 아무도 얘기하지 않는 몇 해가 쉽게 지나 버리고 휑하니 텅 빈 가슴속으로 눈꽃 송이 내려앉는다 아무리 잠들어도 캄캄한 바람 지날 뿐 어떤 꿈도 만나지 못해 코드 #include <cstdio> int sum, tmp, f, n; char s[55] = {1}; int main() { scanf("%s", s+1); for (int i = 1; s[i-1]; i++) { if ('0' <= s[i] && s[i] <= '9') { n *= 10; n += s[i] - '0'; } else if...
-
[BOJ] 1138 : 한 줄로 서기
1138 : 한 줄로 서기 풀이 사람 마음이 참 생각처럼 되질 않아 쓴웃음에 한 번 더 미련을 삼켜 보곤 해 미워하고 싶은데 그것조차 잘 안 돼 너의 기억은 너무나 찬란해 잠 못 들게 해 코드 #include <cstdio> #include <vector> using namespace std; int n, x, a[12]; vector<int> v; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } v.push_back(n); for (int i = n-1; i >= 1;...
-
[BOJ] 2294 : 동전 2
2294 : 동전 2 풀이 가져가 지독한 그리움 기억 속 널 다시 데러가 난 아무렇지 않은 척 애를 써도 또다시 울컥하고 말아 아직도 난 코드 #include <cstdio> int n, k, t, d[100001]; int main() { scanf("%d %d", &n, &k); for (int i = 1; i <= k; i++) { d[i] = 1e9; } for (int i = 1; i <= n; i++) { scanf("%d", &t); for (int j = t; j <= k; j++) {...
-
[BOJ] 2133 : 타일 채우기
2133 : 타일 채우기 풀이 둠두둠칫 코드 #include <cstdio> int main() { int n, d[31] = { 1,0,3 }; scanf("%d", &n); for (int i = 4; i <= n; i += 2) { d[i] = d[i - 2] * 3; for (int j = 4; j <= i; j += 2) d[i] += d[i - j] * 2; } printf("%d", d[n]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++,...
-
[BOJ] 1149 : RGB거리
1149 : RGB거리 풀이 d[i][0] = max(d[i-1][1], d[i-1][2]) d[i][1] = max(d[i-1][0], d[i-1][2]) d[i][2] = max(d[i-1][0], d[i-1][1]) 코드 #include <bits/stdc++.h> using namespace std; int N, r, g, b, R, G, B; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d %d %d", &r, &g, &b); r += min(G, B); g += min(R, B); b += min(R, G); R = r; G = g; B = b; } printf("%d", min(min(R,...
-
[BOJ] 2156 : 포도주 시식
2156 : 포도주 시식 풀이 . 코드 int max(int a, int b) { return a > b ? a : b; } n, a, b, c, A, B, C, w; main() { for (scanf("%d", &n); n--;) { scanf("%d", &w); C = c, B = b, A = a; c = B + w; b = A + w; a = max(max(A, B), C); } printf("%d", max(max(a, b), c)); } 아무말 백준, 백준 온라인 저지, BOJ,...