qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

백준에 있는 "단계별로 풀어보기" 문제들을 모두 풀었다. 작년 9월쯤부터 c++로 PS 공부를 하기 시작하면서 단계별로 풀어보기로 공부했는데 드디어 모든 단계를 전부 해결했다. 대충 난이도를 정리해보면 1~10: 기본 문제들 (언어 연습용) 11~24: 기본적인 알고리즘들 (여기까지만 알아도 코포 딥2C~D까지 풀 수 있음) 25~40: 조금 더 어렵지만 많이 쓰이는 알고리즘들 (여기까지만 알아도 코포 퍼플~오렌지 수준의 지식은 된다) 41~46: 약간 십덕인 알고리즘들 (icpc 같은 곳에는 나오지만 플로우, fft처럼 oi범위가 아닌게 많다) 47~50: 어려운 알고리즘 공부하고 싶은 십덕들을 위한 단계 단계마다 기본문제랑 연습문제들이 들어있어서 알고리즘 공부하기 좋은 것 같다.

퍼플->오렌지는 4달이나 걸렸는데 오렌지->찐렌지는 1달 밖에 안 걸렸다 ㅋㅋ 최근 본 코포 전부 퍼포가 찐렌지~레드 수준으로 나와서 3번만에 찐렌지를 찍을 수 있었던 것 같다. 특히 round #718(div1+div2)에서 운 좋게 159등을 해서 한 번에 115점이 올랐다. 아직 내 실력으로 레드 가는건 무리일 것 같지만 최대한 노력해봐야겠다.

http://boj.kr/8481 8481번: Generator Your program should print the content of the file geni.out to the standard output. Your output may contain additional white space at the end of some lines or at the end of the file. www.acmicpc.net solved.ac 티어: D3 다3짜리 구현(+규칙찾기)문제다 ㅋㅋ; 계속 플래~다이아만 밀다보니까 머리도 아프고 문제도 잘 안 풀려서 잠깐 휴식하면서 구현 연습하려고 이 문제를 풀기 시작했는데 절반쯤 풀었을때부터 후회되기 시작했다. ㅋㅋㅋㅋㅋ 이 문제 풀지 마세요 풀이) 데이터 분석을 하기 ..

숫자 놀이 (BOJ 1187)푼 날짜: 4/7solved.ac 티어: D5 풀이:N=2^k이기 때문에 간단한 아이디어로도 풀린다.일단, N=2일 때는 기우성(홀짝성)이 같은 2개의 수를 고르면 된다.N=2^k (k>=2)인 경우, 수 N-1개를 고른 후, N=2^(k-1)인 경우에서 그 집합에 대해 답을 구해놓는다. 이를 S_1이라 하자.원래 수들의 집합에서 S_1을 빼고, 방금 했던 시행을 한다. 이 시행을 2번 더 해서 집합 S_2와 S_3를 얻을 수 있고, 이 세 개의 집합의 합들을 2^(k-1)으로 나눴을 때 기우성이 같은 두 집합의 합집합이 답이 된다.구현은 분할정복처럼 하면 된다.시간복잡도는 대충 O(3^k) 같은데 맞는지 잘 모르겠다. (얼마인지 알면 댓글로 알려주세요.) 참고로 임의의 N에..

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..

문제 링크: 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..

문제 링크: 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을 통해 오프라인 ..

굿바이 boj 2020 대회에 참가하지 못해서 혼자 문제를 풀어보던 중 G번을 접하게 되었습니다. 문제를 보고 풀이가 금방 떠올랐는데 제 풀이가 알려져 있는 풀이들과는 다른 방식이여서 블로그에 올리게 되었습니다. (이 풀이는 정해보다 복잡한 방법이기 때문에 이렇게 푸는건 추천하지 않습니다. 그냥 이렇게도 풀 수 있구나 하고 재미로 봐주세요.) 문제에 대해 간략하게 설명하자면, 쿼리마다 몇개의 점 v_1, v_2, ... , v_k가 들어오는데 가능한 모든 점의 순서쌍 (v_i, v_j)에 대해 lca의 깊이의 합을 계산해서 출력하는 문제입니다. (단, i