다이아 1일1제

2021년 7월 31일까지 PS에서 실시함. https://www.acmicpc.net/group/9175 p.s) 원래는 개인적으로 진행하던 프로젝트였으나, 때마침 cgiosy와 뜻이 맞아 격일로 플*2 +다5*1 // 플*1+다5*2 문제풀이를 실시한다. Routine: 매일 아침 저녁 내일 문제 3개 프린트 + 다음 날 문제 풀이 20210531: 10124 다5 더보기 Merge Sort Tree와 Small To Large의 아이디어를 차용해서 풀었다. O(N log^2 N) 각 Value 1~N에 대한 인덱스를 저장해서 벡터를 만들고 Merge Sort Tree를 만든다. 포인터를 이용해서 구현했고, 별도로 좌표압축 또한 하지 않았다. 포인터 안쓰는 구현으로 바꾸면 더 빨라진다 풀면 보세요: ..

2021.05.31

올바른 괄호 세그먼트 트리

구간이 올바른 괄호문자열인지 판정하는 쿼리, 구간 문자 뒤집기 '(' ')' 업데이트 쿼리 모두를 O(log N)에 처리하는 세그먼트 트리 C. Sereja and Brackets : 업데이트 X 17407 괄호 문자열과 쿼리 : 점 업데이트 19851 버거운 버거: 구간 업데이트 일반적으로 사용하는 세그 트리의 노드의 종류는 2가지다. 레이지 값은 별도로 저장한다고 가정한다. 1. 구간합과 최소,최대 저장 앞서 '('를 1, ')'를 -1로 모델링했을 때 [a,b] 부분문자열이 올바른 괄호문자열일 조건은 $Sum([a,b]) = 0$ 이고 $Min(Sum([a,i])) >= 0$임을 언급했다. 이를 이용하기 위해 노드에 구간합과 최솟값을 저장한다 만약 구간의 문자를 뒤집을 경우 최솟값이 구간합의 최댓값..

2021.05.28

5월 26일#세그먼트 트리 재활

세그 트리 문제를 다시 풀고 있다. 구현에 초점을 맞췄음. 2021.01.23 - [Problem Solving] - 머리로만 문제 풀기 글에 있는 문제들 중 세그 카테고리 문제들을 구현해봤다. 9623 부분 수열의 길이 처음에는 플4라는 게 믿기지 않았던 문제. 업데이트가 없기 때문에 누적합 배열로 구간의 합을 나타낼 수 있는 것이 핵심. 기본적으로 스위핑인 것은 잘 보인다. 끝점 i를 고정시키고 시작점 j+1중 가장 뒤에 있는 것을 찾는 느낌 $0

2021.05.26

주세혁 VS 티모 볼

정말 주세혁은 레전드다.. 9년 전 월드컵 경기. 저 때가 그들의 최정점이 아니라면 언제일까 주세혁의 수비수 플레이는 스스로 기회를 만들어나간다는 점에서 정말 멋지다고 생각한다. 저렇게 빠른 공을 여유롭게 받을 수 있을 때까지 얼마나 많은 연습을 했을까 탁구를 한 번이라도 쳐봤다면 저렇게 수비하는 게 보이는 것보다 수백배 어렵다는 사실을 깨달을 것이다. 아무 회전 없이 공을 넘기는 데만 해도 온 신경을 기울여야 하는데, 저렇게 빠른 스매시 / 상회전 걸린 드라이브 등을 자유롭게 방향까지 조절해가며 커트를 친다. 한편 티모 볼 또한 대단한 선수이다. 티모 볼은 독일 선수로, 중국이 점령하고 있던 현대 탁구에서 세계 1등까지 찍었다. 당시 유럽에서 영웅 취급을 받았다고 ㅎㅎ 잘생김 + 매너 있는 행동으로 인..

2021.05.26

5월 25일 #금광, 전개도

최근 희자님이 금광을 풀기 위한 연속합 세그먼트 트리를 공부하셨다고 한다. (heeda0528) 볼 때마다 풀고 싶었지만 귀찮아서 넘겨왔던 ㅋㅋ 그런 문제다. 그런데..! 희자님 코드가 너무 깔끔한 나머지 최대 연속합 세그를 구현해보고 싶은 욕구가 생겼다..! 30분 정도 시간 투자해서 2달만에 세그를 짜봤다. - 코드 잘된 구현을 봐서 그런지 생각보다 간단했다! 그리고 내가 왜 그렇게 이 연속합 세그를 귀찮아 했는가 생각을 해보니.... 작년 이맘때 2020년 3월 코드업 1등님한테 한 질문 中 3일을 꼴아박아서 꾸역꾸역 연속합 세그를 만들어냈는데 보다 시피 코드 상황이 벌써 끔찍하다. 세그 3개라니 OTL 이제 그 당시에는 뿌듯해서 굳이 새로운 코드를 찾아보지는 않았는데, 이게 내게 정말 큰 충격으로..

2021.05.25

5월 22일 #JOI 깃발

JOI 깃발 캬 ㅋㅋㅋㅋㅋ 오늘 정말 행복하다! 신이 많이 도와주시는군 >ㅇ< 기차 타면서 내내 이 문제의 구현에 대해 생각했는데 저녁 10시 25분 경에 드디어 구현에 성공했고, 3484ms 라는비범한 시간에 내 코드가 1트만에 통과하는 기적을 목도했다. 구사과님한테 어그로 끌려서 이 문제를 풀게 되었는데 끌리기 정말 잘했다는 생각이 든다!! 메모 1. 적어도 1개 이상이라는 조건은 매우 더럽다. 여사건을 이용하자. 2. 비트 필드 dp를 할 거다. M개의 비트를 들고 다니자. 3. 현재 넣을 알파벳이 'J' 나 'O'라면 위에는 아무 상태나 넣어도 된다. 4. 현재 넣을 알파벳이 'I'라면 바로 위가 'JO'인 상태는넣으면 안된다. 5. J와 O를 같은 비트(0)으로 취급할 건데, 맨 첫번째 비트는 ..

2021.05.22

5월21일 #Palindrome DP

1. Palindrome DP 팰린드롬https://www.acmicpc.net/problem/1243 팰린드롬의 개수https://www.acmicpc.net/problem/1204 팰린드롬 문장https://www.acmicpc.net/problem/1054 N개의 문자열을 붙여 만들 수 있는 팰린드롬의 개수를 구하는 유형. 1054는 단어를 1번씩만 사용 가능한 것이 차이점이다. dp 상태를 정하기에 앞서 관찰을 해보면 항상 dp는 한 단어를 정하고 이를 사용하는데서 시작한다. 단어를 앞/뒤에 번갈아 붙이게 된다. 첫 단어 이후부터는 조건이 생긴다. 가령 abcd라는 단어를 골라서 앞쪽에 붙였다고 하면 뒤쪽에 dcba를 접미사로 가지는 문자열이나 dcba의 접미사인 문자열만 뒷쪽에 붙일 수 있다. ..

2021.05.21

5월 20일 #Bit Scrolling DP

Bit Scrolling DP 문제들 밀기 정말 재밌는 알고리즘이다. 두부 모판 자르기가 입문으로 가장 좋은 듯 감 안 오면 휘님 블로그 풀이 보세요~ https://www.acmicpc.net/problem/10937 10937번: 두부 모판 자르기 KOI 두부 공장에서 만들어내는 크기가 N × N (N ≤ 11)인 두부모판이 있다. 이 모판을 1×1 크기의 단위두부가 2개 붙어있는 형태의 포장단위(즉, 1×2 혹은 2×1 크기)로 잘라서 판매한다. 그런데 두부 www.acmicpc.net https://code.sasa.hs.kr/problem.php?id=2143 SASA OJ discuss3 세종이는 자신의 동생, 제인이와 블록을 채우는 놀이를 하고 있다. 세종이는 제인이의 두뇌를 말랑말랑하게 만..

2021.05.20

탁구 핵심 전략 10가지

*Reference의 번역과 필자의 분석이 담긴 글입니다. 글을 인용하거나 공유할 때는 이 글의 주소를 맨 위에 표시해주시기 바랍니다. 감사합니다. 1. 공의 회전을 분석한다 임팩트 순간에 상대방의 라켓의 이동방향을 본다. (관찰자가 상대편의 라켓을 봤을 때) 아래에서 위로 => 상회전 위에서 아래로 => 하회전 왼쪽에서 오른쪽으로 => 왼쪽으로 휘어진다 오른쪽에서 왼쪽으로 => 오른쪽으로 휘어진다 손목 스냅과 사선 방향 타격은 횡회전이 섞인 상회전, 하회전 공을 만든다. 상대방이 전면으로 공을 빗겨 칠 때, 라켓이 공 오른쪽에 있을 경우는 공이 왼쪽으로 휜다. 라켓이 공 왼쪽에 있을 경우는 공이 오른쪽으로 휜다. *공의 방향는 임팩트 방향과 관련이 있다. ($\vec F = m\vec a$). 특히 서..

2021.05.19

한글로 파이썬 코딩하기

파이썬에 '한글 변수명'을 사용 가능하다는 사실을 알고 있는가? 이 사실을 망각하고 있다가, 기억나서 당장 BOJ 1000번 A+B 문제를 풀어보았다. def 입력(): return input() def 출력(변수): print(변수) def 맵(함수,리스트): return map(함수,리스트) def 정수화(변수): return int(변수) 에이,비 = 맵(정수화,입력().split()) 출력(에이+비) 코드포스할 때 미리 자주 사용하는 함수들을 템플릿화 시켜놓는 것처럼 한글 템플릿을 미리 만들어놓으면 한글 프로그래밍도 더 이상 꿈이 아니다. ㅋㅋ!

2021.05.19

5월 19일 PS일지 #Class 1,2,3 금장

1. Class 3까지 금장 Class 3의 남은 문제들을 전부 해결하므로써 금장을 땄다. 2. 0/1 BFS 기억할만한 요소 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 0/1 BFS 문제로 접근했다. 그리고 0/1 bfs를 그동안 잘못 구현하고 있었다는 사실을 깨달았다. 가중치가 0 또는 1뿐이므로 0의 가중치를 가진 간선을 연결할 때는 dq의 front에, 1의 경우는 dq의 back에 p..

2021.05.19

5월 17일 PS일지

1. Class 2 남은 문제들을 땀 자투리 시간을 쓰면 굉장히 많은 일들을 할 수 있다. 생각보다 오래 걸리기는 한다. 실버 문제를 10분씩 걸림. 2. KOI 수상 확인 동상. 아쉽다. 미친 듯이 아쉽다. 옛날처럼 내 자신에게 화가 나고 그러지는 않다. 다른 내신 과목들을 챙기기 시작했고, 난 그걸 실천했으니. 다시 내가 좋아하는 PS 시작할거고 ACM ICPC 국대를 노린다.

2021.05.17

PS 일지

1. PS 다시 시작 삶의 활기를 되찾기 위해 PS를 다시 시작한다. //Always Do Your Best Ku! #include using namespace std; #define all(v) (v).begin(),(v).end() #define nl '\n' #define sp ' ' using ll = long long; using pii = pair; #define dbg(X) cerr

2021.05.16

Slope Trick - 함수 개형을 이용한 최적화

Special Thanks to Cgiosy Slope Trick: 함수 개형을 이용한 최적화 백준 13323 BOJ 수열 1 풀이 백준 13324 BOJ 수열 2 풀이 *20210513 수정#1 2021/05/13 정보과학세미나 시간에 보고서 및 발표자료의 내용으로 사용함. WhiteBoard Tutorial BOJ수열1 BOJ수열2

2021.05.13