PS(201)
-
2021년 1월 10일 PS 일지
어제 욕심이 과도했다 계획한거 하나도 안 끝내고 자버림! 이쯤되면 일상과 PS의 공존이 주내용 우선순위를 살짝 틀어서 1. 게임 이론 2. 수학 숙제 3. 학교 일 어제 교훈을 얻었으니, 2,3번은 하기 싫으면 안해도 된다는 결론을 내렸다. ㅋㅋㅋㅋㅋㅋ 이렇게 가자. Atcoder은 정 하고 싶으면 화요일날 버추얼 가야지! UPD1 게임 이론을 공부하기 위해 실제로 국제 게임 토너먼트에 참가했다 5명 중 2등했고, Stage 2로 간다. 당분간 디코 계속 켜야겠네 🤣
2021.01.10 -
2021년 1월 9일 PS 일지
어제 필요한 업솔빙을 다 하고 자서 기분이 좋다. 오늘은 원칙 상 블로그 글 쓰는 날이다. ARC가 오늘, ABC가 내일 있던데 해도 될까? 결론을 내렸다: 최근 공부한 게임 이론을 포스팅하고, 수학 숙제를 끝내고, 오답 노트를 완성한 다음, 학교 일을 마무리한 다음 라운드를 돌리기로 ㅎㅎ UPD: 과도한 계획은 할 수 있던 것도 못 끝내게 합니다. 다음 날로 넘어가주세요
2021.01.09 -
2021년 1월 8일 PS 일지
다른 분들처럼 막 거창하게 쓸거 아니다. 나만의 방식으로, 매일 쓰는게 목표다. 레이지 연습문제 하나 풀려 그랬는데, 그러지 말고, 수업 시작 전에 (월,목) 풀 테스트 문제로 남겨두었다. 그날은 테스트 문제, PST, CosmoCraft를 푸는게 학습 목표. 오늘은 Codeforces Round #695 (Div. 2)에 참가할거다. 7분 뒤 시작! 끝나고 간단한 후기 남겨보겠다. Codeforces Round #695 (Div. 2) 끝나고 Div2 치고는 어렵다는 평이 많았다. Worst contest 이런 댓글도 있었는데 반응이 좀 과하다는 생각이 든다. C를 잡다가 D로 넘어갔는데 이건 굉장히 좋은 선택이었다. A는 그리디 B는 Brute Force C는 Case Work D는 dp + pref..
2021.01.08 -
2021년 1월 7일 PS 일지
자기 전까지는 오늘이 맞지~ www.commonlounge.com/discussion/f6052177ea3543439251079f57f480e0 요기 옛날에 하다가 접었었는데, 초반 문제들이 너무 쉬운게 원인이다. 어려운거부터 해야지 보니까 어려운게 없다 ㅋㅋㅋ 엄청 대단한건줄 알았는데 별거 없네. 이래서 사람은 어떤거든 시작하고 봐야 한다. 일단 하기로 이미 글을 적어 놨으니, 모르는걸 찾아서 공부한다. 1. Augmented Segment Tree 코포 링크로 연결된다. PST 등 모르는 개념이 있어서 함께 공부하기로 한다 첨에 세그먼트 트리를 개념을 한 번 읽어봤다. 이미 알고 있는거여서 개쉽네~ 하고 넘기려다가 예제 문제 들어가봤더니.. 어렵네? 이때 이상함을 느끼고 기초부터 다잡고 가기로 했다...
2021.01.08 -
겨울방학
매일 1개 이상 하기~ 정해 놓은 로드맵은 다음과 같음 월 목 -> IOI Program 화 금 -> 코포 버추얼 / 라운드 수 토 -> 블로그 글 - 공부한 알고리즘 or 코포 - 하고 싶은거 일 -> 알고리즘 책 독서실에서 풀기 (전자기기 X) 하면 된다 여기에 동기부여용 시스템을 하나 만든다. 매일 실천한 내용을 정말 조금이라도 적는다. 그래야 계속하기가 훨씬 재밌따. 난 각 잡고 글 쓰는 것보다 이렇게 의식의 흐름대로 글을 쓰는 것을 정말 좋아한다.
2021.01.08 -
신기한 Contest
atcoder.jp/contests/hokudai-hitachi2020 Hitachi Hokudai Lab. & Hokkaido University Contest 2020 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp Marathon 형식의 Contest를 몇 번 봐 왔는데 이렇게 한달 동안 하는 건 처음 본다. 나중에 심심할 때 해보기~
2021.01.03 -
프로그래밍으로 수학하기
이버 확률과 통게 보고서를 생각했던 주제를 누가 이미 했다 ㄷㄷ 적분을 울프람 알파가 못해서 끙끙대고 있었는데 이 분은 중적분을 파이썬으로 수치적분해버렸다. (내가 몰라서 그렇지 매트랩으로도 가능할 것이다.) ok97465.github.io/2018/09/180911_DistanceBetweenTwoPointsOfQuadrate 수학 신호/영상처리 Python/C++ 코딩 수학, 레이다, 신호처리, 영상처리, Python, Programming 에 대해 공부한 부분을 정리해 두는 개인 블로그 입니다. ok97465.github.io 이거 보고 수학에 입문하고 싶다.
2020.12.29 -
제 1회 세종정보올림피아드
제 1회 세종정보올림피아드 후기 제 1회 즐겁게 고등부 1등 먹고 왔습니다. 친구들과 택시 타고 세종 SW 교육센터에 도착. 12시~12시 30분 사이 입실이라 근처에 있는 칼국수 집에서 든든하게 한 그릇 뚝딱. 오후 1시부터 5시까지 4시간 동안 진행했습니다. 풀이 스케치 A: 스위핑 문제. 일단 기지국이 원점이 되도록 좌표들을 평행이동한다. 레이저가 일직선 형태로 나아가므로 점들을 x>0 인 것과 x
2020.12.20 -
The J-th Number
The J-th Number 10641번: The J-th Number You are given N empty arrays, t1,…,tn. At first, you execute M queries as follows. add a value v to array ti (a ≤ i ≤ b) Next, you process Q following output queries. output the j-th number of the sequence sorted all values in ti (x ≤ i ≤ y) www.acmicpc.net 진짜 너무 화났지만 재밌는 문제다. PBS가 무엇인지는 이 글 참고. Range Update, Range Sum Query가 필요하므로 당연히 처음에 Lazy Propagation..
2020.12.17 -
병렬이분탐색 & 최소신장트리
www.acmicpc.net/workbook/view/5749 문제집: 병렬 이분 탐색 (pentagon03) www.acmicpc.net 최근 병렬이분탐색 문제를 많이 풀었는데, 모든 해결 소스의 실행 시간이 매우 긴 것을 확인했다. 실행 시간이 짧은 사람들의 코드를 확인해봤는데 대부분 최소 신장 트리라는 개념을 사용하더라. 대표적으로 승현이와 승현이, JOI 국가의 행사, Ski Course Rating 등이그렇다. -관련 설명 tamref.com/65 공부해보자.
2020.12.16 -
Codeforces Round #690 (Div. 3)
실력이 느는게 실감이 간다. System Test, Hacking을 조금 더 지켜봐야겠지만 웬만해서는 핵 당할 일은 없을 것이다 UPD: E2 TLE E2에서 심각하게 절었는데 페널티 덕분에 실시간으로 순위가 밀리는 걸 관찰했다 '-' 하지만! 그 덕분에 핵 당할뻔한 E1 코드를 고칠 수 있어서 만족한다. 생각 없이 눈에 보이는 것만 수정하고 코드를 다시 제출하는 습관을 버려야된다. 페널티를 쌓는 주 원인이다. A: Favorite Sequence 0:04 AC 투 포인터처럼 배열을 양 끝에서 번갈아 출력하면 된다. B: Last Year's Substring 0:15 AC 이렇게 오래 끌 문제가 아니다.. 주어진 문자열에서 합쳐서 "2020"이 되는 prefix, suffix가 존재하는지 묻는 문제. ..
2020.12.16 -
알고리즘 프로그램
www.commonlounge.com/discussion/5d2822257dfa49328d85fd27cf114441 Competitive Programming: From Beginner to Expert | CommonLounge This is a very comprehensive 94-part course on competitive programming. It gets you from knowing basic programming to being a yellow-red rated coder on Codeforces / CodeChef / TopCoder / etc. The primary objectives of this course are to learn about 30 diff www.commonlo..
2020.12.15 -
Slope Trick
이론 정리 게시물로 이동해주세요 howtoliveworldnice.tistory.com/477 Slope Trick - 함수 개형을 이용한 최적화 Special Thanks to Cgiosy Slope Trick: 함수 개형을 이용한 최적화 백준 13323 BOJ 수열 1 풀이 백준 13324 BOJ 수열 2 풀이 WhiteBoard Tutorial BOJ수열1 BOJ수열2 howtoliveworldnice.tistory.com 공부한 기록 12/14 : 21:40 ~ 23:20까지 블로그 글과 코드포스 글을 열심히 읽었으나 이해 실패 cgiosy 말로는 스스로 종이에 그래프 그려가면서 하는게 훨씬 이해가 잘된다고 한다. 다음 Try 때는 그렇게 한다 Slope Trick 공부하는 문제 jwvg0425-..
2020.12.14 -
Tree DP
www.secmem.org/blog/2019/02/10/TreeDP/ Tree DP 문제 해결 목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 알고리즘 공부를 하면서 오랫동안 다이나믹 프로그래밍을 그것도 트리에서 해결하는 문제를 꽤 안풀었음을 www.secmem.org codeforces.com/blog/entry/20935 DP on Trees Tutorial - Codeforces codeforces.com www.commonlounge.com/discussion/8573ee40c4cb4673824c867715a5bc7b Dynamic Programming on Trees (or Tree DP) | CommonLounge In this tutori..
2020.12.14 -
DCP 124
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem# 124: 격자판 DP Problem Description Idea DP(i,j) : (1,1)부터 (i,j)까지 오는 동안 먹을 수 있는 동전 가치 합의 최댓값 DP(i,j) = max(DP(i,j-1),DP(i-1,j)) + arr[i][..
2020.12.07 -
ABC 184
AtCoder Beginner Contest 184 AtCoder Beginner Contest 184 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp A : 하면 된다. B : string, cin 쓰면 공백 처리 편해서 좋다. D : C번보다 관찰이 쉬웠다. 기댓값 DP C : 사람에 따라 헷갈릴 수 있는 문제. 두 점이 주어지는데, 한 점을 원점으로 하도록 평행이동하는게 구현상 편하다. 대부분 2번만에 게임을 끝낼 수 있음을 관찰하면 문제가 쉽게 풀린다. F : Meet in the Middle. ..
2020.11.26 -
2020년 세종과학예술영재학교 정보올림피아드 풀이
※2020/11/23 - [Problem Solving] - 2020년 세종과학예술영재학교 정보올림피아드 후기에서 문제 풀이를 분리한 글입니다. 문제 소개 및 풀이 문제 체감 난이도와 사용 알고리즘은 다음과 같습니다. 문제 난이도 : A < B < D < C 핵심 알고리즘 : A 누적합 배열, B 투포인터, C 다이내믹 프로그래밍, D 세그먼트 트리 문제 A: 할로윈과 별사탕(L) 크기 N 배열에서 주어진 위치 k를 제외한 모든 위치에 x를 더하는 쿼리를 M번 처리하는 문제입니다. 모든 쿼리를 처리한 후 최종 배열을 출력해야 합니다. $ 1
2020.11.23 -
2020년 세종과학예술영재학교 정보올림피아드 후기
1등했습니다. ※이제 문제를 풀어볼 수 있습니다. code.sasa.hs.kr/problemset.php?page=34 A:2671, B:2672, C:2674, D:2675 1. 서론 세종과학예술영재학교 정보 행사의 꽃, 교내 정보올림피아드가 11월 21일, 토요일 열렸습니다. 대회는 시간 제한 3시간, 4문제로 구성되었습니다. 작년과 크게 달라진 점이 있다면 문제 수가 6문제에서 4문제로 줄었다는 것입니다. 작년 참가자 대다수가 4,5,6번을 건드리지도 못했고 1등조차 3문제 정답 + 부분점수 긁기로 400점을 넘긴 상황을 고려했을 때 합리적인 결정. 다만 4문제가 너무 쉽거나 어려울 경우 대회의 변별력이 크게 떨어지는 것을 우려했으나, 다행히도 그런 상황은 벌어지지 않았습니다. 2. 흐름 대회 시작..
2020.11.23 -
BFS 메모리 줄이는 방법
BFS에서 visit 배열을 거리 저장 용도로 사용하고는 한다. int vis[N][M]={}, dr[] = {1,0,-1,0}, dc[] = {0,1,0,-1}; queue q; q.push({sr,sc}); vis[sr][sc] = 1; while(!q.empty()){ auto t = q.front(); q.pop(); int r = t.first, c = t.second; for(int i=0;i0 ; sz--){ auto t = q.front(); q.pop(); int r = t.first, c = t.second; if(r==er && c==ec) return dist; for(int i=0;i0; sz--) 이 for문이 dist 값을 가진 노드들만이 큐에서 빠지게 해준다.
2020.11.18 -
Li Chao Tree 공부
어떤 기술 X의 사용 범위를 R(X)라 나타내자. R(Convex Hull Tree ) > 1; /* m에서 high가 더 크면 왼쪽에 high 넘기고 오른쪽 업데이트 */ if(cmp(high,low,m)) { tree[nd].v=high; if(tree[nd].r==-1) {..
2020.11.14 -
Knuth Optimization
DP Optimization Technique 정의 $ cost[i][j] $가 특정 조건을 만족할 때 아래 dp에서 최적화를 적용할 수 있다. $ dp[i][j] = \min_{i
2020.11.12 -
KOI에 등장하는 DP 문제들 #3
2020.11.03 codeup.kr/classop.php?class_id=7839 개인 강의 KOI에서 출제된 DP 문제입니다. codeup.kr 문제를 풀기 앞서 이번에는 무제한 고민보다는 15분 rule을 적용했다. 15분 rule은 한 문제당 최대 15분 연속으로 고민하는 것이다. 이는 15분 이상 고민해도 Idea조차 떠오르지 않는 상황에서 문제를 푼 경우가 거의 없었기 때문이다. 15분이 살짝 짧은 감도 없지 않아 있어 2시간 동안 실험해보고 15분이 적절한지 판단할 것이다. 15분이 됐을 때 뚜렷한 아이디어는 없지만 문제에 대한 감이 잡힌다~ 라는 상태면 5분간의 추가 시간이 부여된다. 물론 잘 풀리면 계속 풀면 된다. 그러다가 풀이가 틀렸다는 확실한 감이 오면 다음 문제(존재한다면)로 넘어..
2020.11.03 -
KOI 고등부 1,2번 문제집 완료
www.acmicpc.net/workbook/view/4576 다각형의 확장까지 풀면서 결국 문제집을 완료했다. 시험기간에는 역시 코딩이 잘된다.
2020.10.24 -
문제를 풀 때 답지를 보는 것
명확히 하자. 문제를 풀 때 답지 보는 것을 즐기는걸까, 문제를 맞췄다는 AC 마크를 받는 것에 쾌락을 느끼는걸까? 지금까지도 후자를 더 실행하고 있다. 쾌락은 분명 전자가 강하다. 그러나 후자가 더 쉽다. 문제를 풀 때 오래 고민하는 시간보다, 다른 사람의 아이디어를 보고 구현하는게 훨씬 간편하기 때문이다. 이렇게 하면 실력이 정체될 것이란걸 알면서도 아직도 답지를 본다. 개발자로 살기 싫다며, 기획자로 살자는 나의 각오를 기억하고는 있는걸까? 생각하자.
2020.10.23 -
Problem #79
벌써 79번 문제다 주어진 수열의 한 원소를 수정해 단조 증가로 만들 수 있느냐가 문제 non decreasing 수열의 정의를 살펴보면 쉽다 정의 : 모든 n에 대해 a(n) a(x+1) or a(x-1) > a(x) and a(x) < a(x+1) a(1)
2020.10.22 -
백준 3487 Copying Books/정올 책 복사하기2 해결코드
프레젠테이션 자료 정올 책 복사하기2 문제는 Copying books에서 M,K 제한이 추가된 문제로, 파라메트릭 서치 풀이를 강제한다. www.acmicpc.net/problem/3487 3487번: Copying Books The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 > k; for (int i = 0; i > arr[i]; M = max(M, arr[i]); } auto c..
2020.10.15 -
[도전 28일차] 기하 구현 끝판왕, 달팽이
백준 6990 달팽이 2020/04/09 - [Problem Solving/KOI 고등부] - (※재도전 시급) [도전 11일차] 백준 6990 달팽이 4월 9일에 포기했던 문제를 6개월만에 다시 잡다. 6개월 전 시청한 IOI Korea님의 풀이와 나의 오랜 thinking이 합쳐져 구현에 온전히 집중할 수 있었다. 문제 : 백준 6990 달팽이 문제 링크 문제 요약 : L * L 크기의 좌표 평면에 N 마리 달팽이가 있다. 달팽이들의 시작 위치는 정해져 있고 일직선으로 움직인다. 달팽이들은 1초에 1의 속도로 움직인다. 달팽이는 다른 달팽이가 움직인 흔적이나 벽에 부딪혔을 때 멈춘다. 달팽이들의 시작 위치와 초기 방향이 주어졌을 때 모든 달팽이들이 멈추는데까지 걸리는 시간은 얼마일까? 모든 달팽이들은..
2020.10.10 -
DO
CHT/리차오 연습 (문제풀이그룹) 인터랙티브 문제 디버거 만들기 jwvg0425-ps.tistory.com/136 인터랙티브 문제 로컬 디버깅하기 인터랙티브 문제를 처음 접하면, 틀릴 때 도대체 왜 틀렸는지 모르겠는데 디버깅하는 방법도 알 수가 없어서 굉장히 헤매게 된다. 모든 인터랙티브 문제에서 사용할 수 있는 방법은 아니지만 인 jwvg0425-ps.tistory.com DONE 10.10 달팽이 문제 www.acmicpc.net/problem/6990 bowbowbow.tistory.com/17 플레dp3대장 사수아탕 습격자초라기 박성원 트리의 가중치 www.acmicpc.net/problem/1289 atcoder.jp/contests/abc176/tasks/abc176_f F - Brave C..
2020.10.03 -
그리디연습1
풀이는 올리지 않는다. 시작 시간 13:35 끝난 시간 다음날 01:00
2020.10.01 -
KOI에 등장하는 DP 문제들 #2
2020.09.29 1. 부동산 투자 codeup.kr/problem.php?id=3724 정수 수열에서 연속된 1부분 또는 2부분을 골라 합을 최대화하는 문제. 수열 길이 N 0 : Left[N] = dt[N-1] else : Left[N] = N dtR[N] : N번째 수를 시작으로 하는 구간을 고를 때, 구간합의 최대 dt[N]과 똑같이 구한다. mdt[N]을 dt[1]~dt[N] 중 max로 정의하자. mdtR도 마찬가지. dt[N] 중 최대를 구한 후 모든 합최대구간 중 max( mdt[left[N]-1] , mdtR[N+1] , 0)을 구해 2번째 합최대 구간을 구한다. 구현! 놀랍게도 반례가 있었다. 합최대구간을 고르지 않는게 최대일 수도 있다. 위 증명에서 A1,A2중 적어도 하나는 X와 ..
2020.09.29