본문 바로가기

PS

 (8)
7/14~7/15 Codeforce 연습 학기가 끝났다. 정말 열심히 놀았다. 학점도 적당히 받았고 하니 이제 PS를 해보자! 1000-1500 rating의 그리디 문제들을 잡았다. 1703F. Yet Another Problem About Pairs Satisfying an Inequality 문제에서 요구하는 식이 웃깁니다. $a_i
지금까지의 삶 + 12/25 PS 입시가 끝났다. 서울대학교 컴퓨터공학부에 입학하게 되었다. 이제 다시 PS를 시작해야 한다. 내 큰 계획은 다음과 같다. 1. PS 재활 + 코드포스 기초 쌓기 2. 백준 기초부터 다시 풀기 3. 흥미로운 것들 학습. 지금은 가우스 소거법과 hld를 배우고 싶다. 4. 코드포스 블루 찍기 일단 코드포스에서 쉬운 문제들을 잡고 풀어보았다. 실력이 처참함을 다시 깨닫는다. Codeforces 1620B. Triangles on a rectangle 간단한 문제이다. 삼각형의 넓이는 밑변과 높이에 의존한다. 최소한 두 점이 같은 변 위에 존재하므로 높이가 최대일 때는 나머지 한 점이 반대편에 존재할 때이다.따라서 네 변 각각에 대해 거리가 최대인 점의 쌍을 찾아서 높이를 곱해주면 된다. Codeforces 1..
2021 NYPC 연습문제 풀기 2021년도 NYPC가 내일 시작한다. 연습문제 2개가 올라와서 풀어보았다. 1. 최대구간합 너무 유명한 문제다. $dp[i] = max(dp[i-1]+a[i],\,\, a[i])$ 2. 도토리를 주워라 출력 결과만 제시하면 되지만, 그냥 평범한 문제라고 생각하고 풀어 보자.좌우로 움직이는 것이 자유롭기 때문에 칸별로 보는것보다는 움직일 수 있는 구간별로 보는 것이 좋다. 만약 어떤 두 구간 사이에 유저가 존재한다면 두 구간에 있는 도토리를 동시에 먹을 방법이 없다.따라서 dp를 다음과 같이 세운다: $dp[i][j]=$ $i$번째 가로줄에서 $j$번째 구간에 있는 도토리를 모두 먹을 때 최대 도토리의 개수 구간끼리의 연결 관계를 설정하면 상태 전이는 $dp[i][j] = max(dp[i-1][k])$ ..
8월 1주차 PS 컨셉은 쉬운 문제 밀기 + 그리디 Codeforces Round 703B. Eastern Exhibition Sol) $x$축과 $y$축이 독립이기 때문에, 각각에 대해서 최소인 $x$좌표와 $y$좌표를 찾으면 충분하다. 이때, 거리가 절댓값들의 차의 합으로 정의되기 때문에 거리의 합의 함수가 아래로 볼록해진다. 따라서, 맨 밑의 계곡에 있는 원소의 개수를 찾으면 된다. 점 개수가 홀수일 때는 1, 짝수일 때는 중앙값 2개의 차이를 곱하면 답이다. Codeforces Round 703D. Max Median Sol) 어떤 값의 최댓값을 묻고 있으므로, Parametric Search를 적용해서 답이 x보다 크거나 같은가?라는 질문으로 바꾼다. 어떤 구간에 주어진 값이 오직 1과 -1뿐이라고 하자. 그렇다..
2월 4주차 PS: 문자열 대신 귀 여운 문자열을 드리겟 습니다 문자열은 마법처럼 풀리는 게 많아서 재밌다. 응용도 내가 푸는 레벨에서는 심하지 않고.. 백준 13506 카멜레온 부분 문자열 www.acmicpc.net/problem/13506 13506번: 카멜레온 부분 문자열 문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다. 문자열 S가 주어졌을 때, 카 www.acmicpc.net 학교 수업에서 본 문제인데, 근본 살리기를 위해 재방문 해 보았다. 풀이>> 더보기 주요 아이디어: KMP 중간에 한번 더 나오는 공통 접두-접미사들 중 제일 긴 걸 찾으라는 말이다. 원래 문자열을 $a$라 하자...
2.21 PS: 쉬운 정올 문제 풀기 정올 문제들이 전반적으로 괜찮다고 생각한다. 적당히 높은 수준, 참신한 아이디어 등등.. 그래서 골드 문제들만 찍먹하기로 했다. 백준 17623 괄호 ( 2019 고등부 본선 2번 ) www.acmicpc.net/problem/17623 17623번: 괄호 6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해 www.acmicpc.net 되게 참신한 문제다. 나만 몰랐던 건가? 풀이>> 더보기 주요 아이디어: DP 문제에서는 마치 변수 두 개를 만족하는 최적해를 내놓으라는 것 같아서 접근이 힘들어 보이는데, 잘 보면 괄호 값 자체는 고정되어 있다. 그..
2.18 PS: 도전 www.acmicpc.net/problem/10098 10098번: 양분 섬을 합동인 두 다각형으로 나누는 선분이 존재하면, 선분의 두 끝점이 (x1, y1), (x2, y2)일 때 x1, y1, x2, y2를 나타내는 4개의 정수를 한 줄에 출력하면 된다. x1=x2이거나 y1=y2여야 한다. 선분은 다 www.acmicpc.net 백준 10098 양분.. 아이디어는 대강 생각해 놓았다.진짜 풀어보고 싶다. 대충 세 단계 정도면 풀 수 있다. (아마?) 1. 합동이면 넓이가 같으므로, 넓이를 이등분하는 x축, y축에 평행한 직선을 이분 탐색으로 빠르게 찾는다.이 "빠르게" 는 x축 기준, y축 기준으로 블록들을 나눈 뒤에 부분합 배열을 만들어서 할 수 있다. 2. 교점을 구해서 새로운 다각형 두 개를 ..
2.17 PS: 세종정보올림피아드 밀기 세종정보올림피아드를 개인 사정으로 불참하고 나서, 언젠가는 풀어야겠다는 생각을 하고 있었다. 그런데, 요즘 푸는 문제들이 하나같이 귀찮다. 재밌긴 한데, 구현까지 가지를 못 한다. PS에 대한 즐거움을 살리기 위해 오늘 한번 날을 잡고 풀어 보았다. 학원 수업은 안 들었지만 어떠한가. 체감 난이도는 실5-실1-플5-플4? 되게 쉽게 풀고 끝낼 줄 알았는데, 난 내 생각보다 더 못한다.;; code.sasa.hs.kr/problemset.php SASA OJ code.sasa.hs.kr 함께 풀어볼 분들은 이 사이트를 권합니다. 2690 세종이와 레이저(L)(고등부 A번) ABC C번에 나올것처럼 생겼다. 풀이>> 더보기 주요 아이디어: 구현, map 원점을 레이저로 잡고 기울기들을 세면 된다. 이건 st..

티스토리툴바