Everything
-
[요약] ICPC 전략 가이드
https://people.cs.uchicago.edu/~borja/pubs/sigcse2016-programming-contests.pdf 이 글은 Aaron Bloomfield와 Borja Sotomayor의 "A Programming Contest Strategy Guide"를 읽고 한국어로 요약한 내용입니다. 핵심을 간단하게 전달하기 위해 필자의 해석이 담겨 원문과 다른 내용이 있을 수 있습니다. 세줄 요약 저자는 북미 대학 ICPC 코치들이다. 1999년 이후로 한 번도 북미 출신 대학이 우승 못하고 항상 러시아 / 중국 / 폴란드만 우승한다는 사실에 안타까움을 금치 못한다. 따라서 "어떤 팀들이 ICPC에서 활약하는가"를 자신들의 월드파이널(줄여서 월파) 코치 경험을 통해 사례 기반 연구하여 ..
2024.04.02 16:17 -
USACO US Open 2009 Gold 3 - Tower of Hay
USACO US Open 2009 Gold 3 - Tower of Hay BOJ 6116 케이크 1st Step First, we can consider a greedy approach. By the following perspective: "lower the last floor, better it is"So we greedily choose the lowest last floor possible. (e.g. the last floor consists of only one bale) ex) 9 1 2 4 7 => 9 / 1 2 4 / 7 However we can find out this is wrong. Consider "3 3 1 2". choosing only '2' at the last event..
2024.02.23 17:03 -
백준 17399 트리의 외심 - 정당성 증명
https://acmicpc.net/problem/17399 트리 위 노드 a,b,c의 외심을 찾는 문제. 외심은 정의는 다음과 같다. 1. 동일성 -> dist(a,b) = dist(b,c) = dist(c,a) 2. 최소성 a와 b의 가장 가까운 중점을 M이라 해보자. M에서 a와 b쪽이 아닌 다른 방향 (부모 혹은 자식)으로 간 것들도 모두 a와 b의 중점이 될 것이다. 거리를 d라 하자. dist(M,c) = d라면 정답은 그대로 M이된다. (다른 방향으로 옮기면 d가 증가한다.) dist(M,c) != d라면 M을 적당히 옮겨서 c와의 거리를 맞춰야 한다. 적당히 옮겨서 외심 M이 존재한다고 가정하자. 놀랍게도 이때의 M은 (a와 c의 중점) 혹은 (b와 c의 중점) 중 하나다. 만약 M이 (a..
2024.02.11 22:08 -
백준 단계별로 풀어보기 완.
컨벡스헐부터 정체되어 있던 백준 단계별 풀어보기를 2024-02-05 오늘 끝냈다. PS를 제대로 하기로 다짐한 사람이라면 단계별로 풀어보기부터 강의 듣듯이 빠르게 배운 후 OI / ICPC 스타일 문제를 풀어보는 것도 하나의 가장 효율적인 방법이라고 생각한다. 하나의 Tool Box를 다 채우고 시작하는 느낌.
2024.02.05 12:08 -
Min Cut과 Max Flow와의 관계
Link to original note: [[Flow Graph]] Cut은 Flow Graph에서 정점 s에서 t까지 가는 유량이 없도록 어떤 간선들을 자를 때, 그 간선들의 집합을 의미한다. 이때 Min Cut이란 간선 용량의 합이 최소가 되는 집합을 의미한다. 먼저 모든 flow f에 대하여 모든 cut C와의 관계를 알아보자. |f| t flow는 A->B flow의 크기와 똑같고, 이는 A->B 용량보다 작거나 같으므로 |f| e.g f(u,v) V-S로 향하는 간선은 없다. 따라서 모든 V-S -> S 간선만 보자. V-S에 속한 정점을 v, S에 속한 정점을 u라고 할 때 1)v -> u가 역간선일 경우 u->v가 존재하면 안되므로, u->v의 여유 용량은 0이다, 즉 f(u,v) = c(u..
2024.02.03 00:21 -
C/C++코드를 빠르게 고치기 위한 체크리스트
체크리스트 대부분의 IDE에서는 컴파일 에러 이유를 보여줍니다. 모든 실행문 끝에는 세미콜론을 적었나요? 지금 사용한 변수를 선언했나요? 중괄호가 열렸다면, 닫혀야 합니다. '들여쓰기’를 맞추면 코드가 눈에 보입니다. 'A’와 A는 다릅니다. main 함수 안에 있는 변수는 자동으로 초기화되지 않습니다. scanf에 들어가는 인자들은 주솟값이어야 합니다. &를 붙였나요? scanf에서 공백과 줄바꿈 문자를 넣지는 않았나요? scanf/printf에서 형식 지정자를 잘 맞췄나요? 문제의 입력과 출력 부분, 조건을 다시 한 번 꼼꼼히 읽어보세요. 자료형을 확인하세요. 실수 계산을 정수 계산으로 대체할 수 있나요? 배열 인덱스를 확인하세요. 배열 크기는 늘 넉넉하게 잡는 것이 편합니다. 함수가 제대로 동작하지..
2023.10.29 14:21 -
28031 Milk Sum
Link to original note: 2023-10-26 목 10:34:07 종이에 생각중 10:40:31 문제 요약 ${A_{i}}$ 가 있을 때 적당한 순서로 배열해서 $$S = \sum_{i=1}^{n}{i*A_{i}}$$ 를 maximize 해야 한다. 이제 $Q$개의 쿼리가 들어온다. 쿼리 $i ; j$는 $A_i$를 $j$로 바꿨을 때, $S$의 최댓값을 구하고, $A_i$를 원상복구 시키는 것이다. 문제 풀이 당연히, 그리디 하게 ${A_{i}}$ 를 단조 증가하도록 바꾼 ${B_{i}}$ 를 관리하면 된다. ${B_{i}}$ 에서 최댓값이 나오기 때문이다. 편의 상 $B_{0}=-\infty, B_{n+1} = \infty$ 로 두자. $id_{i}$를 $A_{i}$의 $B_i$에서의 ..
2023.10.26 22:55 -
Android Studio 설치 중 무한부팅 블루스크린: DRIVER_UNLOADED_WITHOUT_CANCELLING_PENDING_OPERATIONS, aehd.sys
2023/08/09 컴퓨터 관점에서 섬뜩한 일이 있었다. 아예 무한 BSOD (블루스크린) 상황에 빠진 것. 일반적인 안전모드 방법도 전혀 먹히지 않았다. -> "Startup Settings" 이 버튼이 없음. 이러한 화면 DRIVER_UNLOADED_WITHOUT_CANCELLING_PENDING_OPERATIONS aehd.sys 상황을 분석하기에는 시간이 너무 많이 들어서 사건 발생부터 해결까지 시간 순으로 설명하겠다. [문제 상황] 1. Android Studio 설치 이 과정에서 aehd 2.0이 깔림. https://developer.android.com/studio/run/emulator-acceleration?hl=ko Android Emulator의 하드웨어 가속 구성 | Android..
2023.08.09 17:12 -
Notion Site에 Custom Domain 넣기
1. 그대로 따라한다. https://stephenou.notion.site/stephenou/Fruition-Free-Open-Source-Toolkit-for-Building-Websites-with-Notion-771ef38657244c27b9389734a9cbff44 Fruition: Free, Open Source Toolkit for Building Websites with Notion If your site doesn't work, please read this section. stephenou.notion.site 2. Cloudflare DNS Record에 2가지 추가 (1) CNAME - www - 도메인 이름 (2) CNAME - 도메인 이름 - notion.so 후기) 도메인 연결..
2023.07.29 06:26 -
[VSCode] Code Runner에서 파일 명 공백과 java class 인식 오류 해결
일단 Extensions - Code Runner - Settings - Executor Map by File Extension - Edit in settings.json 버튼을 눌러 settings.json 파일에 진입하자. 1. 파일 명 공백 문제 문제 원인: Powershell에서 실행할 때 $dir$fileNameWithoutExt 이 부분이 ""으로 묶여 있지 않아, 가령 파일명이 "test file"일 경우 .\test file 로 인식 되어 문제가 생긴다. 이게 두 변수가 붙어 있어서 단순히 ""을 바깥쪽에 묶어주는 것으로 해결되지 않으므로 settings.json의 "code-runner.executorMap"의 해당하는 언어의 부분을 ex) cpp "cpp": "cd $dir && g++..
2023.07.14 01:02 -
[BOJ 17371] 이사 | 증명
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..
2023.01.07 16:26 -
Chat GPT: How to be happy 2022.12.10 22:55
-
About Me
안녕하세요, pentagon03입니다. 알고리즘 프로그래밍을 즐깁니다. Email: pentagonkr@gmail.com
2022.12.07 00:44 -
코드업 KOI 문제 (DP) 문제집 올솔브
고등학교 때 처음 보고, 굉장히 오랫동안 풀고 싶어했던 문제들입니다. https://www.acmicpc.net/problem/2625 2625번: DNA유사도 모든 생물의 DNA 서열은 A, C, G, T 네 개의 문자로만 표현된다. 한 DNA 서열에서 두 문자의 거리 는 두 문자 사이에 있는 문자들의 개수이다. DNA 서열의 부분서열은 DNA 서열에서 몇 개의 문자를 제 거 www.acmicpc.net 이 가혹한 문자열 문제에 가로막혀 오랫동안 생각하지 않고 있다가, 북마크를 보고 다시 떠올려 오늘 해결했습니다. 더보기 기본적으로 최장길이는 O(N^2K^2) dp를 통하여 LCS/편집거리와 비슷하게, 쉽게 구할 수 있다. 한 단계 발전시켜 한 방향으로 덱이나 누적합 등을 사용하면 O(N^2K)에 구할..
2022.12.05 19:21 -
공지사항 2022.12.01
1. 블로그 이름 변경 비키라의 세상 => Pentagon 굳이 다른 닉네임 사용할 필요성을 못 느껴서 드디어 통일합니다. 2. 휴식 뻘글만 늘어나고 블로그에 발전은 없어 당분간 정기적인 글을 올리지는 않습니다. 제가 다시 공개적인 글을 적는 날은 뚜렷한 주관이 생겼을 때입니다. 늘 하던 것처럼 재밌는 일 생기면 글 적습니다. 3. 연락처 연락은 pentagon03@kaist.ac.kr로 주세요.
2022.12.01 21:33 -
[BOJ 26035] “컷” $0101$
https://www.acmicpc.net/problem/26035 PS는 원래 폰으로 하는거다. 추가) 이 문제는 우리 갓 https://www.acmicpc.net/user/heeda0528가 만든 갓 문제입니다. 모두 찬양하시기 바랍니다.
2022.11.18 21:33 -
[BOJ 25972] 도미노 무너트리기 "컷"
https://www.acmicpc.net/problem/25972 문제를 과대해석 하는 경향이 있다. 오 이거 재밌겠는데? 하는 생각이 들면 그렇게 문제를 풀어버린다. 정렬하면 모든 도미노는 인접한 도미노에만 영향을 준다.
2022.11.17 18:04 -
[BOJ 3679] 단순 다각형 "컷"
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) 점들의 경우 순서를 뒤집어주자. = 거리가 가까운 것부터 이어야 하므로
2022.11.17 11:24 -
[BOJ 20295] 사탕배달 "컷"
https://www.acmicpc.net/problem/20295 난이도 기여 창에서 추천 받은 문제 심플 비트마스킹이 편하지만 배열을 써도 충분히 여유로울듯 하다. 1e5 * 20 * 5 = 1e7 1-based랑 0-based를 헷갈려서 디버깅 때 고생 좀 했다. 되도록 0-based로 통일하자. 이런식으로 디버깅 매크로를 만들어서 쓰는데 주석을 안 치고 제출하면 "시간초과"를 받는다. 로컬에서 디버깅하고 주석 안 쳐도 되게 만들었다. http://boj.kr/1b071128a8194d42bbf23c604971e9fa
2022.11.15 11:42 -
[BOJ 3176] 도로 네트워크 "컷"
https://www.acmicpc.net/problem/3176 이 문제를 아직까지 안 풀었었다니! sparse table 이용한 LCA 기본형 문제. HLD도 이용할 수 있다. LCA할 때 이런 식으로 i를 -1까지 보내면 한층 편하다. 코드가 못생겨지지만 편한게 장땡.
2022.11.15 11:07 -
[BOJ 13334] 철로 "컷"
https://www.acmicpc.net/problem/13334 http://boj.kr/d7291475a4294aa58c892481968bf9e3 문제를 보자 말자 세그나 mergesort tree 풀이만 생각나서 고생했다. 골드2인데, 그게 정해일리도 없을 뿐더러, 구현이 빠른 풀이를 생각해보고 싶었다. 문제를 보면 2가지 접근이 기본적으로 생각난다. 스위핑 혹은 파라메트릭 서치. 이 문제의 경우 파라메트릭이 오히려 더 어렵다. 바로 스위핑으로 접근해도 된다. 위치를 받아서 선분 형태로 만들어주고 끝점 기준으로 정렬한 뒤 시작 점들만 관리해주면 된다. 현재 보고 있는 끝점을 b라 했을 때 지금까지 추가해준 시작점들 중에서 b-d 이상인 개수만 구해주면 된다. 시작점을 a라 하면 a도 정렬되게 관리..
2022.11.15 09:24 -
[BOJ 3015] 오아시스 재결합 "컷"
http://boj.kr/943e1681a633468ea54da59124647d2d 공유 소스 보기 www.acmicpc.net 단조스택에 한 방 먹었다. 나였으면 i v[j] , v[i] == v[j] 인 경우 나눠서 세그로 비비고 복잡하게 쓰는 풀이만 떠올랐다. 스택.. 스택은 일단 단조 증가, 단조 감소 한 번 박아놓고 그때부터 명확하게 생각하는게 중요하다. '스택에 있는 값'에 대해 현재의 값을 보는 건지 현재의 값에 대해 '스택에 있는 값'을 보는 건지 알아내면 문제는 끝.
2022.11.13 19:23 -
[BOJ 2533] 사회망 서비스(SNS) "컷"
"문제를 잘 읽기" 얼리어답터가 아닐 경우, 친구 중 한 명만 얼리어답터면 되는줄 알았다. 이 문제는 모두 얼리어답터야 하므로 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.”
2022.11.12 21:00 -
[BOJ 1553] 길의 개수 "컷"
https://www.acmicpc.net/problem/1533 http://boj.kr/42cd430fb1f94613bdc6b6d2feb6a7fd 인접행렬 거듭제곱이라는 개념을 사용해야 하는건 본대 산책 시리즈를 풀어봤으면 바로 보인다. 다만 길에 가중치가 있어 이를 적절히 1짜리 길로 나누어줘야 하는데, 각 길마다 정점을 새로 만들어주면 N = 10*10*5 = 500으로 행렬 곱셈을 할 때 시간이 너무 많이 걸린다. 따라서 각 정점마다 4개의 새로운 정점을 추가하는 방식으로 해결할 수 있다. 앞으로 바로 못 푼 문제나 신기한 아이디어를 사용하는 문제는 복습용 문제집에 저장해둔다. https://www.acmicpc.net/workbook/view/13241
2022.11.10 16:55 -
[BOJ 1006] 습격자 초라기 "컷"
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:/..
2022.11.07 22:52 -
Pushup Program
출처
2022.11.04 09:51 -
INPUT:OUTPUT's Law - Lesson 2
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 ..
2022.11.02 23:32 -
인풋 대 아웃풋의 법칙 제 2강: 진짜다
지난 이야기: https://howtoliveworldnice.tistory.com/673 읽었으면 알겠지만 대부분 뇌피셜이다. 여러분이 뇌 비우고 읽다가 좋은 문장이나 내용 하나 건지면 이 글은 성공이다. 막상 실제로 유명인들의 IOR(Input Output Rate)을 찾아보려니 엄두가 나지 않았다. 몸풀기 겸, 이상적인 IOR에 대해 다시 한 번 말해보도록 하겠다. 사실 대부분의 초심자는 한 챕터를 배울 때 1.배우고(Input) 2. 적용하고(Output) 3. 피드백 받는다(Input)의 IOI 패턴을 따라간다. 따라서 I,I : O = 2:1의 IOR이 되어 전형적인 IOR이 된다. 누구나 쉽게 떠올릴 수 있다. 그러다가 시간이 지나면 '처음 배운 건' 너무나 먼 이야기가 되고 그 챕터 내에서..
2022.11.02 22:54 -
INPUT:OUTPUT's Law - Lesson 1
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..
2022.10.30 20:43 -
인풋 대 아웃풋의 법칙 제 1강: 과연?
먼저 잘 들어라, 그럼 너도 잘 말할 수 있다 논문 많이 읽는 사람이 좋은 논문을 쓴다 코드 리뷰를 많이 할 수록 코드의 질은 좋아진다 프로들이 운동하는 모습을 봐야 너도 프로답게 운동할 수 있다 평소 방송을 즐겨봐야 내 영상도 재미있게 편집할 수 있다 . . . 어떤 분야에 진입하든 항상 듣는말이다. 모든 화법 자기계발서의 1장에는 먼저 상대방의 말을 들으라는 이야기가 나온다. 그리고 나는 이 진부한 패턴에 다시는 그 분야 책을 쳐다보지 않았다. 듣고, 또 더 들어도 내 다른 사람들과의 대화에 만족스럽지 않았기 때문이다. 며칠 전에 "사람의 귀가 2개고 입이 1개인 이유가 뭔지 알아? 상대 말 2번 듣고, 너 말 1번 하라는거야" 라는 글귀를 보았다. 생물학적으로 근거가 없는 말이지만, 이 말은 그 당..
2022.10.30 20:38 -
VS Code C/C++/Python 설정 방법 - PS를 위한
컴퓨터를 초기화할 때마다 필자도 이 글을 켜고 설정한다. 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++ 관련 확장 프로그램을 설치하라는 알림이 뜨는데, 그것..
2022.10.22 23:57 -
한 마디
모든 문제는 명료함의 부재에서 온다
2022.09.22 13:58 -
Master Theorem
*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..
2022.09.14 11:35 -
Computing Fibonacci Sequence with Matrix Multiplication
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..
2022.09.06 12:49 -
0901 금토일 연습
연습 주기를 바꿨습니다. 월화수목 셋은 4문제, 금토일 셋은 6문제 셋 제작자: pentagon03 A - 산업 스파이의 편지 B - 해킹 C - 시저 암호 D - 보안 업체 E - 수열과 쿼리 14 F - 여우 퀴즈 A. dfs + 에라토스테네스의 체 B. 우선순위큐로. 이를 구조화하면 다익이라고 하는데 다익 생각 안 나도 우선순위큐 쓰는게 당연해 보입니다 C. Step 1 원문을 쉬프트하는게 아니라, 거꾸로 암호문을 쉬프트합시다 Step2: 원문의 pi배열이 그대로이므로 각 쉬프트마다 빠르게 kmp를 쓸 수 있습니다~ D. Step1: 한 번 움직일 때 경로 상에 있는 모든 경유 점을 방문하는게 이득입니다. 즉 (start,start)구간에서 한 번 움직일 때마다 구간의 길이가 1씩 늘어나는 방식으로..
2022.09.04 23:40 -
[서평] 백엔드를 위한 GO 프로그래밍
영진닷컴에서 진행하는 이벤트에 당첨되어 백엔드를 위한 GO 프로그래밍 책을 받았습니다. 아래는 파릇파릇한 새 책입니다. 디자인이 예뻐서 내용도 기대됩니다. 제가 매기는 책의 별점은 다음과 같습니다. 내용 4.9 / .5.0 구성/디자인 5.0 / 5.0 저는 개발보다는 컴퓨터 알고리즘 문제풀이에 훨씬 가중치가 많이 부여되어 있는 사람이므로 개발자나 개발입문자의 관점보다는 '새로운 언어에 관심이 있는, 취미로 코딩하는 사람'의 관점으로 책을 읽었습니다. 물론 책 제목에 '백엔드를 위한'이 붙어있으므로 "이 책 하나로 나도 백엔드 개발자?"라는 상상도 잠깐 했습니다. 어디까지나 상상입니다. 책의 내용, 구성, 그리고 실제로 배운 것 3가지에 대해 알아보겠습니다. 이 글은 계속 업데이트될 수 있습니다. UPD..
2022.08.28 22:50 -
0826 연습
셋 제작자: 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:
2022.08.26 08:48 -
0824 연습
셋 제작자: 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: 문자열을 $..
2022.08.24 17:18 -
BOJ 4786 Cosmocraft
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로 키우는데..
2022.08.22 19:36 -
0822 연습
셋 제작자: 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..
2022.08.22 10:03 -
PS | 0814~0820 | 2022
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)로 반복문 ..
2022.08.16 11:27 -
PS | 0731 ~ 0806 | 2022
8월 5일부터 일정이 있어서 PS를 당분간 못할 가능성이 높다. 1557 제곱 ㄴㄴ 더보기 기회가 되서 풀게 됐다. 옛날엔 감도 안잡힐 정도로 어려운 문제였는데 지금은 쉽게 풀이가 떠오르는게 기분이 매우 좋다. 내 풀이는 DB 풀이인데 Segmented Sieve를 사용한다. https://www.acmicpc.net/problem/1016 를 풀고 나면 적당한 min, max만 찾으면 된다는 생각을 할 수 있다. 그 min,max를 구하기 위해 구간을 적당한 블록(2*10^6 정도)로 나눠주고 각 블록의 제곱 ㄴㄴ수의 개수를 구하는 것이다. 미리 전처리를 해놓고 (블록의 크기에 따라 다르겠지만 나의 경우 2000개의 수를 저장) 구간을 찾은 뒤 만들어놓은 체로 K번째 제곱ㄴㄴ수를 구해주면 된다. 내 풀..
2022.07.31 23:14 -
PS | 0723 ~ 0730 | 2022
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을 굉장히 많이 ..
2022.07.28 15:30 -
PS | 0717 ~ 0723 | 2022
2409 더보기 백준에 있는 USACO 중 가장 오래된 문제 17일날 꽂혀서 계속 풀고 dfs+커팅이라는 정보를 얻어서 ( = 완전한 해답이 없다) 커팅 방향으로 계속 풀이를 고쳐나가는중이다. UPD: 7/21 AC 어찌저찌 풀이를 짜다가, dfs 탐색의 횟수를 제한시키는 방법을 떠올리게 되었다. 커팅이라 보기에도 애매하고 이게 무작위 데이터에 대해 돌아갈지 또한 전혀 정확하지 않은 방법이지만 배열을 랜덤셔플하면 최소한 사람이 추가할 수 있는 데이터 내에서는 돌아갈 수도 있다는 생각이 든다. 내가 푼 시점에 총 3사람이 풀었더라. 분명 문제 풀기 전에 봤을 때 한 사람이 1730ms? 이정도로 통과해있었는데 내가 풀고 나니 사라져 있었다. 계정을 지웠거나 지워진건가? 다른 두 사람의 코드를 터트리고 싶다..
2022.07.18 14:48 -
PS | 0710~0716 | 2022
15940 더보기 본선 팀연습 때 jjaewon9와 함께 해결한 문제. 트리에서 각 간선에 대해, 그 간선이 나누는 두 서브트리의 지름을 빠르게 구해 문제에서 원하는 최댓값을 갱신해주면된다. 루트를 하나로 고정해두면 이제 루트가 아닌 각 정점에 대해 그 정점이 루트인 서브트리의 지름과, 이 서브트리의 여집합 (정점의 부모로부터 이어진) 트리의 지름을 구하면 된다. 서브트리의 지름을 구하는 방법 중 dp 방식이널리 알려져 있는데, 각 서브트리에서 루트로부터 가장 먼 정점과의 거리를 저장해 두고 max( max(dp(자식)), max(가장 긴 2개 다리 길이의 합))을 구하면 된다. 아래 지름을 dpD, 위 지름을 dpU에 저장하자. dpU를 구하는 방법도 dpD와 비슷한데, 정점과 부모를 고정하고 생각하면..
2022.07.10 06:31 -
UCPC 2022 예선
1년 간의 휴식을 끝나고 참가하는 첫 대회 icpc팀원인 sean9892의 제안으로 jjaewon9와 팀을 이루었다. 셋 다 약 1년의 휴식을 가지고 있어 걱정반, 오랜만의 PS라 설레임 반이였는데 팀원들이 잘 이끌어준 덕분에 연습과 예선을 성공적으로 마무리할 수 있었다. 팀명을 비롯한 대회 참가 내용의 99%는 아래 두 글의 합집합에 있다. https://sean9892.tistory.com/22 https://jjaewon.tistory.com/29
2022.07.03 07:48 -
Strict Weak Ordering?
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..
2022.07.01 15:24 -
Road to PS God
문제풀이 사이트(집중) 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:..
2022.06.24 16:55 -
Full Diamond
상위 100개 문제를 다이아 이상의 문제로 채웠다! 공부하고 연습한 기록이 이만큼 쌓여서 뿌듯하다. 이제는 사고력을 키워보자. 스스로 사고해서 문제를 풀어내는 것이 재밌어지는 그날까지 연습!
2021.06.11 14:40 -
Amazing CF 공부 리스트
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 너무 좋다! ㅎㅎ 코드포스 공부할 때 정말 최고
2021.06.05 21:58 -
그래프 이론 좋은 자료
http://kocw.or.kr/home/search/kemView.do?kemId=1346284 KOCW에 이런 좋은 자료가 있다는 것에 감동 받았다. 6장 매칭과 커버에 좋은 내용이 많다.
2021.06.03 01:53 -
다이아 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 22:46 -
올바른 괄호 세그먼트 트리
구간이 올바른 괄호문자열인지 판정하는 쿼리, 구간 문자 뒤집기 '(' ')' 업데이트 쿼리 모두를 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 01:44 -
5월 26일#세그먼트 트리 재활
세그 트리 문제를 다시 풀고 있다. 구현에 초점을 맞췄음. 2021.01.23 - [Problem Solving] - 머리로만 문제 풀기 글에 있는 문제들 중 세그 카테고리 문제들을 구현해봤다. 9623 부분 수열의 길이 처음에는 플4라는 게 믿기지 않았던 문제. 업데이트가 없기 때문에 누적합 배열로 구간의 합을 나타낼 수 있는 것이 핵심. 기본적으로 스위핑인 것은 잘 보인다. 끝점 i를 고정시키고 시작점 j+1중 가장 뒤에 있는 것을 찾는 느낌 $0
2021.05.26 21:31 -
주세혁 VS 티모 볼
정말 주세혁은 레전드다.. 9년 전 월드컵 경기. 저 때가 그들의 최정점이 아니라면 언제일까 주세혁의 수비수 플레이는 스스로 기회를 만들어나간다는 점에서 정말 멋지다고 생각한다. 저렇게 빠른 공을 여유롭게 받을 수 있을 때까지 얼마나 많은 연습을 했을까 탁구를 한 번이라도 쳐봤다면 저렇게 수비하는 게 보이는 것보다 수백배 어렵다는 사실을 깨달을 것이다. 아무 회전 없이 공을 넘기는 데만 해도 온 신경을 기울여야 하는데, 저렇게 빠른 스매시 / 상회전 걸린 드라이브 등을 자유롭게 방향까지 조절해가며 커트를 친다. 한편 티모 볼 또한 대단한 선수이다. 티모 볼은 독일 선수로, 중국이 점령하고 있던 현대 탁구에서 세계 1등까지 찍었다. 당시 유럽에서 영웅 취급을 받았다고 ㅎㅎ 잘생김 + 매너 있는 행동으로 인..
2021.05.26 15:54 -
5월 25일 #금광, 전개도
최근 희자님이 금광을 풀기 위한 연속합 세그먼트 트리를 공부하셨다고 한다. (heeda0528) 볼 때마다 풀고 싶었지만 귀찮아서 넘겨왔던 ㅋㅋ 그런 문제다. 그런데..! 희자님 코드가 너무 깔끔한 나머지 최대 연속합 세그를 구현해보고 싶은 욕구가 생겼다..! 30분 정도 시간 투자해서 2달만에 세그를 짜봤다. - 코드 잘된 구현을 봐서 그런지 생각보다 간단했다! 그리고 내가 왜 그렇게 이 연속합 세그를 귀찮아 했는가 생각을 해보니.... 작년 이맘때 2020년 3월 코드업 1등님한테 한 질문 中 3일을 꼴아박아서 꾸역꾸역 연속합 세그를 만들어냈는데 보다 시피 코드 상황이 벌써 끔찍하다. 세그 3개라니 OTL 이제 그 당시에는 뿌듯해서 굳이 새로운 코드를 찾아보지는 않았는데, 이게 내게 정말 큰 충격으로..
2021.05.25 21:35 -
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 22:31 -
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 06:13 -
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 01:03 -
탁구 핵심 전략 10가지
*Reference의 번역과 필자의 분석이 담긴 글입니다. 글을 인용하거나 공유할 때는 이 글의 주소를 맨 위에 표시해주시기 바랍니다. 감사합니다. 1. 공의 회전을 분석한다 임팩트 순간에 상대방의 라켓의 이동방향을 본다. (관찰자가 상대편의 라켓을 봤을 때) 아래에서 위로 => 상회전 위에서 아래로 => 하회전 왼쪽에서 오른쪽으로 => 왼쪽으로 휘어진다 오른쪽에서 왼쪽으로 => 오른쪽으로 휘어진다 손목 스냅과 사선 방향 타격은 횡회전이 섞인 상회전, 하회전 공을 만든다. 상대방이 전면으로 공을 빗겨 칠 때, 라켓이 공 오른쪽에 있을 경우는 공이 왼쪽으로 휜다. 라켓이 공 왼쪽에 있을 경우는 공이 오른쪽으로 휜다. *공의 방향는 임팩트 방향과 관련이 있다. ($\vec F = m\vec a$). 특히 서..
2021.05.19 12:53 -
한글로 파이썬 코딩하기
파이썬에 '한글 변수명'을 사용 가능하다는 사실을 알고 있는가? 이 사실을 망각하고 있다가, 기억나서 당장 BOJ 1000번 A+B 문제를 풀어보았다. def 입력(): return input() def 출력(변수): print(변수) def 맵(함수,리스트): return map(함수,리스트) def 정수화(변수): return int(변수) 에이,비 = 맵(정수화,입력().split()) 출력(에이+비) 코드포스할 때 미리 자주 사용하는 함수들을 템플릿화 시켜놓는 것처럼 한글 템플릿을 미리 만들어놓으면 한글 프로그래밍도 더 이상 꿈이 아니다. ㅋㅋ!
2021.05.19 10:49 -
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 10:36 -
5월 17일 PS일지
1. Class 2 남은 문제들을 땀 자투리 시간을 쓰면 굉장히 많은 일들을 할 수 있다. 생각보다 오래 걸리기는 한다. 실버 문제를 10분씩 걸림. 2. KOI 수상 확인 동상. 아쉽다. 미친 듯이 아쉽다. 옛날처럼 내 자신에게 화가 나고 그러지는 않다. 다른 내신 과목들을 챙기기 시작했고, 난 그걸 실천했으니. 다시 내가 좋아하는 PS 시작할거고 ACM ICPC 국대를 노린다.
2021.05.17 14:32 -
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 23:37 -
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 14:44 -
나의 탁구 Skill 분석
내 탁구 서브 1. 횡회전 서브 (우회전) 서브형 그립으로 바꾼 다음에 몸 안쪽으로 수직 아래로 세워서 스핀을 넣음 상대가 못 받거나 안정적으로 커트를 넣는데 나도 맞 커트 응수하면 된다 2. Fast Line Serve 서브형 그립으로 바꾸면서 회전 없이 왼쪽 라인이나 오른쪽으로 서브를 넣음 내 횡회전 서브에 익숙해진 상대는 커트를 넣게 되는데 이러면 공이 뜬다. 신중하게 자세 잡고 때려버리면 된다. 3. 기습용 좌회전 서브 코트 중앙에서 자세를 완전히 낮추고 라켓을 위로 수직으로 세운다음 앞쪽으로 긁는다 궤적이 왼쪽으로 휨 4. 좌회전 서브 이제 몸을 눕히지 않고 라켓을 손목을 접혀서 포핸드로 잡은 뒤 강한 스윙으로 넘긴다. 공에 회전이 많이 걸려서 Knuckle처럼 공이 흔들리기도 한다. 5. Sn..
2021.04.02 14:11 -
정과프
퀴즈를 보고 나서야 이 과목에 대한 열정이 생겼다. 나라는 인간은 꽤 엄청난 (그러나 해결 가능한) 자극이 주어질 때 그때서야 어떤 분야에 흥미를 느끼나 보다 교과우수 각이 나왔다~ 자만하지 말고 재밌게 해보자 UPD) 1문제 틀렸다. 다 푼건데 입력을 잘못 받아서 틀렸군 급할 수록 차분하게 지내자. 매일 되새기고 있음. 탁구도 마찬가지다. 1. 공보고 치기 2. 차분하기 3. 몸을 움직이기 UPD) 2문제 틀렸다. 조만간 이곳에 주어진 문제와 이를 해결하는 코드를 올릴 것이다.
2021.03.31 19:03 -
뫼비우스 역공식
gratus907.com/74 BOJ 1557 제곱 ㄴㄴ / BOJ 8464 Non-Squarefree Numbers 난이도 : Solved.ac 기준 다이아 5 사실상 거의 같은 문제인 1557과 8464는 둘 모두 Square Free Number의 개수에 관한 문제이다. 풀이는 1557을 기준으로 설명하고, 마지막에 8464에 적용하는 것은 간단하다 :) gratus907.com codeforces.com/blog/entry/53925 [Tutorial] Math note — Möbius inversion - Codeforces codeforces.com codeforces.com/blog/entry/54090 [Tutorial] Math note — linear sieve - Codeforces ..
2021.03.25 20:34 -
Pic2Face
(학교 정보과학프로젝트 시간에 만들었다고 아무도 말하지 않았습니다.) || || || V 사진을 입력하면 사진에 웃는 형태의 틀을 덮어 씌워 준다. 본격 Pic2Face 메소드 이 버전은 검은색이 주류인 사진은 사용할 수 없다. //Full Code : http://colorscripter.com/s/STJKOfy inline void Gradient(unsigned char B[HEIGHT][WIDTH],unsigned char G[HEIGHT][WIDTH],unsigned char R[HEIGHT][WIDTH],int weight=400) { double fordivideheight = 1.0*HEIGHT / weight; double fordividewidth = 1.0*WIDTH / weight;..
2021.03.17 16:36 -
독자들에게 가끔씩 바라는 점
나도 다른 블로그를 참 많이 읽는다. 나만 그런 것인지는 모르겠지만 알고리즘 글을 읽을 때 유난히 "이게 무슨 개소리야" 하는 상황이 많이 닥친다. 철없을 때는 다른 사람이 글 참 못 쓴다.. 생각했지만 내가 블로그를 해보고 나니, 그 귀차니즘에 대해 이해해버렸다. 문제 풀고 맞추는게 재밌지, 그 지식을 다른 사람에게 전달하는 것에서 재미를 느끼는 것은 또 전혀 다르다. 흥미를 느끼지 않는데 글이 술술 잘 써질리 전무하다. 그런데, 대부분 그 사실을 잘 모른다. 알고리즘 정리/문제 풀이 글에는 대부분 댓글이 거의 달리지 않기 때문이다. (...) 내 블로그를 떠나서 PS블로그계는 정말 질문에 인색하다는 생각이 많이 든다. 나부터도 글을 읽다 막혀도 대부분 혼자 고민하고, 정 안되면 다른 글로 그냥 넘어간..
2021.03.09 22:18 -
메타인지 #1
이 글의 발단은 메타인지#0을 참고 바랍니다. 2021/03/06 - [Problem Solving/Road to PS GOD] - 메타인지 #0 현재 L=1, R=31 => mid = 16 => Platinum 5 Platinum 5 문제를 푼다. 문제를 맞은 사람 수 대로 정렬하고 위에서부터 안 푼 문제를 푼다. 첫 문제는 단절점이다. 이 기세를 모아서 단절선도 풀었다. 비슷한 유형의 문제이기에 이건 카운팅 안 함. 두 번째 문제는 소트다. 친구가 푸는 거 보고 따라 풀었는데, 생각보다 많이 절었다 .-. 처음엔 그래프 문젠줄 알았지만, 길이가 n인 경로를 빠르게 찾을 수 없어 실패. 다음날 그냥 그리디적으로 고른 다음 반복적으로 시뮬레이션하면 쉽게 풀 수 있더라. n이 좀 커져도 될 듯 multis..
2021.03.07 21:33 -
CF #705 Div.2
Saycorn과 함께 봤다 문제가 어려웠다. 이번 라운드 업솔빙하면 실력 많이 늘 것이다. 아이디어가 떠올랐을 때 바로 구현하지말고 시간복잡도를 예측해보는 시간을 들여야 한다는 것을 배웠다. 이와 반대로 시간이 촉박할 경우 어떤 아이디어든 세세하게 재지 말고 바로 구현에 들어가야 한다.
2021.03.07 20:41 -
메타인지 #0
Problem Solving을 할 때, 내 자신에 대해 느껴왔던 것 중 하나는 "답지"를 유난히 많이 본다는 것이다.모방은 창조의 어머니라지만, 모방만이 반복되면 결국 표절의 대가가 되어버리고 만다. 현재 나의 solved.ac 티어는 Diamond 2다. 내 실력보다는 훨씬 높은 티어라는 생각이 든다. 나의 본 실력을 파악하기 위해 한 가지 실험을 진행하려고 한다. 가설: 나는 Bronze 5부터 Diamond 2까지 모든 문제들을 풀 수 있는 실력을 가졌으며, 그 이상의 문제는 답지를 참고해야 한다. 실험은 다음과 같다. 기본 컨셉) Bronze5를 1, Ruby1을 30으로 놓고 이분탐색을 진행한다. L: 내가 풀 수 있는 문제 티어의 최댓값 R: 내가 풀 수 없는 문제 티어의 최솟값 L, R의 초..
2021.03.06 17:04 -
Centroid Decomposition - 센트로이드 분할
센트로이드 분할 1. 존재의의 센트로이드 분할 = 트리에서의 분할 정복 기법 트리에서 어떠한 문제( i.e.) 길이가 K인 경로의 개수를 구하라)를 해결해야 될 때 트리를 크기가 더 작은 서브 트리들로 분할하여 문제를 적용한다. 이때 효율적인 분할의 대표적인 기법이 센트로이드 분할이다. 2. 센트로이드란 트리의 무게중심인 정점. 트리를 어떤 정점을 기준으로 차수만큼의 서브트리들로 나눌 수 있다. 이때 모든 서브트리의 크기가 전체 트리 크기의 절반 이하일 때, 그 정점을 Centroid라 한다. Q) 센트로이드는 항상 존재하는가? A) 그렇다 증명 1) 센트로이드 탐색 알고리즘 임의의 노드를 고르자. 그 노드를 루트로 하는 트리를 생각한다. 모든 서브트리의 크기가 조건을 만족한다면 그 노드가 센트로이드다...
2021.02.28 23:16 -
(공유) 알고리즘 구현 깃헙
KACTL 프로젝트 FORK 해왔다. github.com/Pentagon03/kactl Pentagon03/kactl KTH Algorithm Competition Template Library (... eller KTHs AC-tillverkande lapp) - Pentagon03/kactl github.com 개인적으로도 만들고 있음 github.com/Pentagon03/AlgorithmTemplate Pentagon03/AlgorithmTemplate Contribute to Pentagon03/AlgorithmTemplate development by creating an account on GitHub. github.com
2021.02.23 20:44 -
Codeforces Round #703 Div.2
이정도로 망친건 꽤나 오랜만이다. 애드혹, Case-Work 연습이 부족함을 절실히 느낀 라운드 A 잔실수와 C 뇌절이 결정적인 악재로 작용했다. D,E를 봤을 때는 이미 시간이 30분밖에 안 남은 시점이었다. C에서 D,E로 빨리 넘어가면 라운드를 살릴 가능성이 더 높아졌을 거라 판단된다. A. x in {a,b,c}에 대해 min( (t+x-1)/x*x )를 구하여 출력하면 된다. 함수를 만들었는데 함수 인자를 int로 하는 실수를 저질렀다. 교훈: 간단한 함수는 lambda + auto 타입 인자를 사용하자. define도 좋은듯 B. 쉬운 constructive. 뒤에서부터 큰 수 기준으로 배열을 자르면 된다. C. 파라메트릭, dp 뇌절로 쉬운 애드혹을 1시간 20분 가량 붙들었다. 펑 파라메트..
2021.02.23 20:31 -
Codeforces Round #703 Div.2
codeforces.com/contest/1486 총평: 전체적으로 문제 셋이 재밌었고 선방했다. 정확히 1달만에 즉흥적으로 친 코포라 걱정 반 설렘 반이였는데 오히려 더 나은 결과를 얻었다 A -> B -> C1 -> C2 -> E 순으로 풀었다. A는 직관적으로 생각하면 쉬울 것을 너무 성급하게 찍어버렸다. i -> i+1 단방향만 가능하므로 i=0->n-1까지 따라가면서 가능한지 검사하는게 중요 포인트 B는 수학. 무난히 빨리 풀었다. C1, C2는 재미있는 인터랙티브 문제이니 꼭 풀어보는 것을 추천한다. 로그를 붙이는 다양한 알고리즘에 관하여 숙고한 경험이었다. C1 구현에 오래 걸리고, C2는 자칫 못 풀 뻔 했지만 관점을 완전히 바꾸니 시간 투자 후 해결할 수 있었다. E는 다익스트라 문제인데..
2021.02.19 14:08 -
레드 블루 스패닝 트리
4792 최소 스패닝 트리를 만든다고 생각해보자 빨간색 간선을 먼저 이용해서 스패닝 트리를 만들면 파란색 간선을 최소로 이용하는 스패닝 트리가 생성된다. -> B개 반대로 파란색 간선을 먼저 이용해서 스패닝 트리를 만들면 빨간색 간선을 최소로 이용하는 스패닝 트리가 생성된다. -> R개 이때, R,B개는 각각 스패닝 트리를 만들 때 각 색깔에서 '꼭 필요한' 간선의 개수다. 우선적으로 이용하는 색의 가중치를 0, 다른 색의 가중치를 1로 놓고 최소 스패닝 트리를 만든다고 생각하면 쉽다. B
2021.02.10 18:11 -
Solved.ac 경험치 시스템 개편
최근 Solved.ac 티어 계산 시스템이 바뀌었다. 1번 항목과 2번 항목은 푼 문제를 어려운 순으로 정렬해 상위 100개 문제를 합산하는 것으로 수정되었다. 솔브드 Slack에서 얻은 정보들이다. 첨언 하자면 푼 문제 수에 따른 값은 최대 175이며, 거의 증가하지 않는다. 675문제 푼 내가 169점이고, 9000문제 가량 푸신 구사과님이 175점인 것을 보면 된다! 기여 수에 따른 값은 최대 25이고 135문제 기여 -> 25, 8문제 기여 -> 14인 것을 보면 티어와 거의 무관한 수치다. 티어와 가장 유관한 것은 푼 문제들 중 가장 어려운 것과 클래스가 되시겠다. 다이아, 루비를 많이 풀자 의도
2021.02.08 21:38 -
내 PS 방향성
4일 동안 PS 없이 생활 했다. 그동안 꾸준히 PS하던 노력을 공부에 쏟으면 3학년 1학기 내신과 대학 서류, 면접에 필요한 기초 다지기 등을 더 착실히 준비할 수 있겠다는 생각에서였다. 결론은 '그러지 않다' 2주 이상 끊었던 게임을 다시 시작하고 (6년 동안 해온 짓), 독서실에 가도 예전처럼 집중이 안 되기 시작했다. PS가 사라지면서 비운 시간들을 여가 거리들이 대신 채웠다. 정녕 대한민국의 고3의 생활이 맞는가? 라는 말도 들었다. 공부일지를 써보려 했지만, 본능에 따라 쓰는게 아닌만큼 잘 안됐다. PS 다시 할까? 라는 유혹이 쉼새 없이 몰아쳤다. 그래도 안 했다. 블로그와 블로그를 보시는 분들과약속했기 때문이다. 난 스스로 한 약속도 안 지키고 다른 사람과 한 약속도 그렇게 잘 지키는 편은..
2021.02.01 08:04 -
백준 20654 "음료수는 사드세요 제발"
문제 : 음료수는 사드세요 제발 문제 링크 백준 20654 음료수는 사드세요 제발 풀이 사용 알고리즘: 병렬이분탐색(pbs), 그리디, 세그먼트 트리 문제 요약 N개의 액체가 있습니다. 각 액체는 3가지 속성이 있어요 1.맛 2.단위 가격 (원/리터) 3.최대 사용 가능 양 (리터) 음료수는 액체를 임의로 섞어 만들 수 있습니다. 음료수의 맛은 $min(섞인 액체들의 맛)$으로 정의됩니다. M개의 쿼리가 들어옵니다. 쿼리는 A,B 2개의 정수로 이루어집니다. "A원 이하를 사용해 B리터 이상의 음료수를 만들 때, 맛의 최댓값을 구하시오. 조건을 만족하는 음료수를 만들 수 없다면 -1을 출력한다." $1 자신의 왼쪽 노드 구간이 합이 B 이상이면 왼쪽으로 내려가고, B 미만이면 "B - 왼쪽 노드 구간 합..
2021.01.26 16:27 -
2021년 1월 26일 PS 일지 - 마무리.
1. 대회를 위한 PS 최근 Green55님의 이런 글을 읽었다. 대회의 실력 향상에 도움이 되는 것은 '기본기'라는 내용. 나는 알고리즘을 즐기는 타입이지만 대회에 욕심이 있는 것도 사실이다. 코포, 정올, ... cgiosy와도 늘 이야기를 해 왔던 거지만 일반적인 대회의 수상은 "다이아를 4시간 잡고 풀 수 있는가?" 보다 2시간 내에 플레 3~4개를 밀 수 있는가와 더 밀접한 관련이 있다. 세종정올 때는 그게 잘 됐고 좋은 결과를 얻었다. 코포에서는 빠른 시간 내에 퍼플까지 올라왔다. 하지만 앞으로 한국정올 수상, 코포 레드까지 가기 위해서는 다른 전략이 필요함을 깨달았다. 쉬운건 더 빨리, 어려운 것도 신속한 관찰을 해야 한다. 요즘 자료구조 하나 잡고 관련 문제 푸는 것에 맛들렸다. 최근 PS..
2021.01.26 01:21 -
2021년 1월 25일 PS일지
1. BOJ 5 Solve (1) 13553 수쿼 8 Mo's Algorithm + Fenwick. Add와 Del 함수를 어설프게 합치는 것보다 제대로 분리한게 낫다. -포인터를 옮기는 순서를 항상 구간 확대를 축소보다 먼저 하자. 1 2 -> 3 5 이렇게 옮기는 상황에서는 2를 먼저 5으로 옮기고 1을 3으로 옮기자. 1을 먼저 옮기는 방식으로 하면 꼬이는 경우도 있는 듯. ex) 1 2 -> 2 2 -> 3 2 -> 3 3 -> 3 4 ->3 5 위 처럼 이상한 경우가 생긴다. (2) 서로 다른 수와 쿼리 2 1시간 정도 고민했는데 안 나와서 스톤준님 풀이 보고 했다. PST는 연습만이 답인듯. 잘 안 보이고 구현도 어렵다. Cgiosy 비재귀 퍼시스턴트 트리는 정말 미친 듯 => 소스 cgios..
2021.01.25 04:47 -
2021년 1월 24일 PS일지
1. 하루 3솔 레이지 세그먼트 트리 형제 1. 수열과 쿼리 23 ✔ 2. 버거운 버거 ✔ - 레이지 세그 3개를 한 문제에 동시에 박은 건 처음이다. 확실히 구현량이 많아질 수록 실수가 잦다. 빨리 찾아서 다행이지만 더 치밀해지자. 끝나고 다른 풀이를 보니 훨씬 간단하던데 배우자. 내 풀이는 여는 괄호를 1, 닫는 괄호를 -1로 모델링 하고 min(sum[i]) >= 0 && sum[n] == 0 이 만족되어야 올바른 괄호 문자열이다를 이용하는 풀이다. min(sum[i]) 이 조건이 괄호를 반전하면 max(sum[i])를 구하는 것이기 때문에 (1) 구간 곱, 합을 업뎃을 지원하는 최솟값/최댓값 쿼리 세그먼트 트리와 (2) 구간 곱 업뎃을 지원하는 구간합 쿼리 세그먼트 트리가 필요하다. 구현 꽤 빡셌..
2021.01.24 02:15 -
공부할 예정 목록은 다 여기에!
해시 algoshitpo.github.io/2020/02/09/hashingtechnique/ 해싱으로 문자열 문제 날로 먹기 Intro ACM-ICPC 등에서 주로 출제되는 문자열 문제는 일반적으로 KMP, Suffix Array, Trie, Aho-Corasick 등의 자료구조나 알고리즘을 사용해서 해결하는 것이 정해인 경우가 많습니다. 하지만, 그 중 많은 문 algoshitpo.github.io www.acmicpc.net/blog/view/67 해시로 장난치기 안녕하세요. rdd6584입니다. 문자열이라면 절레절레 하던 제가 이번 네블컵을 준비하면서, 해시에 대해 어느정도 이해를 하게 되었습니다. 그래서 해시로 여러가지 장난을 쳐봤고, 해시로 풀 수 www.acmicpc.net ICPC 다이아 ..
2021.01.23 23:10 -
머리로만 문제 풀기
구현 없이 풀이만 생각 효율적인 사고력 증진 연습 https://www.acmicpc.net/problem/1040 1040번: 정수 정수 N이 주어진다. N보다 크거나 같은 수 중에, K개의 서로 다른 숫자로 이루어진 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오. www.acmicpc.net dp[N][first][st] : 길이 N의, first로 시작하는 수들 중 st 상태만큼의 숫자들을 사용했을 때 만들 수 있는 최소 정수 www.acmicpc.net/problem/9623 9623번: 부분 수열의 길이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N (1 ≤ N ≤ 500,000)과 X (-109 ≤ X ≤ 109)가 주어진다. 둘째 줄에는 수열에 들..
2021.01.23 10:08 -
2021년 1월 23일 PS일지
1. 간선의 가중치가 음이 아닌 정수인 그래프에서의 최단경로 알고리즘 $0
2021.01.23 09:57 -
2021년 1월 22일 PS일지
1. 이분매칭 연습문제 1017 소수 쌍✔ - 모델링 모르겠어서 풀이보고 짬. 홀수 / 짝수 모델링 처음에 동일한 집합 간 이분 매칭을 시도하려 그랬는데 어림도 없다 이분 매칭은 항상 '이분' 되어야 함을 명심하자. 2. PST 연습문제 11932 트리와 k번째 수✔ PST 사용한다는 말만 듣고 혼자 풀었는데, 기분 정말 좋다!! 당분간 사용할 PST 구현 13538 XOR 쿼리 16977 히가큰직쿼
2021.01.22 08:08 -
If you are a Newbie in Competitive Programming
There was a question in Codeforces recently. Talking about "I'm such a Newbie in Codeforces.. What should I do?" This is a quite boring question since there are tons of same questions. So it got many downvotes, obviously. However, I wanted to reply him because I was once a Newbie too. My Reply If you are thinking Codeforces as a 'tutorial' site, you are in the wrong place. That's why you are get..
2021.01.21 19:22 -
2021년 1월 21일 PS 일지
1. Persistence Segment Tree 연습문제 풀이 www.acmicpc.net/problem/11932 11932번: 트리와 K번째 수 첫째 줄에는 두 개의 양의 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 각 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치이다. 이 가중치는 모두 www.acmicpc.net 트리와 K번째 수 문제는 푸는 중이다 풀이 보기 전에 어제 풀었던 Component Tree 내용을 이용해 O(N log^3 N) 풀이를 짰으나 장렬히 시간초과가 난다. 덕분에 LCA 복습했다 ^^ HLD로 비슷하게 할 수 있을 것 같으나 역시 시간초과가 예상된다. 잠깐 다른 과목 밸런스 맞추러 갑니다. 한동안 PS에..
2021.01.21 16:59 -
2021년 1월 20일 PS 일지
1. Segment Tree 연습문제 마무리 2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest C. Component Tree codeforces.com/gym/100513/problem/C Problem - C - Codeforces codeforces.com 분명 간단한 세그트리 연습문제라 들었건만 정말 어렵다 2시간 이상 고민했는데 풀이가 안 나와서 풀이를 찾아봤다. 정말 다양한 풀이를 봤지만 이해가 안됨. 오히려 HLD 쓰는 풀이를 이해해버려서 세그 쓰는 풀이를 탐색 중임. 그냥 혼자 생각하기로 함. 일단 property 별로 생각하는 것은 명백하다. 어떤 노드가 property를 가지고 있다. -> 자신의 subtree에 영향을 미친다. 결국 구..
2021.01.20 23:39 -
2021년 1월 19일 PS 일지
코포 참여합니다~ codeforces.com/blog/entry/86882 Codeforces Round #696 (Div. 2) - Codeforces codeforces.com A: 관찰이 조금 늦어서 큰일났다는 생각을 했다. a와 b를 bit sum 한 다음 d를 만드는데 비트 1과 1을 더하면 10이 되는게 아니라 2가 된다. ex) 110 + 110 -> 220 그런데 연속된 값이 있으면 20 이렇게 자릿수가 줄어든다. b가 주어질 때 a+b의 최댓값을 찾기. (a와 b의 자릿수는 정해져 있음) 앞자릿수가 가장 크고, 자릿수가 안 줄어든게 이득. 그런 경우는 딱 한가지 밖에 없다. 맨 앞자릿수를 1로 고정시키고 다음 자릿수로 넘어갈 때 인접한 비트의 합이 안 같은 경우로 고른다. 두가지 선택지가..
2021.01.19 18:17 -
Persistent Segment Tree 구현 메모
난 이 글의 마지막 부분을 보고 퍼시스턴트 세그먼트 트리를 익혔다. 일단 내 나름대로 퍼시스턴트 트리를 떠올려 보았다. 과거 기록을 모두 가지고 있는 트리. 때마침 수쿼22가 그런 컨셉의 문제였고, 나는 스스로 이 문제를 풀어보았다. 어떤 원소를 업데이트할 때 그 원소로 인해 업데이트 되는 세그먼트 트리의 노드는 최대 O(log N)개다. 그럼 각 쿼리마다 log N개의 '기록'만 추가된다는 것. 세그먼트 트리의 각 노드를 '벡터'로 만들어서 k번째 쿼리에는 이 값을 가지고 있었다는 사실을 저장하면 되지 않을까? 별도로 인덱스 배열을 만들어서 나는 'x번째 쿼리'때 이 값으로 변경되었어요~를 저장하면 추후 이분탐색으로 2번 쿼리를 처리할 수 있다. 구현 성공! 업뎃 쿼리는 O(log N), k번째 업뎃 ..
2021.01.18 22:43 -
PS일지 중간 점검
날짜 한 일 배운 점 1/7 PS일지 작성 결심, Kquery, 레이지세그 기본에 충실하자. 세그에서도 모르는게 많다 1/8 코포 Div2 #695 + C,E upsolve ad-hoc을 더 충실히 할 필요가 있다. C는 쉬웠는데 많이 말린듯 1/9 게임이론 과도한 계획은 실천하기 어려움 1/10 게임이론 계획을 줄였으나 역시 과도했음 1/11 세그 연습문제 가가두점(가장 가까운 두 점) 공부 set,map은 std::lower_bound에서 O(N)에 동작함. 꼭 내장함수를 이용하자 1/12 버추얼 과도한 계획은 실천하기 어려움. 생각을 멈추고 먼저 해버리자. 1/13 염소 줄서기(다이아4) 거의 처음으로 스스로의 힘으로 다이아 문제를 풀었다. 최소 외접원 및 Convex Hull 복습 하면 된다. 1..
2021.01.18 19:56 -
2021년 1월 18일 PS 일지
1. PBS 마무리 Calculating Average라는 문제를 오늘 끝내버린다. 그동안 미뤄 왔는데 오늘 날 잡고 끝내버리기로 결심했다. Calculating Average 맞 았 다! pbs를 엄청 효율적으로 적용하는 방법도 있던데 그것은 300iq님의 코드를 참고하자. CHT를 Persistent하게 관리한다. 2. Segment Tree 연습문제 풀기 codeforces.com/gym/100513/problem/C Problem - C - Codeforces codeforces.com 3. Persistent Segment Tree 드디어 대망의 Persistent Segment Tree를 공부한다. 2021/01/18 - [Problem Solving/알고리즘 이론 정리] - Persisten..
2021.01.18 02:33 -
2021년 1월 17일 PS 일지 - K보다 작은 수의 개수 쿼리
클래스 7에 들어갔는데 재미있는 문제들이 보인다. -> "수열과 쿼리 1" 그중 예전에 풀었던 KQUERY와 연관된 문제가 여럿 있어 모두 AC를 띄우고 왔다. 달달하다~ K Query2 같은 경우 구간에서 k 이상인 수 개수 쿼리 + point update를 처리하는 문제인데 대부분 sqrt decomposition으로 풀었지만 내 풀이는 좌표압축 + BIT in Seg로 O( log^2 N)에 각 쿼리를 처리 가능하다. 하지만 시간은 웬지 모르게 평방분할보다 느리다. 세그가 복잡한 연산이여서 그렇다고 생각한다. Geeks for Geeks 평방분할 풀이 - www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray-set-..
2021.01.17 06:27 -
2021년 1월 16일 PS 일지
1일 3BOJ www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 해싱 연습문제 내가 즐겨쓰는 소수들: 5e5+9, 5e5+29, 1e9+7, 1e9+9, 1e9+21 1e9+21은 잘 알려져 있지 않은 소수이기 때문에 저격을 피할 수 있어 좋다. 머,,, 대부분 저격해놨다면 랜덤을 쓰자. 정렬하면 쉽게 풀 수 있겠지만 일부러 해싱을 써 봤다. 생각나는 또 다른 풀이로는 정렬한 다음 투포인터를 써서 비교 과정을 O(n)으로 구현할 수 있겠다. ..
2021.01.16 16:35 -
How to win Gold Medal in IOI
usaco.guide/dashboard/ Dashboard A free collection of curated, high-quality competitive programming resources to take you from USACO Bronze to USACO Platinum and beyond. Written by top USACO Finalists, these tutorials will guide you through your competitive programming journey. usaco.guide https://codeforces.com/blog/entry/69100 My winning theory in IOI 2018 & 2019 — Why I won 2 golds in IOI - C..
2021.01.15 18:31 -
2021년 1월 15일 PS 일지
Educational Codeforces Round 102 (Rated for Div. 2) Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces codeforces.com 나름 잘했다고 생각한다. 다만 에듀코포여서 모든 문제의 점수가 같다 따라서 빨리 풀고 적게 틀리는게 관건 C를 못 푼게 살짝 심각.. 코포에서 자주 쓰이는 알고리즘을 저장한 템플릿을 어서 빨리 만들어야 겠다. B,D,E 구현이 느렸다 E는 재밌는 문제다. 고급 알고리즘 시간에 다룬 그래프 변환을 여기서 써먹게 됐다. 주어진 그래프를 문제의 정답을 그대로 유지하되, 정점과 간선을 추가/삭제하는게 그래프 변환이다. 여기서는 정점을 상태에 따라 여러 정점으..
2021.01.14 21:17 -
2021년 1월 14일 PS 일지
맞왜틀; 오늘 PST 하는 날인데 ㅜㅜㅜㅜㅜ 맞왜틀에 빠졌다 ㅡ.ㅡ www.acmicpc.net/problem/17236 17236번: Heights 각 줄에 실존하는 삼각형의 높이 값 ha, hb, hc가 각각 주어진다. ha, hb, hc는 실수이며, 0.01 ≤ ha, hb, hc ≤ 100.00이다. www.acmicpc.net 기하 + 부동소수점 오차 빡친다.... 오늘 PST 하고 BOJ 3솔은 내일 해야겠다. 1/13에 적은게 1/14에 3솔했다고 생각하면 됨.
2021.01.14 21:15