PS/Problem Solving(124)
-
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 -
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 -
문제를 풀 때 답지를 보는 것
명확히 하자. 문제를 풀 때 답지 보는 것을 즐기는걸까, 문제를 맞췄다는 AC 마크를 받는 것에 쾌락을 느끼는걸까? 지금까지도 후자를 더 실행하고 있다. 쾌락은 분명 전자가 강하다. 그러나 후자가 더 쉽다. 문제를 풀 때 오래 고민하는 시간보다, 다른 사람의 아이디어를 보고 구현하는게 훨씬 간편하기 때문이다. 이렇게 하면 실력이 정체될 것이란걸 알면서도 아직도 답지를 본다. 개발자로 살기 싫다며, 기획자로 살자는 나의 각오를 기억하고는 있는걸까? 생각하자.
2020.10.23 -
백준 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 -
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 -
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 -
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 -
P#19 Minimum Sum Problem
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding DP[state] = minimum sum of using columns of state index : 0 1 2 3 4 5 states : 1 1 0 1 1 0 this state implies that column 0,1,3,4 are used Use dfs to backtrack all possibile situations. def solve(row:int=0, state:int=0, weight:int=0) ->int: global dp,n,k if state in dp and weight >=..
2020.08.23 -
유용한 PS Blogs & Articles
전설이다 https://koosaga.com/242?category=554431 동적 계획법을 최적화하는 9가지 방법 (1/4) 동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때 koosaga.com 코포 게시글이 많다. https://gumgood.tistory.com/169 Segment Tree (+ Lazy Propagation) 코드 최적화 원문 : https://codeforces.com/blog/entry/18051 Segment tree with single elment modifications Segment tree는 한 배열에서 몇 번의 변경이나 연속..
2020.08.22 -
고알 연습#3
8월 21일 2시간, 5문제 A,C,E -> 그리디 B,D -> 분할정복 실력도 문제고 끈기도 문제다. 매일 한다고 생각하니 진지함이 없어졌다. 전화 오면 받고, 메일 알림 오면 답장하고, 카톡 오면 카톡한다. B는 더 고민했으면 맞출 수 있는 문제였다. A는 #2의 그 문젠데 고민해도 모르겠더라 이로써 업솔빙해야 하는 문제는 3개가 되었다. 금광, 직선 찾기, 멀티탭 스케줄링. C -> 알파벳이 사용되는 수를 합치고, 수가 큰 순서대로 정렬 E -> positive, nonpositive 나눠서 생각. 단, 1은 곱하지 말고 더해줘야 함.
2020.08.21 -
고알 연습#2
8월 20일 2시간 5문제 문제를 풀 때 랭크를 가렸고, 난이도/전략과 무관하도록 셔플했다. 총 점수 : 2솔 내 처음 분석은 이랬다. A: 비트마스킹 DP, B: TreeDP (분할정복 느낌), C:그리디, D: 랜덤 알고리즘, E:그리디/완탐 A,E,B에 대하여 대략적인 풀이를 생각하고 E,A,C,B 순으로 구현에 들어갔다. 개선할 부분 : E->그리디적으로 풀 때는 '확실해야 한다'. 이런 문제를 그리디적으로 풀 때 특징이 if문으로 코드가 난잡해진다는 것이다. 그렇기에 더 꼼꼼해야 한다. KOI, 학교 수행평가는 상관 없다. 그러나 코포/앳코더 같이 페널티 큰 대회들은 이런게 치명적이므로 신경 쓰자. 전체적으로 느렸다. 여유와 쳐짐을 구분하자. A-> 좋았다. dp 테이블 정의도 깔끔했고 구현도 ..
2020.08.20 -
과반수 원소 알고리즘
Majority Element / Majority Vote Algorithm 주어진 리스트에서 과반수를 차지하는 원소의 존재성 판정과, 존재 시 과반수 원소를 구하는 알고리즘. A[] = { 1, 3, 1, 1, 2} 리스트 A에서 과반수 원소는 1이다. 정렬하면 슥삭 풀리는 문제이지만 O(N) 시간복잡도에 가능한 알고리즘이 존재한다. O(N) Solution 내가 소개할 것 : Pair 매칭 알고리즘. *기존 길이 $n$ 리스트 A로부터 길이 $[n/2]$ 리스트 B를 만든다. N이 짝수일 때 : 앞에서부터 차례대로 2개씩 묶는다. 각각의 pair (x,y)에 대해 x==y면 하나만 남기고, x!=y면 둘 다 제거한다. A[]={1,3,1,1,2,1} 을 예시로 들자면 (1,3) => (), (1,1)..
2020.08.20 -
고급 알고리즘 연습#1
0819 수요일 2시간 3분, 5문제 학교 시험 범위에 맞추어 (완탐,그리디,분할정복,DP,기댓값) Set을 잡았다. 앞으로도 고알 연습은 이렇게 돌릴 것이고, 특정 알고리즘이 약하다는 판단이 나오면 알고리즘 종류를 제한할 수 있다. 연습을 돌리기 전 Tourist의 글을 읽었다. - Tourist는 현 코드잼 챔피언으로 최근 수 년 간 자리를 유지했다. 글은 경진 프로그래밍 대회에서의 그의 전략을 담았다. 내가 깨닫고, 이번 Set에서 실천한 것. : 모든 문제를 먼저 푼다. 한 문제를 푼다는 것은 다음 단계들로 이루어진다. Read - Solve - Implement - (Debug) 여기서 Tourist의 전략은 먼저 모든 문제들을 읽고, 핵심 아이디어를 생각해 놓은 다음 Implement로 들어가..
2020.08.19 -
백준 2437 저울
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 문제 만들 수 없는 무게의 최솟값은 무엇인가? 초기 접근 : DP DP[i][j] : 1~i까지의 추를 이용해 무게 j를 만들 수 있는가? 최후에 DP[n][x]를 관찰해 x가 false 인 첫번째 x를 출력하려고 했다. 막힌 것은 추의 무게의 범위가 1~1000000, 추의 개수의 범위가 1~1000이므로 DP[] 는 1e9개의 비트를 저장해야 한다. 메모리 초과 + DT를 채우는 것 자체가 만만치 않다..
2020.08.14 -
긴 대장정이었다.
쉬운 DP 문제인줄 알고 시작했던 것이 실은 수학과 최적화 문제였다. 이 문제를 풀면서 강한 멘탈과 '아이디어' 구체화의 중요성을 다시 한 번 깨달았다. 덕분에 깊게 몰입해서 빡센 구현을 할 수 있었다. 문제를 만드시고, 감을 잡지 못할 때 아이디어를 주신 최성준 선배님께 감사한다. https://code.sasa.hs.kr/problem.php?id=1525 SASA OJ 첫 번째 줄에 정수 M, N, K, p의 값이 입력으로 주어진다. 이때, M은 1 이상 1000000 이하의 정수이고, N은 1 이상 1000 이하의 정수이다. K는 0 이상 10 이하의 정수이고, p는 10000000 이상 1000000009 이하의 소 code.sasa.hs.kr Code SASA 1525: [어려움] 이동하는 경..
2020.07.24 -
Counting Sort할 때 누적합 배열 사용 이유
및 많은 교재에서 계수 정렬 - Counting Sort를 cnt 누적합 배열을 이용해 구현한다. 이를 배울 때 나는 이것이 무용하다고 생각했다. 누적합 없이도 그 개수만큼 세서 큐에 넣어주면 되기 때문이다. 그러나 오늘 pair형 data를 counting sort 하는 것에 대해 공부하고 나서 누적합 배열의 유용함을 알게 되었다. 그 유용함은 바로 index를 cnt 배열을 통해 정해준다는 것이다. 그러므로 그 데이터 자체가 아니더라도 부가적인 정보를 stablesort할 수 있다는 장점이 있다. 부가적인 정보의 예로는 입력 순서 등이 있다. 자세한 구현은 링크에 있으니 꼭 정독하고 counting sort를 마스터하자. https://blog.naver.com/jqkt15/222031601969 [..
2020.07.22 -
[백준] 퇴사
https://www.acmicpc.net/problem/14501 #include #define IOS ios::sync_with_stdio(false);cin.tie(0); typedef long long ll; const int INF = 1e9; const ll LINF = 1e17; int n,t[16],p[16]; int DT[16]; int main(){ IOS; cin>>n; for(int i=1;i>t[i]>>p[i]; for(int i=n;i>=1;i--){ if(i+t[i]-1
2020.07.20 -
각종 알고리즘
Disjoint Set #include #define SIZE 110 class Disjoint_Set{ private: int root[SIZE],rank[SIZE],cnt[SIZE]; public: void Make_Set(int x){ root[x]=x; rank[x]=0; cnt[x]=1; } int Find_Set(int x){ if(x==root[x]) return x; return Find_Set(root[x]); } //Union by Rank void Union(int a,int b){ a=Find_Set(a); b=Find_Set(b); if(a==b) return; int t=cnt[a]+cnt[b]; if(rank[a]>rank[b]){ root[b]=a,cnt[a]+=cnt[b];..
2020.07.08 -
세종 병원
https://code.sasa.hs.kr/problem.php?id=2452 풀이의 개요는 다음과 같다. 1. 손님들을 응급환자,예약환자,일반환자로 구분을 하여 각기 다른 큐에 집어넣는다. scanf("%d : %d") 를 이용해 시간을 효과적으로 입력받는다. 시간이 HH:MM꼴로 되어 있을 텐데 time = HH*60 + MM으로 나타내어 선후관계를 파악하기 쉽게 한다. 세종이의 '도착 시점'을 이때 기록해놓아야 한다. 2. 이때 큐는 '줄을 서기 시작하는 시점'을 우선순위로 하여 가장 빠른 사람을 dequeue하는 우선순위큐여야 한다. 우선순위큐의 원소는 구조체이며, 구조체간 비교 연산이 정의되어야 한다. 3. 환자들을 한명씩 진료한다. 이때 각 사람의 진료가 끝나는 시점을 기록하여 '현재 시간'을..
2020.06.22 -
첫 Codeforces
Codeforces Div.3에 처음으로 참여했다. https://codeforces.com/contest/1367 Dashboard - Codeforces Round #650 (Div. 3) - Codeforces codeforces.com A,B,C는 문제를 빠르게 읽는 것에 경각심을 느끼게 해주었다. D,E는 문자열 다루기에 익숙해지라는 것을 가르쳐주었다. F1,F2는, 내가 아이디어에 강하지만 애매한 구현을 더 연습해야 좋은 결과를 낼 수 있다는 조언을 주었다. 새벽에 재밌었다.
2020.06.17 -
시험 끝나고 PS
https://codeup.kr/problem.php?id=4488 트리회전 첫 번째 줄에는 입력되는 두 트리의 노드 개수를 나타내는 정수 N(5≤N≤300)이 주어지며, 각 노드는 1번 부터 N번까지 번호가 부여된다. 두 번째 줄부터 다음 N개의 줄에는 첫 번째 트리의 구조를 � codeup.kr 최근에 RB트리를 배워서 재밌어 보인다. https://codeup.kr/problem.php?id=4643 달팽이 첫째 줄에는 달팽이의 수 N(1≤N≤1,000)과 울타리 한 변의 길이(cm)를 나타내는 자연수 L(10≤L≤10,000)이 빈칸을 사이에 두고 주어진다. 울타리의 왼쪽 아래 좌표는 (0, 0)이고 오른쪽 위의 좌표는 (L, codeup.kr 광란의 기하 https://codeup.kr/prob..
2020.05.31 -
[Code SASA] 정독실에서 tic-tac-toe
https://code.sasa.hs.kr/problem.php?id=1067 SASA OJ 지원이와 진주는 기숙사에서 새벽에 정독실에서 tic-tac-toe를 두고 있습니다. 지원이는 흑돌, 진주는 백돌을 두고 있는데, 지원이는 진주 몰래 컴퓨터를 이용하여 각 자리마다 그 자리에 두었을 �� code.sasa.hs.kr 하루를 성공적으로 시작하게 해준 문제!!! 1. Tip => 코딩 문제 풀 때는 Pomotroid를 애용하자. 25분 코딩 - 5분 휴식 루틴! 2. 확률 계산이 중요한 문제. 처음에 turn에 따라 확률 계산을 다르게 해야하는 줄 알고 멘붕이 왔었다. 그런데 사실 turn은 그저 맵의 상태를 바꾸어주는 것일 뿐 실제로 돌을 두는 판단을 해야되는 시점은 오직 맨 처음 뿐이므로 쉽게 쉽게..
2020.05.23 -
[Code SASA] 숫자 카드 게임
숫자 카드 게임 SASA OJ 첫 번째 줄에 카드의 개수(1
2020.05.15 -
Scheduling/스케줄링 알고리즘
Code SASA가 다시 열린 기념으로 선배들이 만든 문제를 풀었다. 그러던 도중 예전에 풀었던 문제를 발견했다. https://code.sasa.hs.kr/problem.php?id=1297 SASA OJ 영화를 좋아하는 세종이는 쉬는날인 오늘 영화관에 가서 하루종일 영화를 보려고 한다. 오늘 상영하는 영화의 개수를 N, 각각의 영화의 상영 시작 시간을 S, 상영 종료 시간을 E라고 할 때, 오늘 세종이가 볼 수 있는 영화의 최대 수를 출력하여라. (단, 오늘 24시 이전에 시작하여 다음날에 끝나는 영화도 오늘 상영하는 영화에 포함하며, 상영시간이 24시간 이상인 영화는 없다.) code.sasa.hs.kr (전형적으로 보이는) 영화 스케줄링 문제이다. 어떻게 풀었나 싶어 봤더니 웬걸 N=100 인데도..
2020.04.09