분류 전체보기(223)
-
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 -
백준 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,b) 의 중점..
2024.02.11 -
백준 단계별로 풀어보기 완.
컨벡스헐부터 정체되어 있던 백준 단계별 풀어보기를 2024-02-05 오늘 끝냈다. PS를 제대로 하기로 다짐한 사람이라면 단계별로 풀어보기부터 강의 듣듯이 빠르게 배운 후 OI / ICPC 스타일 문제를 풀어보는 것도 하나의 가장 효율적인 방법이라고 생각한다. 하나의 Tool Box를 다 채우고 시작하는 느낌.
2024.02.05 -
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 -
C/C++코드를 빠르게 고치기 위한 체크리스트
체크리스트 대부분의 IDE에서는 컴파일 에러 이유를 보여줍니다. 모든 실행문 끝에는 세미콜론을 적었나요? 지금 사용한 변수를 선언했나요? 중괄호가 열렸다면, 닫혀야 합니다. '들여쓰기’를 맞추면 코드가 눈에 보입니다. 'A’와 A는 다릅니다. main 함수 안에 있는 변수는 자동으로 초기화되지 않습니다. scanf에 들어가는 인자들은 주솟값이어야 합니다. &를 붙였나요? scanf에서 공백과 줄바꿈 문자를 넣지는 않았나요? scanf/printf에서 형식 지정자를 잘 맞췄나요? 문제의 입력과 출력 부분, 조건을 다시 한 번 꼼꼼히 읽어보세요. 자료형을 확인하세요. 실수 계산을 정수 계산으로 대체할 수 있나요? 배열 인덱스를 확인하세요. 배열 크기는 늘 넉넉하게 잡는 것이 편합니다. 함수가 제대로 동작하지..
2023.10.29 -
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 -
USACO 가르치기
보호되어 있는 글입니다.
2023.10.07 -
Reason You Should Never Start This Fucking Cells Game
보호되어 있는 글입니다.
2023.09.04 -
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 -
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 -
[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 -
2023년 PS 생각
1. 지금까지의 현황 (1) 기분: 답답하다. PS에 전념해서 GOAT가 되고 싶다. 단순 취미를 넘어서 어떤 업적 하나라도 만들고 싶다. 그러나 다른쪽에도 벌여놓은 일들이 나를 옭아맨다. (2) 스트릭: 시간이 없는 날에는 폰으로 매일 브론즈라도 풀었고, 도무지 PS 열정을 참을 수 없을 때는 단계별 문제를 풀었다. 2023.03.25 기준으로 스트릭 111일을 찍었다. (3) 단계별: 앞 단계의 경우는 대부분 풀어져 있어서 각 단계의 2~3문제 정도만 채우면 됐는데 SCC, 세그, 동적계획법 4부터는 플레 상위 개념들이 있어서 나름 재밌었다. 9단계 가량 남았고 곧 네트워크 플로우를 배울 수 있어 기대된다. (4) 코드포스: 도무지 새벽 시간에는 코딩을 못하겠다. 오래 집중하는 능력이 거의 사라졌다...
2023.03.25 -
5 Death Regrets
보호되어 있는 글입니다.
2023.03.20 -
[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 -
Chat GPT: How to be happy 2022.12.10
-
코드업 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 -
공지사항 2022.12.01
1. 블로그 이름 변경 비키라의 세상 => Pentagon 굳이 다른 닉네임 사용할 필요성을 못 느껴서 드디어 통일합니다. 2. 휴식 뻘글만 늘어나고 블로그에 발전은 없어 당분간 정기적인 글을 올리지는 않습니다. 제가 다시 공개적인 글을 적는 날은 뚜렷한 주관이 생겼을 때입니다. 늘 하던 것처럼 재밌는 일 생기면 글 적습니다. 3. 연락처 연락은 pentagon03@kaist.ac.kr로 주세요.
2022.12.01 -
[BOJ 26035] “컷” $0101$
https://www.acmicpc.net/problem/26035 PS는 원래 폰으로 하는거다. 추가) 이 문제는 우리 갓 https://www.acmicpc.net/user/heeda0528가 만든 갓 문제입니다. 모두 찬양하시기 바랍니다.
2022.11.18 -
[BOJ 25972] 도미노 무너"트리"기 "컷"
https://www.acmicpc.net/problem/25972 문제를 과대해석 하는 경향이 있다. 오 이거 재밌겠는데? 하는 생각이 들면 그렇게 문제를 풀어버린다. 정렬하면 모든 도미노는 인접한 도미노에만 영향을 준다.
2022.11.17 -
[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 -
[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 -
[BOJ 3176] 도로 네트워크 "컷"
https://www.acmicpc.net/problem/3176 이 문제를 아직까지 안 풀었었다니! sparse table 이용한 LCA 기본형 문제. HLD도 이용할 수 있다. LCA할 때 이런 식으로 i를 -1까지 보내면 한층 편하다. 코드가 못생겨지지만 편한게 장땡.
2022.11.15 -
[BOJ 13334] 철로 "컷"
https://www.acmicpc.net/problem/13334 http://boj.kr/d7291475a4294aa58c892481968bf9e3 문제를 보자 말자 세그나 mergesort tree 풀이만 생각나서 고생했다. 골드2인데, 그게 정해일리도 없을 뿐더러, 구현이 빠른 풀이를 생각해보고 싶었다. 문제를 보면 2가지 접근이 기본적으로 생각난다. 스위핑 혹은 파라메트릭 서치. 이 문제의 경우 파라메트릭이 오히려 더 어렵다. 바로 스위핑으로 접근해도 된다. 위치를 받아서 선분 형태로 만들어주고 끝점 기준으로 정렬한 뒤 시작 점들만 관리해주면 된다. 현재 보고 있는 끝점을 b라 했을 때 지금까지 추가해준 시작점들 중에서 b-d 이상인 개수만 구해주면 된다. 시작점을 a라 하면 a도 정렬되게 관리..
2022.11.15 -
[BOJ 3015] 오아시스 재결합 "컷"
http://boj.kr/943e1681a633468ea54da59124647d2d 공유 소스 보기 www.acmicpc.net 단조스택에 한 방 먹었다. 나였으면 i v[j] , v[i] == v[j] 인 경우 나눠서 세그로 비비고 복잡하게 쓰는 풀이만 떠올랐다. 스택.. 스택은 일단 단조 증가, 단조 감소 한 번 박아놓고 그때부터 명확하게 생각하는게 중요하다. '스택에 있는 값'에 대해 현재의 값을 보는 건지 현재의 값에 대해 '스택에 있는 값'을 보는 건지 알아내면 문제는 끝.
2022.11.13 -
[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 -
[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 -
[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 -
Pushup Program
출처
2022.11.04 -
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 -
인풋 대 아웃풋의 법칙 제 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