BOJ 17317 이사의 증명 문제: 점 $P_1$, $P_2$, ... $P_N$이 주어질 때 $f(X)$를 점 $X$에 대해 $P_i$중 가장 먼 점과 가장 가까운 점의 거리의 합으로 정의하자. $min(f(X))$를 구하시오. Claim) $min(f(P_i)) = min(f(X))$ = $X$를 $P_i$ 중 하나로 정해도 그 최솟값은 전체 최솟값과 같다. Proof) $f(P_{opt}) = min(f(P_i))$ $f(X_{opt}) = min(f(X))$ $X_{opt}$에 대해 가장 가까운 점 $P_i$와 가장 먼 점 $P_j$. 삼각부등식에 의해 $\overline{X_{opt} P_i} + \overline{X_{opt} P_j} \geq \overline{P_i P_j}$ 증명은 $X..

https://www.acmicpc.net/problem/26035 PS는 원래 폰으로 하는거다. 추가) 이 문제는 우리 갓 https://www.acmicpc.net/user/heeda0528가 만든 갓 문제입니다. 모두 찬양하시기 바랍니다.

https://www.acmicpc.net/problem/25972 문제를 과대해석 하는 경향이 있다. 오 이거 재밌겠는데? 하는 생각이 들면 그렇게 문제를 풀어버린다. 정렬하면 모든 도미노는 인접한 도미노에만 영향을 준다.

https://www.acmicpc.net/problem/3679 3679번: 단순 다각형 첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌 www.acmicpc.net CCW 정렬하면 될 것이라는 추측 실제로 된다. 1. 왼쪽 아래 점 (기준 8개 다 된다. 아래 오른쪽, 왼쪽 위 등) 기준으로 정렬 2. ccw가 같은 마지막 t개(t>=1) 점들의 경우 순서를 뒤집어주자. = 거리가 가까운 것부터 이어야 하므로

https://www.acmicpc.net/problem/20295 난이도 기여 창에서 추천 받은 문제 심플 비트마스킹이 편하지만 배열을 써도 충분히 여유로울듯 하다. 1e5 * 20 * 5 = 1e7 1-based랑 0-based를 헷갈려서 디버깅 때 고생 좀 했다. 되도록 0-based로 통일하자. 이런식으로 디버깅 매크로를 만들어서 쓰는데 주석을 안 치고 제출하면 "시간초과"를 받는다. 로컬에서 디버깅하고 주석 안 쳐도 되게 만들었다. http://boj.kr/1b071128a8194d42bbf23c604971e9fa

https://www.acmicpc.net/problem/3176 이 문제를 아직까지 안 풀었었다니! sparse table 이용한 LCA 기본형 문제. HLD도 이용할 수 있다. LCA할 때 이런 식으로 i를 -1까지 보내면 한층 편하다. 코드가 못생겨지지만 편한게 장땡.

https://www.acmicpc.net/problem/13334 http://boj.kr/d7291475a4294aa58c892481968bf9e3 문제를 보자 말자 세그나 mergesort tree 풀이만 생각나서 고생했다. 골드2인데, 그게 정해일리도 없을 뿐더러, 구현이 빠른 풀이를 생각해보고 싶었다. 문제를 보면 2가지 접근이 기본적으로 생각난다. 스위핑 혹은 파라메트릭 서치. 이 문제의 경우 파라메트릭이 오히려 더 어렵다. 바로 스위핑으로 접근해도 된다. 위치를 받아서 선분 형태로 만들어주고 끝점 기준으로 정렬한 뒤 시작 점들만 관리해주면 된다. 현재 보고 있는 끝점을 b라 했을 때 지금까지 추가해준 시작점들 중에서 b-d 이상인 개수만 구해주면 된다. 시작점을 a라 하면 a도 정렬되게 관리..

http://boj.kr/943e1681a633468ea54da59124647d2d 공유 소스 보기 www.acmicpc.net 단조스택에 한 방 먹었다. 나였으면 i v[j] , v[i] == v[j] 인 경우 나눠서 세그로 비비고 복잡하게 쓰는 풀이만 떠올랐다. 스택.. 스택은 일단 단조 증가, 단조 감소 한 번 박아놓고 그때부터 명확하게 생각하는게 중요하다. '스택에 있는 값'에 대해 현재의 값을 보는 건지 현재의 값에 대해 '스택에 있는 값'을 보는 건지 알아내면 문제는 끝.

"문제를 잘 읽기" 얼리어답터가 아닐 경우, 친구 중 한 명만 얼리어답터면 되는줄 알았다. 이 문제는 모두 얼리어답터야 하므로 dfs 한 번만 돌리면 된다 http://boj.kr/0fe8012660474815898b5860116efc1e 친구 중 한명만 얼리어답터여도 되면 어떻게 풀어야 할까? N^2말고 N으로. N^2 문제를 만들면 사람들이 N으로 잘 풀어줄거다. “인터넷에서 원하는 답을 얻으려면, 질문 말고 틀린 답을 올리면 된다." – 워드 커닝햄 Cunningham’s Law: “The best way to get the right answer on the Internet is not to ask a question, but to post the wrong answer.”

https://www.acmicpc.net/problem/1533 http://boj.kr/42cd430fb1f94613bdc6b6d2feb6a7fd 인접행렬 거듭제곱이라는 개념을 사용해야 하는건 본대 산책 시리즈를 풀어봤으면 바로 보인다. 다만 길에 가중치가 있어 이를 적절히 1짜리 길로 나누어줘야 하는데, 각 길마다 정점을 새로 만들어주면 N = 10*10*5 = 500으로 행렬 곱셈을 할 때 시간이 너무 많이 걸린다. 따라서 각 정점마다 4개의 새로운 정점을 추가하는 방식으로 해결할 수 있다. 앞으로 바로 못 푼 문제나 신기한 아이디어를 사용하는 문제는 복습용 문제집에 저장해둔다. https://www.acmicpc.net/workbook/view/13241

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net http://boj.kr/d30f68e9ef95427789c8bf855081ed79 dp: 시작 행의 상태, 끝 행의 상태를 기준으로 O(N*4*4) DP다. 재귀 dp를 한 1년만에 짜는 듯하다. 노가다 케이스워크 오랜만에 하니까 재밌었다. 나는 원형이기 때문에 양쪽 끝 4개씩 4*4=16개의 상태를 사용했는데 한쪽 4개만으로 가능하다. https:/..

컴퓨터를 초기화할 때마다 필자도 이 글을 켜고 설정한다. 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++ 관련 확장 프로그램을 설치하라는 알림이 뜨는데, 그것..

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