티스토리

woojin042의 블로그

검색하기

블로그 홈

woojin042의 블로그

woojin029.tistory.com/m

Road to Grandmaster

구독자: 6

방명록 방문하기

주요 글 목록

내가 쓰는 코드 스니펫 { "CT" : { "prefix": "ct", "body": [ "#include", "using namespace std;", "", "int main(){", " ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);", " return 0;", "}" ], }, "CP": { "prefix": "cp", "body": [ "#include", "#include ", "#include ", "using namespace std;", "using namespace __gnu_pbds;", "template", .. 공감수 2 댓글수 0 2025. 3. 29.
Codeforces Round 1011 (Div. 2) 셋: https://codeforces.com/contest/2085A. Serval and String Theory$k=0$인 경우, $s$가 universal이기 위해서는 처음부터 original $s$가 한 종류의 문자로만 이루어져 있을 경우, 답은 항상 불가능이다.그 외의 경우 항상 $s$를 universal하게 만들 수 있다. 양 끝 문자가 다르다면 그 둘을 swap하면 되고, 양 끝 문자가 같으면 다른 곳에서 문자를 하나 가져와 양 끝 문자 중 적절한 것과 swap하면 되기 때문이다.int n, k;string str;cin>>n>>k>>str;string rev = str;reverse(all(rev));if(rev > str || str[0]!=str[n-1] && k>0){ cout.. 공감수 0 댓글수 0 2025. 3. 23.
USACO 2019 December Contest > Gold 시험도 끝났겠다 오랜만에 유사코 연습을 돌렸다.어려운 문제를 푸는 연습을 해야 할 것 같아서 셋은 골드 셋으로 골랐다. 내년에도 ICPC를 광탈하지 않기 위해서는 골~플랜디를 더 빡세게 할 필요가 있을 것 같다. 중간에 HLD 템플릿 만든 시간을 빼면 두 시간 정도 걸려서 풀었다. 확실히 유사코는 순수 애드혹/그리디의 비중은 낮고 여러 가지 자료구조와 알고리즘을 사용하는 문제가 많이 출제되는 것 같다. 18262: Milk Pumping (G1, dijkstra) 방향 그래프가 주어지고, 1번 정점에서 시작해 $n$번 정점에서 끝나는 경로 중 (경로의 유량) / (경로의 가중치 합)의 최댓값을 찾는 문제이다. 고정된 $k$에 대해 유량이 $k$ 이상이 되도록 최단 경로를 구성하려면 유량이 $k$ 이상인 .. 공감수 1 댓글수 0 2024. 10. 31.
[BOJ] 3090번 - 차이를 최소로 https://www.acmicpc.net/problem/3090 그리디 + 파라메트릭 서치를 사용하는 문제이다.문제를 풀고 블로그 풀이들을 보는데 내가 푼 방법이랑 많이 달랐고, 하나같이 이걸 어떻게 생각함(...) 식의 풀이여서 글을 쓰게 되었다.(시험 기간에 공부하기 싫어서 쓴 것도 있다.) 우선 보자마자 파라메트릭 서치를 쓰면 좋을 것 같다는 생각이 들었다.인접한 원소 간 차이의 최댓값을 한 번에 최소화하는 것보다, 인접한 원소 간 차이가 어떤 $d$ 이하가 되도록 연산을 수행할 수 있는지 판별하는 게 더 쉬워 보였기 때문이다. 여기서 한 가지 관찰을 할 수 있는데, 배열 $A$의 최소 원소를 $m$이라 두면, 연산을 최적으로 수행하고 얻은 결과 배열의 모든 원소는 $m$보다 크거나 같다.이는 .. 공감수 8 댓글수 0 2024. 10. 19.
USACO March 2014 Contest > Silver 딱히 재미도 감동도 없는 셋이였다... 10021: Watering the Fields (G3, mst) MST 기본 문제이다. 필요한 간선만 만들어서 mst로 슥삭해주면 된다. 10022: The Lazy Cow (G4, 누적 합) 그나마 재밌었던 문제이다. 어떤 시작점으로부터 맨해튼 거리가 $K$ 이하인 점들의 값 합을 최대화하는 문제인데 제한이 작아서 브루트포스를 돌리면 된다. 맨해튼 거리의 contour는 다이아몬드 모양으로 구현이 불편하기 때문에, 45도 돌려서 체비쇼프 거리 꼴로 변환하여 2차원 정사각형 누적합의 최대를 구해주면 된다. 거리 변환 시 빈 공간이 생기는데, 시작점이 빈 공간이 되지 않도록 잘 확인해줘야 한다. 10023: Mooo Mooo (G4, DP) 문제를 잘 변형하면.. 공감수 1 댓글수 0 2024. 9. 21.
USACO November 2011 Contest > Gold 골드 셋도 맛보고 싶어서 도전해봤다. 옛날 대회라 그런가 든든국밥 문제들만 나와서 비교적으로 쉽게 풀 수 있었던 것 같다. 5922: Above the Median (P4, Segment Tree) 젠장 또 median이야!고정된 값 $X$에 대해 주어진 수열의 contiguous subsequence 중 median이 $X$ 이상인 것들의 개수를 구하는 문제이다. $X$보다 크거나 같은 $a_i$를 $1$로 치환하고 $X$보다 작은 $a_i$를 $-1$로 치환하면, 놀랍게도 합이 0 이상이 되는 연속 부분 배열의 개수를 구하는 문제가 된다! 연습 중에는 merge sort tree로 누적 합을 관리하는 방법을 사용했는데 $(N\log^{2}{N})$, 그냥 누적합 배열에서 inversion count.. 공감수 1 댓글수 0 2024. 9. 18.
USACO 2018 US Open Contest > Silver [공지]https://www.acmicpc.net/group/21869USACO 셋을 밀려고 하는데, 혼자 하긴 적적해서 그룹을 만들었어요!매주 수/금/일 오후에 그룹 내 연습으로 silver~gold 수준의 셋 한 개를 돌아볼 예정입니다.(제 개인 사정으로 몇 번 건너뛸 수도..😢)열심히 하실 분 / 찍먹 하실 분 / 관전만 하실 분들 모두 환영입니다..! 오늘은 2018년 US Open (왜 거창하게 us-open이지..?) silver 셋을 돌렸다. 원래 9시 즈음에 시작하려 했으나 치킨이 일찍 오는 바람에 두 시간 늦춰서 문제를 풀었다 ㅎ시간 안에 올솔했고 재밌는 셋이였던 것 같다! 15760: Out of Sorts (G1, 정렬, 좌표 압축) 버블 정렬을 배열의 전체 범위에서 수행하는데.. 공감수 1 댓글수 0 2024. 9. 14.
USACO 2023 February Contest > Silver https://www.acmicpc.net/group/21869요즘 그룹을 만들어서 시간을 재고 USACO 셋을 밀고 있다. (가입 신청 환영!!)첫 연습셋으로 2023 February Contest의 Silver 셋을 돌렸다. 아직 부족한 게 많은 것 같다. ㅠ 27846: Bakery (P4, 수학, 이분 탐색) 대충 이분 탐색을 돌리면 되겠다는 생각만 가지고 있었는데, 어떻게 이분 탐색을 돌릴 지 몰라 못 풀었다. 삼분 탐색, 2차원 이분 탐색(...) 등 여러 뻘짓을 했다. 쿠키와 머핀을 굽는 데 필요한 시간의 합을 기준으로 이분 탐색을 돌리면, 놀랍게도 부등식이 잘 풀려서 $O(n)$에 판별 가능한 꼴이 된다! 따라서 시간복잡도 $O(N\log{M})$에 문제를 풀 수 있다. ($M$: $t_.. 공감수 1 댓글수 0 2024. 9. 12.
2024-05-21 PS 공부 시험 기간에 기분 전환할 겸 랜디를 돌렸습니다!코드포스 스타일의 문제를 조금 연습하고 싶어서 그리디, 수학, 애드 혹, 구성적, 조합론, 정수론 문제 중 S2 ~ G3인 문제들을 골라 풀었습니다.27467: 수학 퀴즈 (S1, 수학, 05:23)방정식 $x^3 = 1$의 허근 $\omega$의 성질을 잘 활용하면 되는 문제이다. 24956: 나는 정말 휘파람을 못 불어 (G4, 조합론, 10:27)H를 기준으로 앞에 있는 W의 개수와 뒤에 있는 E의 개수를 적절히 세어 주면 된다.H 앞에 W가 W[i]개만큼 있고, 뒤에 E가 E[i]개만큼 있으면, 만들 수 있는 유사 휘파람 문자열의 수는 $W[i] \cdot (2^{E[i]}-E[i]-1)$ 개이다.W[i]와 E[i]를 누적합 비슷한 dp로 처리해주고.. 공감수 1 댓글수 0 2024. 5. 21.
2024-03-19 PS 공부 두달만에 다시 글을 쓰네요! 대학에 입학하고 나니 개인적인 공부를 할 시간이 많아져 확실히 좋은 것 같습니다 ㅎㅎ 고등학교 시절엔 "지금 공부 안 하면 큰일난다!!"는 마인드로 공부했었던 것 같은데, 지금은... 뭐 하면 좋고 안 해도 그만이고 ㅋㅋㅋㅋㅋㅋ 고등학교 친구들 공부하는거 보면 그동안 어떻게 버텨왔던건지 참 신기하네요 아무튼간에, 교내 알고리즘 동아리에서 매주 세미나를 진행하는데, 연습문제를 모두 풀면 동아리비를 환급해준다는 말을 듣고(!!) 이번 주차 연습문제를 한번 풀어보았습니다. 25545: MMST (G2, MST) 최소/최대 스패닝 트리가 아닌 아무 스패닝 트리만 구해 출력하는 문제이다. 주어진 그래프에 사이클이 존재한다면 ($V\leq E$) 서로 다른 스패닝 트리가 적어도 3개 존.. 공감수 2 댓글수 1 2024. 3. 19.
2024-01-21 PS 공부 한달만에 돌아왔네요! ㅠㅠ 사실 PS에 대한 흥미가 좀 떨어졌었는데, 입학하기 전까지 민트는 찍어야지(...) 하는 생각에 다시 문제를 풀게 되었습니다. 개인적으로 그리디를 어렵게 느끼고 있던 참이라서, 이번엔 백준 그리디 연습 문제집에 있는 문제들을 낮은 티어부터 쭉 돌아보았습니다. 11000: 강의실 배정(G5) 사용하는 최소 강의실의 개수는, 가장 많은 강의가 겹치는 시점에서의 강의 개수와 같다. 따라서 정렬을 통해 답을 O(NlogN)에 구할 수 있다. 2831: 댄스 파티(G4) 양수 남자 - 음수 여자, 혹은 음수 남자 - 양수 여자끼리만 짝지어 주어야 한다. 양수 남자와 음수 여자가 짝짓는 경우만을 생각해보자. 우선 키가 작은 순서대로 남자를 선택하면 최적해를 얻을 수 있다는 건 쉽게 알 수.. 공감수 1 댓글수 2 2024. 1. 21.
2023-12-13 PS 공부 오랜만에 업다운랜디를 돌렸다. 21276: 계보 복원가 호석(G2, Tree) 시간 안엔 못 풀었다.. 자신의 조상 노드가 문제에서 주어지므로, 맵(map)에 자신의 조상 노드를 모두 담고, 조상 노드를 순회하면서 set의 크기가 자신보다 1 작은 것이 있으면 해당 노드가 자신의 부모 노드가 된다. 부모 노드가 없다면 루트 노드가 되고, 가문의 개수는 루트 노드의 개수와 같다. 이를 이용해 시간복잡도 O(N^2logN)에 계산할 수 있다. 별해) 입력받을 때, 자신보다 깊이가 깊은 노드들에 대해 위에서 아래로 가는 단방향 간선을 만들어준다. 이후 위상 정렬을 수행하면 역시 시간복잡도 O(N^2logN)에 해결할 수 있다! 2492: 보석(G3, Brute-Force) 풀이가 전혀 떠오르지 않아서 그냥 답.. 공감수 0 댓글수 0 2023. 12. 13.
2023-12-06 PS 공부 이번에도 어김없이 업다운랜디를 돌렸습니다. 학교에서 할 게 없어서 하루종일 문제만 풀고 있네요 ㅋㅋㅋ 12784: 인하니카 공화국(G3, Tree, 16:00) dp[i]를 i번을 루트로 하는 트리에서 필요한 최소 다이너마이트의 개수로 잡고 트리 dp를 돌릴 수 있다. 사실 재사용되는 값이 없어서 메모이제이션은 필요하지 않다! 오랜만에 트리DP를 짜봐서 구현이슈가 좀 있었다... 11967: 불켜기(G2, BFS) 시간 초과... 새로운 방에 불을 킬 때마다 그 방의 상하좌우를 탐색해서, 이미 방문한 지점이 있다면 새로운 방을 큐에 넣어준다. 예전에 재채점으로 틀렸던 문젠데 드디어 풀었다 ㅎㅎ 15711: 환상의 짝꿍(G3, 정수론, 18:35) A+B가 짝수인 경우는 골드바흐의 추측(웬만큼 큰 정수까지.. 공감수 0 댓글수 0 2023. 12. 6.
2023-12-03 PS 공부 오늘부터 PS 공부일지를 써 보려고 한다! 입시가 끝나서 PS를 자유롭게 할 수 있는 몸이 되었으므로,,, 앞으로 꾸준히 글을 쓸 예정이다. 오늘은 LCA 알고리즘과 희소 테이블을 공부했다. 15480번: LCA와 쿼리(P2) 케이스 분류가 정말 빡센 문제였다. 쿼리로 들어오는 두 정점이 일직선 상에 있는지 아닌지를 우선 나누고, 일반적인 트리의 형태를 그려서 각 정점별로 답이 될 수 있는 값을 찾는다. 이 때 판단의 기준을 1번 정점, u, v, lca(u, v), 그리고 각 정점의 depth 값으로 한다. 13511번: 트리와 쿼리 2(P3) lca, 그리고 희소 테이블(binary shifting)을 이용하는 문제이다. 1, 2번 쿼리 모두 lca를 찾는 과정에서 만든 이동 배열을 재사용해서 해결할.. 공감수 0 댓글수 0 2023. 12. 4.
제곱수 판별 알고리즘 정수 N이 주어졌을 때, N=k*k로 나타내어지는 정수 k가 존재하는지 판별하는 알고리즘이다. sqrt 함수의 시간복잡도가 O(logN)이라고 가정하면, 알고리즘의 시간복잡도는 O(logN)이 된다. int issqrt(int n){ int sq=(int)(sqrt(n)+0.5); if(sq*sq==n) return sq; else return -1; } 공감수 1 댓글수 0 2023. 12. 3.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.