Previous Story: https://howtoliveworldnice.tistory.com/673 As you'll know if you've read it, it's mostly my-own-thought. If you empty your brain while reading this, and get at least a good sentence or content, this article is a successful. It's to boring to find the IOR (Input Output Rate) of celebrities. Let me tell you again about the ideal IOR as a warm-up. In fact, most beginners follow the ..

지난 이야기: https://howtoliveworldnice.tistory.com/673 읽었으면 알겠지만 대부분 뇌피셜이다. 여러분이 뇌 비우고 읽다가 좋은 문장이나 내용 하나 건지면 이 글은 성공이다. 막상 실제로 유명인들의 IOR(Input Output Rate)을 찾아보려니 엄두가 나지 않았다. 몸풀기 겸, 이상적인 IOR에 대해 다시 한 번 말해보도록 하겠다. 사실 대부분의 초심자는 한 챕터를 배울 때 1.배우고(Input) 2. 적용하고(Output) 3. 피드백 받는다(Input)의 IOI 패턴을 따라간다. 따라서 I,I : O = 2:1의 IOR이 되어 전형적인 IOR이 된다. 누구나 쉽게 떠올릴 수 있다. 그러다가 시간이 지나면 '처음 배운 건' 너무나 먼 이야기가 되고 그 챕터 내에서..

First listen, then you will talk well. Read the papers, then you will know how to write one. The more you read the code, the better your code will be. Always watch professional's playstyle, then now you will be able to play better. How can you make a fun youtube video without even watching one? It's a quote I always hear no matter what field I enter. Chapter 1 of every self-development book abou..

먼저 잘 들어라, 그럼 너도 잘 말할 수 있다 논문 많이 읽는 사람이 좋은 논문을 쓴다 코드 리뷰를 많이 할 수록 코드의 질은 좋아진다 프로들이 운동하는 모습을 봐야 너도 프로답게 운동할 수 있다 평소 방송을 즐겨봐야 내 영상도 재미있게 편집할 수 있다 . . . 어떤 분야에 진입하든 항상 듣는말이다. 모든 화법 자기계발서의 1장에는 먼저 상대방의 말을 들으라는 이야기가 나온다. 그리고 나는 이 진부한 패턴에 다시는 그 분야 책을 쳐다보지 않았다. 듣고, 또 더 들어도 내 다른 사람들과의 대화에 만족스럽지 않았기 때문이다. 며칠 전에 "사람의 귀가 2개고 입이 1개인 이유가 뭔지 알아? 상대 말 2번 듣고, 너 말 1번 하라는거야" 라는 글귀를 보았다. 생물학적으로 근거가 없는 말이지만, 이 말은 그 당..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

컴퓨터를 초기화할 때마다 필자도 이 글을 켜고 설정한다. Python은 공식 홈페이지에서 설치 + Step A 만으로 완료된다. 목차 A. 에디터 설정 B. 컴파일러 설정 C. C/C++ 버전 설정 D. 실행방법 및 주의점 E. 추가적으로 설치하면 좋은 것 A. 에디터 설정 1. VSCode 다운로드 https://code.visualstudio.com/ 2. Code Runner 설치 https://marketplace.visualstudio.com/items?itemName=formulahendry.code-runner 3. Extension 설정에서 Run in Terminal 사용 가능 체크 4. 파일> 새 파일로 .c 파일을 만들면 C/C++ 관련 확장 프로그램을 설치하라는 알림이 뜨는데, 그것..

모든 문제는 명료함의 부재에서 온다

*The content is based on 2022 Fall EE205 MasterMethod Lecture. Master Method is a powerful black box for solving recurrences such as Divide and Conquer Method. Assumption: All subproblems have equal size. $T\left(n\right)$ is the function to analyze operation costs to solve problem size of $n$. Settings 1. Base Case: $\forall$ sufficeiently small $n$, $T\left(n\right) \le$ a constant 2. Recurren..

Fibonacci Sequence as Recursive Formula $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, \quad ^\forall n \ge 2$ Fibonacci Sequence as Matrix Multiplication Form $\begin{vmatrix} F_n \\ F_{ n-1} \end{vmatrix} = \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^{n-1} \cdot \begin{vmatrix} F_1 \\ F_0 \end{vmatrix}, \quad ^\forall n\ge 1$ Fast Recursive Powering for elements of Monoid Suppose we are calcul..

연습 주기를 바꿨습니다. 월화수목 셋은 4문제, 금토일 셋은 6문제 셋 제작자: pentagon03 A - 산업 스파이의 편지 B - 해킹 C - 시저 암호 D - 보안 업체 E - 수열과 쿼리 14 F - 여우 퀴즈 A. dfs + 에라토스테네스의 체 B. 우선순위큐로. 이를 구조화하면 다익이라고 하는데 다익 생각 안 나도 우선순위큐 쓰는게 당연해 보입니다 C. Step 1 원문을 쉬프트하는게 아니라, 거꾸로 암호문을 쉬프트합시다 Step2: 원문의 pi배열이 그대로이므로 각 쉬프트마다 빠르게 kmp를 쓸 수 있습니다~ D. Step1: 한 번 움직일 때 경로 상에 있는 모든 경유 점을 방문하는게 이득입니다. 즉 (start,start)구간에서 한 번 움직일 때마다 구간의 길이가 1씩 늘어나는 방식으로..

영진닷컴에서 진행하는 이벤트에 당첨되어 백엔드를 위한 GO 프로그래밍 책을 받았습니다. 아래는 파릇파릇한 새 책입니다. 디자인이 예뻐서 내용도 기대됩니다. 제가 매기는 책의 별점은 다음과 같습니다. 내용 4.9 / .5.0 구성/디자인 5.0 / 5.0 저는 개발보다는 컴퓨터 알고리즘 문제풀이에 훨씬 가중치가 많이 부여되어 있는 사람이므로 개발자나 개발입문자의 관점보다는 '새로운 언어에 관심이 있는, 취미로 코딩하는 사람'의 관점으로 책을 읽었습니다. 물론 책 제목에 '백엔드를 위한'이 붙어있으므로 "이 책 하나로 나도 백엔드 개발자?"라는 상상도 잠깐 했습니다. 어디까지나 상상입니다. 책의 내용, 구성, 그리고 실제로 배운 것 3가지에 대해 알아보겠습니다. 이 글은 계속 업데이트될 수 있습니다. UPD..

셋 제작자: surface03 A - LCM(1, 2, ..., n) B - Wiring C - 효율적으로 소 사기 D - The Bus E - 퀼린드롬 (Hard) F - Drum Decorator (Large) G - Justice for All 오늘, 내일 휴식 A: B: C: D: E: F: G:

셋 제작자: imtore A - 게임 닉네임 B - 마법의 문자열 C - 복붙하기 D - 가장 긴 공통 부분 문자열 E - 가장 긴 공통부분 팰린드롬 F - 적절한 문자열 문제 G - IQ 테스트 H - Sequence Conversion 2 I - 홀수 싸이클 A~F는 문자열 셋이고 G,H,I는 내가 참여하지 않았던 어떤 셋의 imtore님의 업솔빙이다. (이 3문제 빼고 다 업솔빙하셨다고 한다 :god:) A: 트라이 기본. 문자열의 끝을 나타낼 변수를 따로 정해줘야 합니다. http://boj.kr/2d9a845d3d0a4ab789996d416312ff7f B: 첫번째 단어는 고정시킬 수 있습니다. (하면 빠릅니다.) 가능한 모든 순열에 대해 이어붙인 문자열을 검사하면 됩니다. 방법1: 문자열을 $..

https://www.acmicpc.net/problem/4786 풀 때 도움 되는 몇가지 사실. 0. 표기: worker 수를 W, production 수를 P, 그 턴에서 적 수를 A 1. P랑 W의 관계를 파악하기 위해서 일단 모든 A를 0으로 가정할게요. 2. 각 턴에서 만들 수 있는 최대 army는 min(P,W)에요. 3. 마지막 두 턴에서 최대로 만들 수 있는 army의 수는 마지막 2번째에서 P,W를 기준으로 항상 min(P,W)+W에요. 증명은 케이스 나눠서 하면 돼요 4. 그러면 결국 마지막에서 3번째 턴까지 min(P,W) + W를 최대화 시키는게 목표가 되는데 여기서 그리디가 들어가요. 생각하기 쉬운게 P가 W보다 클 경우 W를 2배하고 W가 P보다 클 경우 돈을 P를 W로 키우는데..

셋 제작자: sean9892 A - 동차 수열 B - 핑크 플로이드 C - 복도 뚫기 D - Xor Maximization E - 성싶당 F - 2,3 거듭제곱의 합 G - XOR과 집합과 트리와 쿼리 H - 다각형 자르기 A: 모든 2x2 부분행렬만 살펴보면 됩니다. 각각의 독립인 위치에 대하여 버블 정렬 느낌으로 2개씩 교환했을 때도 값이 바뀌지 않아야 때문. https://www.acmicpc.net/source/share/fa847a663c5a45b99ac4074096e15d89 B:MST를 만들어주면 되는걸 알 수 있습니다. MST를 만드는 과정에서 가장 작은 경로를 고르기 때문. https://www.acmicpc.net/source/share/510077d7aed645fab6b9e1d3e1f..

0816부터 시작 클래스 5 더보기 클래스 5 안 푼 문제 중에 귀찮은 문제들이 많다 9328 열쇠 흔한 비트마스크 bfs 문제인줄 알았는데 열쇠 개수가 100개 문을 만나면 열쇠가 있는 경우 바로 큐에 삽입하고, 없다면 문 리스트에 삽입한다. bfs를 돌리는데 열쇠 하나를 새로 얻으면 지금까지 봤던 문 리스트에 있던 문들을 큐에 삽입한다. 맵 테두리를 0으로 감싸주면 single source bfs가 가능해서 구현이 훨~씬 편하다. 랜디 더보기 0816 A - 물병 B - 고층 건물 C - 방 번호 D - 롤러코스터 E - 큐빙 F - 스타 대결 A: 이진법으로 나타냈을 때 비트의 개수가 K개 이하인 N 이상의 최소 자연수를 구하면 됩니다. N이 작아서 __buitlin_popcount(X)로 반복문 ..

8월 5일부터 일정이 있어서 PS를 당분간 못할 가능성이 높다. 1557 제곱 ㄴㄴ 더보기 기회가 되서 풀게 됐다. 옛날엔 감도 안잡힐 정도로 어려운 문제였는데 지금은 쉽게 풀이가 떠오르는게 기분이 매우 좋다. 내 풀이는 DB 풀이인데 Segmented Sieve를 사용한다. https://www.acmicpc.net/problem/1016 를 풀고 나면 적당한 min, max만 찾으면 된다는 생각을 할 수 있다. 그 min,max를 구하기 위해 구간을 적당한 블록(2*10^6 정도)로 나눠주고 각 블록의 제곱 ㄴㄴ수의 개수를 구하는 것이다. 미리 전처리를 해놓고 (블록의 크기에 따라 다르겠지만 나의 경우 2000개의 수를 저장) 구간을 찾은 뒤 만들어놓은 체로 K번째 제곱ㄴㄴ수를 구해주면 된다. 내 풀..

UCPC에서 맞고 나니 정신이 차려져서 게임도 끊고 PS에 다시 집중하기 시작했다. 브론즈5 올솔 더보기 모든 제출은 Python 및 Text로 했다. 비하인드를 말하자면 고등학교 문제 수 랭킹이 2등으로 밀려 있길래 랭킹작을 했다. 문제 빨리, 정확히 푸는 연습하는 겸, 파이썬 연습하는 겸 밀었다. # import sys # input = sys.stdin.readline N=lambda:int(input()) M=lambda:list(map(int,input().split())) P=print # from functools import reduce if __name__ == "__main__": A = N() 이건 내 파이썬 문제풀이 템플릿. 풀면서 reduce, filter, map을 굉장히 많이 ..

2409 더보기 백준에 있는 USACO 중 가장 오래된 문제 17일날 꽂혀서 계속 풀고 dfs+커팅이라는 정보를 얻어서 ( = 완전한 해답이 없다) 커팅 방향으로 계속 풀이를 고쳐나가는중이다. UPD: 7/21 AC 어찌저찌 풀이를 짜다가, dfs 탐색의 횟수를 제한시키는 방법을 떠올리게 되었다. 커팅이라 보기에도 애매하고 이게 무작위 데이터에 대해 돌아갈지 또한 전혀 정확하지 않은 방법이지만 배열을 랜덤셔플하면 최소한 사람이 추가할 수 있는 데이터 내에서는 돌아갈 수도 있다는 생각이 든다. 내가 푼 시점에 총 3사람이 풀었더라. 분명 문제 풀기 전에 봤을 때 한 사람이 1730ms? 이정도로 통과해있었는데 내가 풀고 나니 사라져 있었다. 계정을 지웠거나 지워진건가? 다른 두 사람의 코드를 터트리고 싶다..

15940 더보기 본선 팀연습 때 jjaewon9와 함께 해결한 문제. 트리에서 각 간선에 대해, 그 간선이 나누는 두 서브트리의 지름을 빠르게 구해 문제에서 원하는 최댓값을 갱신해주면된다. 루트를 하나로 고정해두면 이제 루트가 아닌 각 정점에 대해 그 정점이 루트인 서브트리의 지름과, 이 서브트리의 여집합 (정점의 부모로부터 이어진) 트리의 지름을 구하면 된다. 서브트리의 지름을 구하는 방법 중 dp 방식이널리 알려져 있는데, 각 서브트리에서 루트로부터 가장 먼 정점과의 거리를 저장해 두고 max( max(dp(자식)), max(가장 긴 2개 다리 길이의 합))을 구하면 된다. 아래 지름을 dpD, 위 지름을 dpU에 저장하자. dpU를 구하는 방법도 dpD와 비슷한데, 정점과 부모를 고정하고 생각하면..

1년 간의 휴식을 끝나고 참가하는 첫 대회 icpc팀원인 sean9892의 제안으로 jjaewon9와 팀을 이루었다. 셋 다 약 1년의 휴식을 가지고 있어 걱정반, 오랜만의 PS라 설레임 반이였는데 팀원들이 잘 이끌어준 덕분에 연습과 예선을 성공적으로 마무리할 수 있었다. 팀명을 비롯한 대회 참가 내용의 99%는 아래 두 글의 합집합에 있다. https://sean9892.tistory.com/22 https://jjaewon.tistory.com/29

https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 이 문제는 Exchange Arguments의 전략을 쉽게 발상할 수 있는데, (문자열 A,B에 대해 AB>BA?) 인접한 것끼리만 교환한다고 생각하면 AB > BA 일 경우 X AB Y > X BA Y 이기 때문에 인접한 걸 계속 이득이 되도록 교환해나가면 최종적으로 가장 이득인 상태가 되는 것을 알 수 있다. 이는 결국 버블정렬을 시행하는 것과 같은데 N lo..

문제풀이 사이트(집중) Codeforces 백준 UCPC 기출 ACM-ICPC ACM-ICPC 서울 리저널 튜토리얼 https://www.geeksforgeeks.org/how-to-prepare-for-acm-icpc/ https://blog.shahjalalshohag.com/topic-list/ https://usaco.guide/ 라이 알고리즘/문제 목록 https://cp-algorithms.com/ https://csacademy.com/contest/archive/ https://cses.fi/problemset/ 동아리 2022 Spring Worksheet https://codeforces.com/gym/103470 https://codeforces.com/gym/103430 https:..

상위 100개 문제를 다이아 이상의 문제로 채웠다! 공부하고 연습한 기록이 이만큼 쌓여서 뿌듯하다. 이제는 사고력을 키워보자. 스스로 사고해서 문제를 풀어내는 것이 재밌어지는 그날까지 연습!

https://codeforces.com/blog/entry/91363 I compiled a list of almost all useful blogs ever published on Codeforces [update: till 04.06.2021] - Codeforces codeforces.com 너무 좋다! ㅎㅎ 코드포스 공부할 때 정말 최고

http://kocw.or.kr/home/search/kemView.do?kemId=1346284 KOCW에 이런 좋은 자료가 있다는 것에 감동 받았다. 6장 매칭과 커버에 좋은 내용이 많다.

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를 만든다. 포인터를 이용해서 구현했고, 별도로 좌표압축 또한 하지 않았다. 포인터 안쓰는 구현으로 바꾸면 더 빨라진다 풀면 보세요: ..

구간이 올바른 괄호문자열인지 판정하는 쿼리, 구간 문자 뒤집기 '(' ')' 업데이트 쿼리 모두를 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.01.23 - [Problem Solving] - 머리로만 문제 풀기 글에 있는 문제들 중 세그 카테고리 문제들을 구현해봤다. 9623 부분 수열의 길이 처음에는 플4라는 게 믿기지 않았던 문제. 업데이트가 없기 때문에 누적합 배열로 구간의 합을 나타낼 수 있는 것이 핵심. 기본적으로 스위핑인 것은 잘 보인다. 끝점 i를 고정시키고 시작점 j+1중 가장 뒤에 있는 것을 찾는 느낌 $0