-
2019 제2회 숭고한 운영 후기
고등학교 때부터 뭔가 일이 끝나면 후기를 남기는 걸 참 좋아했었는데, 요즘에는 왠지 모르게 후기를 남기고 싶지가 않더라구요. 사실 숭고한도 후기를 남길 생각은 없었는데 여러가지로 마음이 바뀌었습니다. 항상 해오던 그런 비슷한 일인데, 왜 이번에는 끝이 아쉽고 공허한지 모르겠어요. 짧다면 짧고 길다면 긴 시간에 함께 고생한 운영진들도 이제 자주 볼 일이 없다고 생각하니 섭섭하고 마음이 별로 좋지 않네요. 그래서 지금 이 마음이 흩어지기 전에 글로나마 몇 자 남기려고 합니다. 숭고한이 무엇인가 세 학교의 네 알고리즘 동아리(숭실대 SCCC,...
-
[잡담] 제3회 천하제일 코딩대회 예선 문제 풀이
대회 정보: https://www.acmicpc.net/contest/view/303 문제 목록: 추가 예정 출제 및 검수 : jh05013, junie, messi, wookje 문제 A B C D E 출제자 wookje junie jh05013 jh05013 wookje A. 엔드게임 스포일러 풀이 0000 : 엔드게임 스포일러 문제 지문 내에 정답의 영문 표기가 적혀 있으므로 출력하면 된다. 코드 #include <cstdio> int main(){ puts("Avengers: Endgame"); return 0; } B. 귀여운 수~ε٩(๑> ₃ <)۶з 풀이 0000 : 귀여운 수~ε٩(๑> ₃ <)۶з 주어진 정수의 각 자릿수가 등차수열을 이루는지 판별하면 된다....
-
[BOJ] 9240 : 로버트 후드
9240 : 로버트 후드 풀이 로테이팅 캘리퍼스 코드 #include<cstdio> #include<algorithm> #include<tuple> #include<vector> #include<cmath> using namespace std; typedef long long ll; typedef pair<int,int> pii; struct POINT{ int x, y; bool operator <(POINT a)const { return x == a.x ? y < a.y : x < a.x; } POINT operator -(POINT a)const { return { x-a.x,y-a.y }; } }; int N; ll sq(int x){ return (ll)x*x; } ll dst(POINT A, POINT B) { return sq(A.x-B.x)+sq(A.y-B.y); } int...
-
[BOJ] 1062 : 가르침
1062 : 가르침 풀이 그냥 완전탐색하면 된다 근데 그냥 하면 시간 초과가 난다 앞뒤에 anta tica를 제거하고 잘 돌려야 한다 코드 #include <bits/stdc++.h> using namespace std; int n, k, dap, a[55]; char s[55]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { scanf("%s", s); for (int j = 0; s[j]; j++) a[i] |= (1<<(s[j]-'a')); } int x = (1<<0)|(1<<2)|(1<<8)|(1<<13)|(1<<19); for (int i = x; i < (1<<26);...
-
[BOJ] 2162 : 선분 그룹
2162 : 선분 그룹 풀이 선분이 교차하면 묶어주면 된다 코드 #include <bits/stdc++.h> #define fst first #define snd second using namespace std; typedef pair<int, int> pi; int n, par[3003], cnt[3003]; pi p[6003]; int ccw(pi a, pi b, pi c) { int r = a.fst*b.snd + b.fst*c.snd + c.fst*a.snd; r -= a.snd*b.fst + b.snd*c.fst + c.snd*a.fst; if (r > 0) return 1; if (r < 0) return -1; return 0; } int iscross(pi a, pi b, pi...
-
[BOJ] 2152 : 여행 계획 세우기
2152 : 여행 계획 세우기 풀이 주어진 그래프에서 scc를 구해서, 각 컴포넌트를 노드로 하는 새로운 그래프를 만들자 scc로 구성된 그래프는 항상 DAG이다 여기서 위상정렬 같은 느낌으로 dp? 같은 느낌으로 으쌰으쌰 하자 타잔으로 scc를 구하면 위상정렬의 역순으로 컴포넌트를 구하게 된다 아몰랑 코드 #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; const int MAXN = 1e4 + 10; int n, m, s, e; int cnt, pos, scc[MAXN], chk[MAXN], stk[MAXN]; vi gph[MAXN]; vector<vi> res; int dfs(int now) {...
-
[잡담] 내가 알고리즘을 공부하는 방법
요즘 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--; }...