분류 전체보기(222)
-
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 -
모든 Mother Vertex를 O(V+E)에 구하는 알고리즘
발행일 : 2020-07-08 UPD1 : 2020-09-25 Find All Mother Vertices in a directed graph. Mother Vertex. 어떤 방향 그래프에서 한 정점이 다른 모든 정점에 도달할 수 있다면 이를 Mother Vertex라 부른다. 이 글에서는 방향 그래프에서 존재하는 모든 Mother Vertex를 구하는 방법에 대해 알아본다. Existence of a Mother Vertex Mother Vertex의 존재성을 판정하는 방법은 두가지가 있다. 첫번째 방법은 각 정점에서 방문이 가능한 정점을 저장하는 bitset을 생성한다. 모든 비트가 체크된 노드가 있다면 그것은 Mother Vertex이다. DFS를 통해 bitset을 갱신한다. 주의할 것은 한번의..
2020.09.25 -
특정 조건에서 LCS를 O((n+m) log (nm))에 구하는 알고리즘
*LCS Longest Common Subsequence. Subsequence는 부분수열들이 꼭 연속하지 않아도 된다. 예를 들어 두 수열 A,B가 있다 하자. A = 1 5 3 4 2 6 5 B = 1 6 3 2 3 5 A와 B의 부분 수열은 {1}, {3}, {1,2} 등 여러가지가 있다. A와 B의 LCS는 {1,3,4,5}이고 그 길이는 4이다. A의 길이를 n, B의 길이를 m이라 할 때 다이나믹 프로그래밍을 이용해 O(nm)의 시간에 LCS(A,B)를 구할 수 있다. 이는 잘 알려져 있는 알고리즘이므로 쉽게 설명된 글이 많다. 이 글에서는 특정 상황에서 빠르게 LCS를 구하는 방법에 집중한다. 또한 앞으로 LCS를 구하는 것을 LCS의 길이를 구하는 것과 동일하게 취급한다. *특정 조건에서 ..
2020.09.25 -
KOI 에 등장하는 DP 문제들 #1
codeup.kr/classop.php?class_id=7839 개인 강의 KOI에서 출제된 DP 문제입니다. codeup.kr Day1 2020/09/17 1. 숫자 카드 (초등 5, 중등 3) 1부터 34까지 수가 적힌 카드 40자리 이하의 수가 주어질 때 카드로 분해하는 가짓수 일단 수를 string으로 받아야 한다. 이를 num이라 하자. dp[i] = i자리까지 보았을 때 숫자를 분해하는 가짓수 dp[i] = (i번째 자리가 1 이상 9이하일 경우 dp[i-1]) + (i-1번째 자리와 i번째 자리 숫자로 이루어진 수가 1 이상 34이하일 경우 dp[i-2]) 이때 2번째의 경우 i-1번째 자리가 0이면 안되는 것에 주의하자. 더보기 #include char s[50]; int dp[50]; i..
2020.09.18 -
USACO 2020 Feb Gold
www.acmicpc.net/category/detail/2200 USACO 2020 February Contest Gold www.acmicpc.net 1. Timeline -30min Solve f(t)를 t번 정점의 시간이라 하자. S_t
2020.09.16 -
약수의 개수의 합을 빠르게 구하는 방법
code.sasa.hs.kr/problem.php?id=1343 SASA OJ 자연수 k에 대하여, k의 양의 약수의 개수를 f(k)라고 하자. 예를 들어, 12의 양의 약수는 1, 2, 3, 4, 6, 12 이므로 f(12)=6 이다. 자연수 n에 대하여, g(n) = f(1) + f(2) + f(3) + … + f(n-1) + f(n) 이라고 정의하자. code.sasa.hs.kr 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include //Code Sasa 문제 1343: 약수의 개수의 합 //pentagon03 //일반적으로 n의 약수의 개수를 sqrt(n)로 구하는 과정의 변형 /*..
2020.09.10 -
정보과학올림피아드 1차 문제 형식 제안
2019년부터 달라진 점은 C++ 코드 해석 평가를 그만두고 비버챌린지 형식 문제들이 출제된다는 점이다. 이산 수학, 조합 문제들은 계속 만나볼 수 있다. 기출문제들을 풀면서 생각한 것인데 정보올림피아드 문제들도 프로젝트 오일러 http://projecteuler.net/와 같이 컴퓨터를 써서 풀 수 있는 문제들로 구성하면 좋겠다. 이산 수학은 기초적인 수학 능력이 맞다. 이산 수학 문제는 오로지 수학 능력을 체크하는 반면 오일러 프로젝트의 문제들은 정보과학적 사고 능력과 수학 능력을 모두 가지고 있어야 해결하기 때문에 정보과학 올림피아드에 더 적합하다고 생각한다. 결론 -> 기존 수학 문제 난이도 up + 문제 풀 때 (구름)IDE 사용 가능하도록 변경 복잡한 컴퓨터를 이용하여 효과적으로 가능하다는 것..
2020.09.09 -
2020 NYPC 예선 후기
대회는 8월 28일부터 9월 6일까지 총 10일에 걸쳐 진행되었습니다. 2일마다 1회차 6개, 2회차 4개, ..., 5회차 2개의 새로운 문제들이 순차적으로 공개됐습니다. 첫 날 문제는 2시간 내에 전부 해결 가능한 난이도였습니다. 그러나 3회차부터 2시간 이상 고민해도 쉽게 해결되지 않는 문제들이 생겼습니다. 대회가 끝나고 꼭 풀이를 찾아 공부하고자 합니다. 첫 NYPC 예선, 충분히 즐거웠습니다. 즐거웠던 문제들 11. 이어달리기 (1) Best Time을 임의로 정한다 (N*N) (2) 그리디적 풀이를 생각한다 (1)과 (2)의 조합으로 풀이를 떠올릴 수 있습니다. 그리디적 풀이는 Time들을 정렬한 뒤에 이루어집니다. 힌트는 한 Time을 봤을 때 가능한 큰 Time과 더해 유효한 시간을 만드는..
2020.09.06 -
다양한 세그먼트 트리 구현 방법
최종 구현 백준 구간합 구하기 Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include using namespace std; using ll = long long; struct Seg{ int n; vector t; void build(int n){ this->n=n; t.resize(2*n); } void build(int n,vector&a){ this->n=n; t.resize(2*n); for(int i=0;i=1;i--) t[i]=t[i>1]=t[pos]+t[pos^1]; } ll query(int l,int..
2020.08.29 -
백준 19623 회의실 배정 2,3,4
백준(BOJ)에 신규 시리즈 문제가 올라왔다. BOJ $19621, 19622, 19623$ 대표적인 그리디 문제로 유명한 '회의실 배정'의 후속작이다. 기존 문제와의 차이점은 각 회의에 가중치가 존재하는 것이다. 즉, 개수가 아니라 가중치의 합을 최대로 만들어야 한다. 2, 3번 문제는 같은 문제에서 크기를 변형한 것이다. 간단한 관찰을 통해 쉽게 해결할 수 있다. 더보기 K번 회의가 오직 K-1, K+1번 회의와 겹친다는 사실이 암시하는 것은 무엇일까? 더보기 1. 회의들은 끝나는 시간이 짧은 순으로 정렬되어 입력이 주어진다. 2. K번 회의는 K-2번 회의와 겹치지 않는다. 4번 문제는 그리디적 요소가 아예 배제되었다. 2,3번 문제의 해결 방법으로 바로 해결되지 않는다. 보자마자 든 생각은 예전에..
2020.08.29 -
Pause / 일시 중지
Since I want to master Calculus, I decided to pause solving Daily Coding Problems for a while. Postings will be continued from Problem #20 at 2020.9.26. Cya, readers and DCP. Daily Coding Problem 푸는 것을 잠깐 멈춥니다. 2020.9.26, Problem #20부터 다시 시작합니다. UPD) 2020.10.26, Problem #20부터 다시 시작합니다.
2020.08.26