leo020630의 블로그

카테고리 제목이 '오늘의 PS'인데 제목에는 당당히 7일치를 박아놓았다. 하지만 저 기간 중 문제를 풀었다고 할 날은 5월 1일과 7일 이틀뿐이었기 때문에, 한 글에 정리해보려 한다. 5월 1일 - 2022 DGIST 현풍전산배 알고리즘 대회 Open Contest 타임라인은 정확히 기억이 나지 않아 문제별 후기만 간단히 정리하도록 하겠다. A. 에어컨 전형적인 구현 문제이다. A번 치고는 까다로운 구석이 여럿 있었던 것 같다. 출력 형식 때문에 printf를 오랜만에 사용해 볼 수 있었다. B. 비즈마켓 코포 Div.2에서 볼 수 있을 것 같이 생겼다. 두 배열을 하나는 오름차순, 하나는 내림차순으로 정렬한 뒤 잘 구해주면 됐던 것 같다. C. D. 사각형 게임 (Small, Large) 오픈콘이라 두..

A. Subtle Substring Subtraction (00:04, +) 평소 A치고 어려웠다. 문자열의 길이가 짝수면 자명하게 선공이 다 지울 수 있고, 홀수라면 첫 글자를 남기거나 마지막 글자를 남기는 것이 최적이다. B. A Perfectly Balanced String? (00:14, +) B답게 쉬울 것 같아서 적당히 찍었더니 맞았다. 내가 한 가정은 '두 같은 알파벳 사이에 다른 모든 알파벳이 최소 하나씩은 있어야 한다' 이다. C. Palindrome Basis (00:18, +1) 팰린드롬의 수가 적당히 작기 때문에 \(O(NM)\)에 냅색을 써주면 풀 수 있다. D. Lost Arithmetic Progression (01:18, +1) 우선 예외 케이스를 잘 분석해서 0, -1에 대..

앳코더와 코드포스 글로벌 라운드가 있었다. AtCoder Beginner Contest 249 A. Jogging (0:05, +) *103 지문이 이상하게 쓰여 있어서 좀 헤멨다. 문제 자체도 평소 ABC A보다 어려웠다. B. Perfect String (0:07, +) *47 하라는대로 하면 된다. C. Just K (0:11, +) *528 이것도 지문이 조금 불친절하긴 했는데, 하라는 대로 완전탐색을 돌려주면 맞는다. D. Index Trio (0:30, +2) *983 인덱스가 같을 수도 있어서 식을 좀 생각해서 써주어야 한다. 예제가 앳코더답지 않게 불친절해서 많이들 틀리는 것으로 보였다. E. RLE (1:00, +) *1970 \(DP[i][j]\)를 i번째 글자까지 쓰고, 압축 길이가 ..

일정상의 관계로 slah007 선배와 둘이 진행하였다. 셋은 Latin America Regional Contests 2018을 사용하였다. ~00:06 A가 쉽다는 소식을 듣고 코딩 컴퓨터를 잡은 내가 바로 짰다. 실수 오차때문에 2번 틀리고, 입력을 string으로 받아서 AC를 띄웠다. ~00:08 뒤부터 문제를 보다 보니 M도 그냥 쉬웠고, 바로 짜서 맞았다. ~00:23 선배가 B가 쉽다고 하셔서 컴퓨터를 넘겼다가, 맞왜틀을 당하시길래 D를 금방 짤 수 있던 내가 들어가서 바로 짰다. ~00:31 같이 틀릴 이유가 없는 B 코드를 열심히 보았고, 내가 반례를 찾아서 if문 한 줄을 추가했더니 맞았다. ~00:45 M을 볼 때 슬쩍 봐둔 L을 선배한테 드렸는데, 굉장히 빨리 푸셨다. 그냥 뇌 비우..

카테고리 제목이 PS인데 너무 CP만 다룬 것 같아서 최근에 푼 백준 문제들 중 인상깊었던 것들을 정리해서 쓰려고 한다. 세미나를 준비하면서 백준에 있는 행렬 DP 문제는 거의 몽땅 푼 것 같다.. 이번에 정리할 문제들도 모두 여기에 속하는 것들이다. 2086 - 피보나치 수의 합, 11440 - 피보나치 수의 제곱의 합, 11778 - 피보나치 수와 최대공약수 모종의 정리들을 알거나 규칙을 찾으면 평범한 피보나치 수 문제로 환원할 수 있다. 2086은 규칙을 찾아서 풀었고, 뒤의 두 개는 적당히 검색해서 풀었다. 17401 - 일하는 세포 보자마자 풀이는 보이는데, 구현이 좀 귀찮은 문제이다. 신경써야 할 점은 1. 같은 행렬을 거듭제곱하는 문제들과는 다르게 교환법칙이 통하지 않는다. 2. 주어진 행렬..

열심히 풀고 기여를 하러 갔는데, 다들 내 풀이와 방향성이 다른 것 같았다. 정해가 시간 복잡도 면에서도, 난이도 면에서도 조금 더 낫지만 내 풀이도 의미가 있다고 생각해 적어보려 한다. 해당 풀이는 7469 - K번째 수를 PST로 푸는 방법을 트리로 확장시켜 적용한다. 간단하게 요약을 하자면, 인덱스 순으로 세그트리를 \(N\)개 만든 후 \(R\)번째 세그트리에서 \(L-1\)번째 세그트리를 뺀 값으로 세그 이분탐색을 해서 K번째 수를 찾는다. (이 과정에서 배열의 각 수에 대해 좌표압축을 해 주어야 한다.) 세그 이분탐색이란 왼쪽 자식의 합과 K를 비교해 K가 크면 오른쪽, 그렇지 않으면 왼쪽으로 가는 작업을 반복하는 것을 말하며, 세그트리를 여러 개 만드는 것은 PST를 통해 수행할 수 있다. ..

A. Red Versus Blue (0:02, +) R/(B+1)개와 R/(B+1)+1개를 적절히 배치해주면 된다. B. Bit Flipping (0:16, +) 앞에서부터 그리디하게 설정해주면 되는데.. 구현 미스가 나서 좀 오래 걸렸다. C. Line Empire (0:40, +) 끝 위치가 \(x\)라면, 그 전까지는 계속 옮겨주는 것이 최적이다. 이를 각 경우에 대해 계산해주면 된다. D. Reverse Sort Sum (1:06, +) 우선 주어진 배열의 평균을 통해 1의 개수를 구해준다. 이후, 뒤 원소부터 보며 자명하게 결정 -> 1의 개수에 따라 업데이트를 반복해주면 문제를 해결할 수 있다. Range Update Point Query 펜윅트리를 사용하면 \(O(NlogN)\)에 문제를 해..

A. Lacked Number (0:01, +) *22 B. Slimes (0:02, +) *41​ 생략 C. Dice Sum (0:05, +) *787 C번치고 어려워서 놀랐다. \(DP[i][j]\)를 i번째 주사위까지 봤을때 합이 j인 경우의 수로 정의하면 \(O(N^4)\) 정도에 문제를 해결할 수 있다. D. Range Count Query (0:06, +) *793 같은 숫자들에 대해 등장하는 인덱스를 벡터에 저장해 준 후 lower bound와 upper bound를 적절히 사용해 개수를 구해주면 된다. E. K-colinear Line (0:15, +) *1292 고려해야 하는 직선의 개수가 \(O(N^2)\)개이고, 이에 대해 \(O(N)\)으로 주어진 조건을 만족하는지 확인할 수 있다...

블로그 주인의 PS 경력에 대한 소개글입니다. 계속 수정됩니다.e-mail: leo020630@naver.com[프로필]BOJ- leo020630 (3818 Solved, Ruby IV - 2805, POSTECH #1)Codeforces - leo020630 (Max Rating : 2314, International Master)Atcoder - leo020630 (Max Rating : 2029, 1 Dan)CodeChef - leo020630 (Max Rating : 2358, 6★)Competitive Programming Hall of Fame: Leo JangICPCID: Leo Jang [소속][2018~2020] 경기북과학고등학교 3학년 졸업[2019] 경기북과학고등학교 알고리즘 동아리..

이번 주말은 유독 칠 대회가 많았다. 총 앳코더 2개, 코포 2개, 구글 코드잼 1A 라운드가 있었는데, 코드잼은 자느라 못쳤고, 앳코더는 (실력적으로) 못 쳤기 때문에 특별히 잘 친 2개의 코드포스 라운드를 정리해보도록 하겠다. Codeforces Round #781 (Div. 2) A. GCD vs LCM (0:00, +) 보자마자 답이 보여서 짜서 냈다. 덕분에 코포하면서 처음으로 500점을 먹을 수 있었다. ㅎㅎ B. Array Cloning Technique (0:05, +) 가장 많이 등장하는 수의 개수를 센 후, 적당히 2배씩 하면서 횟수를 구해주면 된다. C. Tree Infection (0:33, +3) 킹받는 그리디 문제이다. 우선 노드를 Sibling 단위로 묶으면 트리와 관계 없는 ..