전체 글
-
코드포스 오렌지 달성 후기일기장 2021. 4. 10. 18:01
4/3~4/4에 있었던 Round #712(Div.1)에서 3솔하고 256등을 하면서 코드포스 오렌지를 찍었다. 작년 8/2에 처음으로 파이썬으로 프로그래밍을 접하고, 그 이후로 PS에 중독돼서 백준과 코드포스에서 800문제가량을 풀면서 실력을 길렀고, 드디어 오렌지를 찍게 되었다. 코드포스를 시작하고 4번째 라운드(20/10/24)에 블루를 찍었고, 20/12/04에 퍼플을 찍어서 오렌지는 1달~2달 정도 코포하면 바로 갈 줄 알았다. 하지만 내신대비와 학원 등의 이유로 1월에 대회를 한 번도 참가하지 못했고, 그 이후로 보는 대회마다 망하거나 시스텟이 터져버리는 바람에 레이팅이 1950 근처에서 변동이 거의 없었다. 그러다가 최근 두 대회에서 2200~2400 정도의 퍼포먼스가 나왔고, 레이팅이 71..
-
백준 18799번 풀이 (이상한 편집기)문제풀이 2021. 3. 26. 18:14
문제 링크: www.acmicpc.net/problem/18799 18799번: 이상한 편집기 스택에 전체 문자열을 추가한 뒤, 한 번 출력하는 것이 최적이다. www.acmicpc.net 문제를 보고 dp문제 느낌이 나길래 dp로 풀었습니다. 제한이 2000이기 때문에 O(N^3)으로는 안 풀리고, O(N^2logN)으로 풀기 위해 slope trick을 사용했습니다. 근데 이걸 slope trick이라 해도 되나? 풀이) 처음에 naive한 dp 풀이를 만든 후, 최적화하는 방식으로 풀이를 설명하도록 하겠습니다. 입력으로 들어온 문자열을 str, str의 길이를 n이라 하겠습니다. O(N^4) Solution 다음과 같은 dp배열을 정의합시다. dp[l][r]: 마지막으로 붙여넣은 문자열이 구간 [l..
-
백준 13515번 풀이 (트리와 쿼리 6)문제풀이 2021. 3. 17. 17:08
문제 링크: www.acmicpc.net/problem/13515 13515번: 트리와 쿼리 6 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 www.acmicpc.net 다음 2가지 쿼리를 처리하는 문제입니다. 1 i. i번 정점의 색을 바꾼다. 2 u. u와 연결된 정점의 개수를 출력한다. (단, 두 정점이 연결되었다는 것은 두 정점을 연결하는 경로상의 모든 정점의 색이 같다는 것을 의미한다.) 이 문제의 정식 풀이는 Tree DP를 heavy-light decomposition으로 최적화하는 것이고, sqrt decomposition을 통해 오프라인 ..
-
백준 20535번 풀이 (Good bye, BOJ 2020! G번)문제풀이 2021. 1. 3. 20:45
굿바이 boj 2020 대회에 참가하지 못해서 혼자 문제를 풀어보던 중 G번을 접하게 되었습니다. 문제를 보고 풀이가 금방 떠올랐는데 제 풀이가 알려져 있는 풀이들과는 다른 방식이여서 블로그에 올리게 되었습니다. (이 풀이는 정해보다 복잡한 방법이기 때문에 이렇게 푸는건 추천하지 않습니다. 그냥 이렇게도 풀 수 있구나 하고 재미로 봐주세요.) 문제에 대해 간략하게 설명하자면, 쿼리마다 몇개의 점 v_1, v_2, ... , v_k가 들어오는데 가능한 모든 점의 순서쌍 (v_i, v_j)에 대해 lca의 깊이의 합을 계산해서 출력하는 문제입니다. (단, i
-
블로그 소개글공지 2021. 1. 2. 18:53
안녕하세요. 블로그를 시작하게 된 qwerasdfzxcl(리프)입니다. 최근 ps에 관심이 생기게 되면서 다른 ps 고인물분들처럼 블로그를 만들어봐야겠다는 생각에 블로그를 시작하게 되었습니다. 주로 포스팅할 내용은 boj 문제풀이, codeforces나 Atcoder 대회 후기, KOI, NYPC와 같은 대회 후기 및 풀이 등을 올릴 예정입니다. 백준 문제풀이나 대회 풀이는 인터넷에 많이 있기 때문에 제 블로그에는 인터넷에 풀이가 없거나 저만의 풀이로 푼 문제의 풀이를 올릴 예정입니다. 수정 날짜: 2021/03/17