#include"invrtd.h"

모든 글

• 

  2024 SCPC (삼성 대학생 프로그래밍 경진대회) 1차 예선 후기 1. A보다 B가 좋아 (예측 S3) #문자열 #애드혹모든 AA와 ABA를 지워주기 위해 사이에 B를 끼워넣어주면 된다. 증명: 어떤 구간 [l, r] 사이에 있는 A가 B보다 많다고 하자. 주장은 이 안에 적어도 1개의 AB 또는 ABA가 있다는 것이다. 이를 검증하기 위해 귀류법으로 저런 패턴이 없다고 가정하고, ABBABBA... 이렇게 써 보면 절대 A가 B보다 많아지지 않는다.  2. 배달 (예측 S1) #정렬 #애드혹 #그리디문제에서 주어진 식, |a-b|+|b-c|+|c-d|+|d-a|는 2*max(a,b,c,d) - 2*min(a,b,c,d)와 같다. 따라서 정렬 후 a, d를 가장 바깥쪽에서 골라주고 b, c를 가장 안쪽에서 골라주면 된다. 이를 N/4번 반복. 3. 보안망 점검 (예측 .. 2024.07.06

• OCaml에서 Vector 자료 구조 만들기 OCaml은 표준 라이브러리에서 배열과 리스트를 제공하지만 가변 길이 배열(벡터)은 제공하지 않는다. 그래서 OCaml 연습도 할 겸 가변 길이 배열을 만드는 Vec 모듈을 만들어보기로 하였다. 먼저 레코드를 이용해 'a vec 타입을 만든다. 레코드에는 데이터 data와 벡터의 길이 length를 저장한다. 벡터 특성상 length의 길이는 실제로 Array에 할당된 크기(capacity)보다 작을 수 있는데, 이는 Array.length 함수를 호출하면 가져올 수 있으므로 capacity를 따로 저장할 필요는 없다. type 'a vec = { mutable data : 'a Array.t; mutable length : int; } 모듈이 하나의 타입을 구현하므로 관습에 맞게 type 'a t를 작.. 2024.03.31

• 

  Mac에서 Launchpad가 하단 바에서 디폴트로 안 보일 때 해결법 Launchpad도 응용 프로그램이다. 따라서 해결법은 아무 응용 프로그램을 하단 바에서 디폴트로 나타나게 하는 법과 같다. Finder에서 [응용 프로그램] 탭 들어가서 Launchpad를 찾은 뒤 하단 바로 드래그하면 된다. 2024.03.20

• 충격!) C++에서 Rust의 블록 표현식과 유사한 구문을 사용할 수 있다?! Rust는 {}으로 감싸지는 코드 블록이 단순한 문장들의 나열이 아니라 하나의 표현식(Expression)으로 사용될 수 있다. let x = ??? let result = { let x0 = if x >= 0 {x} else {0}; x0 * x0 * x0 + 3 * x0 }; 코드블록의 마지막 문장인 x0 * x0 * x0 + 3 * x0 뒤에 세미콜론이 찍혀 있지 않으므로, 코드블록은 x0 * x0 * x0 + 3 * x0으로 평가되는 표현식(Expression)이 된다. 따라서 result에 해당 값이 들어간다. 이런 구문은 이름공간의 오염을 줄이는 역할을 한다. result를 계산할 때 말고는 절대로 x0가 다시 사용되지 않는다는 것을 알고 있다면 코드 블록을 사용하여 x0을 특정 영역 안에 가.. 2024.03.04

• 

  확실히 등단하고 나서 내 인생이 달라졌다 원래는 대학교때 짝사랑하는? 교수님 눈도 못 마주치고 쓰레기 아무데나 버리고 조던피터슨한테 침 찍찍 뱉고 했는데 시와편견 신인문학상 등단패 오너가 되고나니깐 품위유지하려고 스스로 노력할려고한다. 방금도 내가 3달 전에 썼던 에리히프롬 까는 초고 버려져있길래 주워서 쓰레기통에 버리고왔다. 학생때는 한병철이든 자청이든 맘에 안 들면 다 깠는데 이제는 동아리원들(특징: 철학서 나보다 많이읽음) 눈도 못 마주친다. 아무리 말하고 싶은 얘기가 있어도 샤워하면서 혼자 나는 누구? "시와편견 신인문학상 등단패 오너" 하니까 겁나 부담스럽네 이래서 자리가 사람을 만든다는말이 나온것같다. 2024.03.02

• 철학은 자기 공격성을 포장하기 위한 수단이 아니에요 그냥 내 시처럼 자기가 공격성 있다는 걸 쿨하게 인정하든가 아니면 그냥 처음부터 뺨 때린 사람에게 다른 쪽 뺨도 내줄 기세로 사고하든가 자기 도덕성이 점점 진보하고 있다고 믿는 사람과 대화하는 것만큼 고통스러운 일이 없어요 2024.02.01

• 

  상속, A is B, A behaves as B, 리스코프 치환 원칙 객체 지향 프로그래밍은 인간이 사물이나 개념들을 서로 연관 짓는 방식을 프로그래밍 언어로 그대로 표현할 수 있게 함으로써 코드의 가독성을 높인다. 여기서 자주 쓰이는 "연관 짓는 방식"에는 다음과 같은 것들이 있다. 포함 관계 (A is B) 예제: 사람은 동물이다. 프로그래밍 언어에서 상속이라는 기능을 쓰면 포함 관계를 표현할 수 있다. 다음 프로그래밍 언어 "public class Human extends Animal"은 적법한 코드다. 사람은 동물이기 때문이다. 그러나 위 짤방에 나온 "public class Car extends Person"은 좋은 코드가 아니다. 개체 관계 (a is an instance of B) 예제: 박은빈은 사람이다. 프로그래밍 언어에서 클래스와 인스턴스 사이의 관계가 .. 2024.01.30

• 무슨 컴공 글을 써야 사람들이 원하는 글을 쓸 수 있을까 자료구조론, 알고리즘 아니면 파이썬 고급 feature들 아니면 C++만의 고유 디자인 패턴 사실 잘 모르겠음 (주제 추천 받아요) 2024.01.28

• 

  [백준 1285] 동전 뒤집기 $N\le 20$이므로 $2^N$ 또는 그에 준하는 풀이를 생각해볼 만하다. 가로 $N$개의 줄, 세로 $N$개 줄 중 무엇을 뒤집을 것인지 생각하는 문제이므로 존재할 수 있는 선택의 개수는 $2^{2N}$이다. 그중에서 가로줄과 세로줄 중 하나가 몇 번 줄을 뒤집을지 그 상태가 이미 정해졌다면(편의상 세로줄이라 하겠다), 가로줄에 H가 더 많으면 가만히 놔두는 것을 선택하고 T가 더 많으면 뒤집는 것을 선택하는 그리디 알고리즘을 생각할 수 있다. 이것이 성립하는 이유는 세로줄이 이미 선택된 이상 모든 가로줄은 서로 영향을 주지 않는 독립이므로 순간의 최적 선택이 전체 최적 선택을 담보하기 때문이다. 한 번 그리디 알고리즘을 시행할 때마다 전체 셀 개수인 $O(N^2)$의 시간.. 2024.01.10

• 

  글쟁이를 위한 해시태그 이게 뭐시여~ 원래 여기는 inverted.h가 주인장인 코딩/개발 블로그인데 이번만큼은 박예담 빙의해서 작성함 1. 글을 쓰게 된 계기 인간에 대해 이해하고 싶어서일 거임 아마 2. 하루에 쓰는 분량 시 쓰는 사람은 하루에 그렇게 많이 쓰지 못해가주구 요즘은 2주에 한 편꼴로 쓰고 있는 것 같습니다 이것보다 더 많이 쓸 수 있긴 한데, 시인의 딜레마라는 게 쌓인 일이 많다 -> (+) 얻을 수 있는 글감이 많다 (-) 시 쓰기 전에 그 일을 해야 한다 쌓인 일이 적다 -> (+) 시 쓸 시간이 많다 (-) 얻을 수 있는 글감이 적다 이 굴레에서 벗어날 수가 없음 3. 슬럼프 극복하는 방법 극복을 안 했음 4. 작업곡 / 노동요 시 쓸 때만큼은 노래 안 듣습니다 단어 하나하나에 초집중해야 해서 집중한 꼬.. 2024.01.06

• 

  2023 제2회 미적확통컵 출제 후기 귀찮으니까 빨리 적어야지 미적확통컵 특) 플래 겁나많음 1회 미확컵보다 솔브드 기여 난이도는 낮게 잡힐 것 같은데 1회 때 웰노운이 많았던 것과 달리 2회 때는 그런 게 없어서 사람들이 좀 고전하는 것 같았다 60분 이내에 솔브가 나지 않은 문제가 1회 3개 -> 2회 5개로 늘었고 푼 사람이 1자리 수인 문제가 1회 3개 -> 2회 6개(...)로 늘었다 CD 결혼식이 끝나고 PE 최고의 크리스마스트리 두 문제를 출제했다 결혼식이 끝나고 퍼솔 84분, 푼 사람 8명 내가 미적확통컵에 맨 마지막으로 들어간 출제진이다. 정확히 말하면 추가합격인데 8월쯤에 출제진 한 분이 빠지셔서 추가모집 때 내가 들어갔어요 이것도 사실 겨우겨우 들어갔음 하루님이 메일을 보내셨는데 스팸메일함으로 쏙 들어가버린겁니다 그래서 .. 2023.12.24

• 

  ICPC 2023 본선 후기 (망함) 팀 멤버는 armyantking (P1), invrtd_h (D1), 172635 (P5). 내가 작년에 리저널 28등을 했음에도 불구하고 (팀명은 codingMinsu) 올해도 그만큼의 성적을 기대하긴 힘든 상황이었다. 가장 큰 전력이었던 bbb1293 (D5) 형님이 졸업하셔서 더 이상 ICPC를 치지 못하시기 때문. 그래서 대회 치기 전에는 30-40등을 기대하고 있었는데(물론 목표는 28등 위로 올라가는 것) 예상보다 더 꼴아박은 49등이 나왔다. 여러 가지 이유가 있었는데, 일단 내가 카이스트 교환학생을 가 있었기 때문에 팀 연습이 아주 힘들었다는 것. 내가 172635 이 분을 열심히 갈궈서(?) 훈련을 시켰어야 했는데 그럴 여건이 안 됐다. 172635 이 분에게 큰 기대를 걸고 있었던 이유.. 2023.11.26

• 

  Python 3.12 업데이트! 유용한 기능 살펴보기 2023년 10월에 Python 3.12가 발표되었다. 개인적으로 이번 업데이트는 언어적 측면에서 새로운 기능을 많이많이 추가했다기보다는 부족한 부분을 보완하고 속도 향상에 초점을 맞춘 것 같다. PEP 695: 타입 매개변수 문법 Python에서 드디어 현대적인 스타일의 제네릭 프로그래밍 문법을 지원한다. def max[T](args: Iterable[T]) -> T: ... class list[T]: def __getitem__(self, index: int, /) -> T: ... def append(self, element: T) -> None: ... 출처: https://docs.python.org/ko/3/whatsnew/3.12.html 사용법은 다른 프로그래밍 언어의 제네릭 프로그래밍 사.. 2023.10.11

• 

  Bomb Lab에 꼭 필요한 gdb 커맨드 모음 굵은 글자는 다른 검색 결과에서 안 알려주는 개꿀팁(?)이다. 1. gdb 시작하기 gdb - gdb를 실행한다. gdb bomb - gdb를 실행하고 gdb 위에 bomb을 올린다. 한편 gdb를 여러 번 실행해서 실행할 때마다 같은 작업을 반복해야 한다면, 다음과 같이 자동화할 수 있다. gdb bomb -x inst.txt - gdb bomb을 실행한 뒤 inst.txt에 담긴 명령을 그대로 수행한다. gdb bomb --command inst.txt - 위와 동일 inst.txt 파일은 상황에 따라 원하는 대로 짜면 된다. 내가 Bomb Lab을 할 때는 이렇게 짰었다. 2. 프로그램 실행, 중단 run - gdb에 올려져 있는 프로그램을 실행한다. r - run의 약어 run 1 2 3 - gd.. 2023.10.08

• 

  [C++] 객체지향, 제네릭 세그먼트 트리 라이브러리 구현하기 이 글에서는 재사용 가능한 제네릭 세그먼트 트리 라이브러리를 구축하는 방법에 대해 알아본다. 세그먼트 트리를 사용할 어떤 상황이 나와도 최대한 복붙만으로 문제를 해결할 수 있게 하는 것을 목표로 한다. 세그먼트 트리의 작동 원리 자체에 대해 설명하는 글은 아니기 때문에 독자가 세그먼트 트리에 대해 어느 정도 이해하고 있다고 가정한다. Motivation 세그먼트 트리는 point update & range query를 O(log N)에 처리할 때 유용하게 사용 가능한 자료구조다. 여기서 range query는 다음과 같은 것들이 주어질 수 있다: 구간 a[l..r]의 합/곱/xor을 구하기 구간 a[l..r]의 최솟값/최댓값을 구하기 구간 a[l..r]의 최대 부분연속합을 구하기 (속칭 금광세그) 구간 .. 2023.10.03

• Scala에서 Continuation Monad를 구현해 보았다 일단 Continuation Monad에 대해 되게 잘 설명한 글을 찾았는데 https://gall.dcinside.com/mgallery/board/view/?id=github&no=35622&search_pos=-38670&s_type=search_subject_memo&s_keyword=continu&page=1 이거다 그리고 내가 왜 Continuation Monad를 구현하고 앉아 있냐...하면 KAIST의 프로그래밍 언어론(CS320)을 독학하고 있었는데 거기서 Continuation Passing Style이 나오고, 처음 봤을 땐 잘 이해가 안 돼서 포기하고 있었다. 근데 이젠 어느 정도 이해함 바로 코드를 보자 private class Cont[R, U](data: (U => R) => .. 2023.09.08

• 

  [백준 26105] Folding Stick (ICPC 2022 Seoul Regional D; Platinum III) 주어진 수열을 연속된 것들끼리 몇 묶음으로 묶되, 묶음에 포함된 막대기들의 길이의 합이 감소하지 않는 수열을 이루도록 하는 문제로 치환할 수 있다. (단, 마지막 묶음만 빼고...) 예를 들어 예제의 1 3 2 3 4 2 2는 다음과 같이 묶일 수 있다: (1 3) (2 3) (4 2) (2) 이렇게 묶이면 각각의 묶음이 4 5 6 2가 되어 마지막 묶음만 빼고 감소하지 않는 수열이 된다. (4 n; std::vector vec(n, 0), pfs(n, 0), dp(n, 0); std::vector stack; for (auto& x : vec) std::cin >> x; pfs[0] = vec[0]; for (int i = 1; i < n; ++i) { pfs[i] = pfs[i - 1] + vec[i.. 2023.08.27

• 

  [백준 28399] 황혼 (UCPC 2023 본선; Platinum IV) 원본 그래프 G의 복사본을 만들어 각각 G1, G2라고 이름붙여줄 수 있다. 만약 주어진 사람이 단순 경로를 처음부터 따라 이동하는 중이라면 그 사람을 G2 위로 보내고, 아니라면 G1 위로 보내자. 그러면 이것은 그냥 그래프이므로, 다익스트라를 돌리면 한 점 위에서 나머지 2n개의 정점으로 향하는 최단 경로의 길이를 구할 수 있다. 다 구한 다음에는 그래프를 다시 하나로 합쳐 주고, 정점에 부여된 가중치는 두 정점의 최솟값으로 잡으면 된다. 이 문제는 체감상 다익스트라를 돌리는 과정보다 구현이 더 까다로웠다. 예를 들면, 내가 지금 주어진 단순 경로 위에 있는지, 있다면 주어진 단순 경로의 다음 정점은 몇 번인지를 어떻게 O(1)에 구하는가? 이 문제를 해결하기 위해 vector를 2개 만든다. 첫 번.. 2023.08.11

• 

  SCPC 2023 (삼성 대학생 프로그래밍 경진대회) 예선 1차 후기 올솔...을 하지 못하고 5번 문제에서 180점을 날렸다. 1234는 만점을 받았다. 대회는 24시간이었는데 당연히 24시간을 다 쏟아붓지는 않고 6시간 정도는 박은 것 같다. 1234 푸는 데 4시간, 5번 왜 억까당하는지 체크하는 데 2시간... 이상한 실수를 많이 했는데, 3번에서 64비트 정수를 안 써서 틀린다든지 하는 짓을 많이 했다. 1 -> 2 -> 3 -> 5 -> 4 순으로 구현했는데 3번 64비트 정수를 안 써서 억까당하고 5번 오답 떴을 때 '아 내 실력이 고작 이 정도인가'하고 멘탈 나가는 줄 알았다. (사실 1, 2번만 풀어도 2차는 진출한다는 얘기가 있으므로 그럴 필요가 전혀 없었다.) 1. 증강현실 배달 안경 (예측 S5-S3) 브루트포스를 한다. 2. 딸기 수확 로봇 (예측 .. 2023.07.29

• 

  [짧은 글] 용필남 사태가 알려주는 것들 판사님 저는 용필남이 무엇의 줄임말인지 얘기 안 했습니다. 1. 극단주의 유튜버들의 구독자는 생각보다 유튜버에게 충성하지 않을 수 있다 이것은 '용'의 유튜브 구독자 수가 날아가고 있는 것으로 설명이 된다. 내가 한 4년 전쯤인가 자기계발 유튜버들을 계속 보면서 느꼈던 게 하나 있는데(그때는 내가 고3이었고, 유튜브 자기계발 유튜브의 현실을 잘 몰라서 가능한 일이었음) 유튜버들이 설명하는 내용들 중에서 내가 틀렸다고 생각하는 게 하나 있다고 하더라도 바로 구독을 취소하지는 않는다. 무언가 잘못 설명하는 내용들이 계속 쌓이고 쌓여서 뭔가 잘못됐다는 생각이 들었을 때쯤에야 탈출을 감행한다. 그러는 이유는 아마도 내가 구독해서 얻는 이익이 잘못된 정보를 받음으로써 얻는 손해보다 더 크다고 생각했기 때문일 것이.. 2023.07.23

• 

  [백준 13261] 탈옥 (분할 정복을 사용한 최적화) (Platinum I) 분할 정복을 사용한 최적화 입문 문제인 탈옥이다. 분할 정복을 사용한 최적화는 한 번 읽어서는 도무지 어떤 방식으로 코드를 짜야 할지 감이 오지 않는다(적어도 나에게는 그랬다). 나에게 있어서 이해를 방해하는 가장 큰 사실은 분할 정복과 DP가 도저히 어울리지 않는 것 같다는 사실이었다. 예컨대 피보나치 DP 문제를 살펴보자. 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> ... 이렇게 한 칸을 계산하는 일이 다음 칸의 계산에 영향을 미친다. 이 DP 문제를 억지로라도 분할 정복으로 계산할 수 있을까? 힘들어 보인다. 애초에 문제의 분할 자체를 어떻게 정의해야 할지도 모르겠다. 일단 탈옥 문제의 DP 식은 다음과 같다. i명의 간수를 사용해서 j번째 감옥까지 감시를 한다면, .. 2023.06.11

• 

  [백준 2740] 행렬 곱셈 (Rust 풀이; Silver V) https://www.acmicpc.net/problem/2740 use std::ops::Mul; use std::fmt::{Display, Formatter}; struct Mat { data: Vec, } impl Mat { fn from(raw_data: Vec) -> Mat { Mat { data: raw_data, } } fn i_len(&self) -> usize { self.data.len() } fn j_len(&self) -> usize { self.data[0].len() } } impl Mul for Mat { type Output = Mat; fn mul(self, rhs: Self) -> Self::Output { let (li, lj) = (self.i_len(), self.j.. 2023.05.01

• 

  [백준 2667] 단지번호붙이기 (Rust 풀이; Silver I) https://www.acmicpc.net/problem/2667 이 블로그는 내가 공부한 것을 올리는 블로그고 나는 BFS 정도는 발가락으로도 짤 수 있기 때문에 자세한 풀이를 올리지는 않는다. 그런데 이 문제를 블로그에 올리기로 결심한 이유는 내가 지금 Rust를 공부하고 있기 때문이다. 그러니까 BFS가 어떻게 돌아가는지 알고리즘은 모두가 알고 있다고 가정하고 자세한 구현을 보자. use std::collections::VecDeque; use std::ops::Add; #[derive(Clone)] #[derive(Copy)] struct Point { i: i32, j: i32, } impl Point { const fn new(i: i32, j: i32) -> Point { Point{i, j.. 2023.04.30

• 

  [백준 12963] 달리기 (Platinum III) https://www.acmicpc.net/problem/12963 최대 유량의 정의를 알고 있다면, 이 문제는 최대 유량을 구하는 문제의 특수한 버전이라는 것을 쉽게 알 수 있다. 그런데 최대 유량 최소 컷 정리에 의해 최대 유량의 값은 최소 컷의 값과 같다. 간선의 value가 3^i 꼴로 주어지기 때문에, 최소 컷의 값을 그리디 알고리즘으로 구하기가 상당히 쉽다. 최소 컷을 구하는 것은 가장 적은 비용의 간선을 자르는 것이므로, 가장 많은 비용의 간선을 살린다고 생각할 수도 있다. 그렇다면 가장 먼저 살려야 할 간선은 가장 value가 큰 간선임이 명백하다. 이는 value가 3^i 꼴로 주어지기 때문에 성립하는 것이고, 일반적인 상황에서는 성립하지 않는다. 이 사실을 증명하는 것은 쉽다. 최종 결.. 2023.04.27

• 

  제1회 와쿠컵 출제 후기 어쩌다가 제1회 와쿠컵으로 출제 데뷔전을 치르게 되었습니다. 그런데 제1회 와쿠컵에 거의 600명이나 되는 사람들이 몰리면서 지금 상당히 부담스러워 하고 있습니다. 이번 와쿠컵에서 K. I LOVE JavaScript O. 지연 평가 이렇게 두 문제를 출제하게 되었습니다. 사실 5문제 정도를 만들었는데 가장 난이도가 낮고 퀄리티가 높다고 생각한 두 문제를 뽑았습니다. O. 지연 평가 이 문제를 첫 번째로 만들었습니다. 아마 5문제 중에 3번째로 만든 문제였던 것 같은데 둘 다 골드 넘어갈 것 같아서 그냥 혼자서 버리기로 결정했습니다. 그렇게 해서 만든 문제가 이 문제였는데 사실 이 문제도 골드를 갈 뻔했습니다. 버전이 총 3개가 있었는데 세상에 나온 버전은 그중에 가장 쉬운 버전이었습니다. 처음에 출제진.. 2023.04.21

• [코딩관련글] It's probably time to stop recommending Clean Code https://qntm.org/clean It's probably time to stop recommending Clean Code @ Things Of Interest It may not be possible for us to ever reach empirical definitions of "good code" or "clean code", which means that any one person's opinions about another person's opinions about "clean code" are necessarily highly subjective. I cannot review Robert C. Mar qntm.org 3줄 요약) 조금의 코드 반복이 가독성에 큰 악영향을 주지는 않는다.. 2023.04.17

• 

  Codeforces 블루 후기 후기...? 가 있어야 되는데 잘 모르겠어요... 전 그냥 문제가 주어지면 풀었을 뿐임... 그리고 Div.2보다 Div.3, Div.4를 많이 참가했으니 저 같이 얍삽한 방법으로 블루 찍지 마세요 2023.04.06

• 

  [백준 2336] 굉장한 학생 (Platinum II) https://www.acmicpc.net/problem/2336 일단 등수대로 적혀 있던 것을 나름대로 잘 해석해서 함수 개개인에게 점수를 부여한다. 점수는 Student 구조체 하나를 만들어서, 거기다 저장할 수 있다. 이제 문제를 단순화해서 만약 시험 결과가 2개만 주어진다면 문제를 어떻게 풀지 생각해보자. 나라면 아마 다음과 같은 그림을 그려서 풀 것이다. 그림의 화살표가 나타내는 것은 알고리즘의 흐름이다. 우선 x좌표가 가장 큰 점에서부터 출발해, x좌표가 점점 작아지는 순으로 각 점들을 방문해 나간다. 이렇게 하기 위해서는 당연하지만 정렬이 필요하다. 이렇게 하면 x좌표에 대한 비교가 이미 끝났으므로 y좌표에 대한 비교만 하면 된다는 사실을 알 수 있다. 점 하나를 방문할 때마다 그 점이 이전.. 2023.03.31

• 

  [백준 11717] Wall Making Game [Platinum II] https://www.acmicpc.net/problem/11717 11717번: Wall Making Game The first line of the input consists of two integers H and W (1 ≤ H, W ≤ 20), where H and W are the height and the width of the board respectively. The following H lines represent the initial board. Each of the H lines consists of W characters. The j-t www.acmicpc.net 다각형 게임과 비슷하게, 행동을 하나 하면 게임판이 여러 개로 나뉘는 문제기 때문에 스프라그-그런디 정리로 문제를 해결.. 2023.03.27

• 

  [백준 25952] Rectangles (ICPC 2022 Seoul Internet; Diamond V) https://www.acmicpc.net/problem/25952 25952번: Rectangles Your program is to read from standard input. The input starts with a line containing an integer $n$ ($1\le n\le 70000$), where $n$ is the number of points given in the plane. In the following $n$ lines, each line contains two integers that represent, r www.acmicpc.net n = 70 000이라는 제약조건이 상당히 생소한 문제다. 보통 n = 100 000 정도를 주면 O(n log n) ~ O(n).. 2023.03.02

• 

  [백준 16998] It's a Mod, Mod, Mod, Mod World [Diamond IV] https://www.acmicpc.net/problem/16998 16998번: It’s a Mod, Mod, Mod, Mod World You are given multiple problems with three integers p, q, and n. Find ${\displaystyle \sum _{i=1}^n((p\cdot i)\text{ mod }q)}$. That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus. www.acmicpc.net $\sum _1^n(pimodq)$의 값을 구하는 문제. 50만 개 정도의 쿼리가 주어지는데.. 2023.02.19

• 

  라빈-카프 알고리즘 구현 꿀팁 라빈-카프의 전체적인 동작 원리를 설명하는 글은 아니다. 문자열 s = a0a1a2...를 해싱으로 f(s)로 보내버릴 때, 다항식을 f = a0 + a1 * c + a2 * c^2 + ... 이렇게 인덱스를 맞춰서 잡기보다는 거꾸로 f = an + a_(n-1) * c + ... 이렇게 잡는 게 더 구현이 쉽다. hashval = (hashval * c + s[i]) % M을 재귀적으로 반복해서 구현할 수 있기 때문. c의 모든 거듭제곱을 전처리하지 않아도 된다. C = c ^ k만 전처리해서 어디다가 저장해 두고 있어도 된다. 첫 번째 해시값을 구했으면 한 칸씩 옮기면서 다음 해시값을 hashval = (hashval * c + s[i] - C * s[i - k]) % M으로 O(1)에 구할 수 있다.. 2023.02.07

• 

  Heap과 Priority Queue의 차이, 그리고 Abstract Data Type이란 무엇인가 얼마 전까지만 해도 나도 헷갈렸던 부분이다. 일단 배경지식이 어느 정도 필요하다. C++에서 스택(std::stack)은 어떻게 구현되어 있을까? std::vector 구현체처럼 그냥 공간을 뭉탱이로 할당해 놓고 공간 부족해지면 늘려서 할당하고 그런 식으로 구현되어 있지 않을까? 대부분의 자료 구조 강의에서도 stack을 그런 식으로 구현하니 말이다. 하지만 실제로는 이렇게 생겼다. 왜 이렇게 끔찍하게 생긴 방식으로 구현되었을까? 사실 이 구현은 양쪽에서 모두 원소를 뽑아 쓸 수 있는 큐인 deque(double-ended queue)에서 한쪽을 막아놓는다는 이상한(?) 방식이다. std::queue 구현도 마찬가지다. 대체 왜 그냥 자료 구조 교과서에 있는 스택을 안 만들고 굳이 deque를 만든 다음.. 2023.02.07

• 

  [백준 21117] Number of Colorful Matchings [Ruby III] https://www.acmicpc.net/problem/21117 21117번: Number of Colorful Matchings Output $n+1$ lines containing your answers for $k=0,1,2,\dots ,n$ respectively. Remember that you only need to output the answer modulo $2$. www.acmicpc.net 알아두어야 할 배경지식이 몇 개 있다. 자세한 사항은 https://en.wikipedia.org/wiki/Permanent_(mathematics) 여기를 참고했다. 1. 이분 그래프 G의 adjoint matrix는 \( \begin{bmatrix} O & A \ A^T & O.. 2023.02.06

• 

  충격!) 파이썬에서 오버로딩(overloading)이 가능하다?? 파이썬은 원래 오버로딩이 안 되는 언어라고 알려져 있었다. 왜냐하면 오버로딩을 하려면 타입이 필요한데 파이썬의 각 변수들은 타입이 지정되어 있지 않기 때문이다. 3.4 이후로 typing 모듈이 생기면서 파이썬에서도 타입 지정이라는 개념이 생기기는 했지만 여전히 optional 요소일 뿐이다. 그런데... 언제부터인지는 모르겠는데, 파이썬에도 타입에 따른 오버로딩이라는 개념이 생겼다. 예제 코드는 다음과 같이 생겼다. import functools as ft @ft.singledispatch def hello(arg) -> None: print("arg type not implemented") @hello.register def _(arg: int) -> None: print("Integer: {}".f.. 2023.02.04

• 

  [백준 18292] NM과 K (2) (Platinum IV) https://www.acmicpc.net/problem/18292 18292번: NM과 K (2) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 1014번 컨닝과 비슷한 Bitmask DP 문제다. 티어도 컨닝과 똑같은 티어가 찍혔다. 3차원 dp로 해결 가능한데 for문은 4중첩으로 돌려야 한다. dp[i][j_bits][k]를 다음과 같이 정의하자 : i번째 행까지 봤고, i번째 행에서 선택을 j_bits와 같이 했으며, 0..i행 통틀어서 k개의 선택을 했을 때, 점수의 최댓값 그 다음 dp[i]에서 dp[i+1]로 가는 .. 2023.01.29

• 

  [백준 1915] 가장 큰 정사각형 (Gold IV) https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP로 풀린다는 사실이 꽤 유명하다. dp[i][j]를 grid[0..i][0..j]에 존재하고 [i][j] 좌표를 차지하는 가장 큰 정사각형이라고 정의하자. 그러면 DP 식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1이다. 이 점화식은 LCS나 knapsack 문제 풀 때처럼 테이블을 순차적으로 방문하면서 칸 채워넣기가 좋은 점화식이다. 시간복잡도는 O(mn)이다. 또한 dp 저장공간 토글링 .. 2023.01.24

• 

  [백준 9658] 돌 게임 4 (Python 풀이, Silver II) https://www.acmicpc.net/problem/9658 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 흔한 DP 문제다. n이 작을 때는 직접 손으로 처리해주고, 점화식 f(n) = not (f(n-4) and f(n-3) and f(n-1))을 넣어주면 끝. @cache 데코레이터를 써서 DP를 자동으로 할 수 있다. 그러나 hashmap을 쓰기 때문에 handwritten DP가 속도가 더 빠를 듯하다. from functools import cache @cache def game(n: int) -> bool: if n 2023.01.22

• 

  [백준 9252] LCS 2 (Python 풀이, Gold IV) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 테이블을 만든 뒤, 테이블 역추적으로 LCS 문자열을 복원하는 문제다. 일단 LCS 문제를 푸는 점화식은 잘 알려져 있다. memo[i][j] = memo[i - 1][j - 1] + 1 (if a[i] == b[j]) memo[i][j] = max(memo[i - 1][j], memo[i][j - 1]) (otherwise) DP 역추적은 이.. 2023.01.18

• 

  [백준 1238] 파티 (Python 풀이, Gold III) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net dijkstra로 푸는 문제다. 일단 잘 구현된 dijkstra 함수 하나를 갖고 오자. 숙련자는 7분 만에 짤 수 있다. 어떤 그래프 G의 한 노드 v에 대해서 v로부터 모든 노드로 가는 최단경로의 거리를 각각 구해주는 것은 쉽다. 그러나 모든 노드에 대해서 모든 노드로부터 v로 가는 최단경로의 거리를 각각 구해주는 것은 약간의 생각이 더 필요하다. 간선의 방향을 .. 2023.01.17

• 

  파이썬 튜플에 대한 충격적인 사실 튜플은 () 괄호 때문에 만들어지는 게 아니라 쉼표 때문에 만들어지는 거임 2023.01.14

• 

  [백준 3904] The Teacher's Side of Math (Diamond IV) https://www.acmicpc.net/problem/3904 3904번: The Teacher's Side of Math One of the tasks students routinely carry out in their mathematics classes is to solve a polynomial equation. It is, given a polynomial, say $X^2-4X+1$, to find its roots $(2\pm \sqrt{3})$. If the students’ task is to find the roots of a giv www.acmicpc.net $\sqrt[m]{a}+\sqrt[n]{b}$를 근으로 갖는 정수 계수 mn차 다항식을 찾는 문제.. 2023.01.12

• 

  [백준 16224] Path Equality (Diamond III) https://www.acmicpc.net/problem/16224 16224번: Path Equality $N$, $M$이 한 줄에 차례대로 입력된다. 입력은 $1\le N\le 500$, $1\le M\le 5000$를 만족한다. www.acmicpc.net 선형대수학 D3 문제치고는 굉장히 어려웠다. 구현이 쉬워서 난이도가 약간 깎인 듯싶다. 일단 결론은 $m\le n$이고 $\sqrt{mn}$이 자연수라는 조건이 필요충분조건이다. () 방향 증명은 어렵다. n = 9이고 m = 1인 경우로 사례연구를 해 보자. tr(A) = 3이므로 9개의 노드 중 3개는 자기 자신을 향하는 loop를 갖고, 나머지 6개는 그렇지 않다. 일단 자기 자신을 향하는 loop를 갖는 3개의 노.. 2023.01.11

• 

  C++ 버전이 바뀌면서 의미가 달라진 키워드들 C++에는 이렇게 많은 키워드가 있다. C++은 C에서 처음 시작했지만 시대가 발전하면서 Python, Haskell 등 프로그래밍의 패러다임을 바꾼 수많은 언어가 튀어나왔고 C++는 30년 동안 그 수많은 패러다임을 다 먹어치울 기세로 커졌기 때문이다. 그 과정에서 C++의 몇몇 키워드는 의미가 바뀌기도 했다. 가장 대표적인 키워드가 inline으로, 이 키워드는 C++에서 함수 실행 오버헤드를 줄이기 위해 함수 호출하는 부분을 그냥 함수 본문으로 대체하는 것과는 전혀 관련이 없다. 모든 C++ 개발자들은 바뀐 키워드의 내용을 숙지하여 모던한 프로그래밍 습관을 기르도록 하자. auto (C에서) storage duration을 auto로 설정함 (C++11부터) 정의된 변수의 타입을 컴파일러가 알아서 .. 2023.01.09

• 

  고속 푸리에 변환, 이론부터 구현까지 1. 구현하기 전에 필요한 지식 고속 푸리에 변환(Fast Fourier Transform; FFT)은 어떤 벡터의 이산 푸리에 변환을 $O(n\log n)$ 안에 구할 수 있게 해주는 쉬우면서도 강력한 알고리즘이다. 푸리에 변환이라고 하니 굉장히 생소해 보이고, 신호 처리나 미분방정식 푸는 데 외에는 쓸데가 없어 보이지만, 사실 이걸 갖고 상당히 많은 일을 할 수가 있다. 예를 들자면 차수가 n인 두 다항식을 $O(n\log n)$에 곱한다. (가장 직관적인 방법으로 계산하면 $O(n^2)$이 나오게 된다.) 크기가 ${10}^n$ 정도인 두 자연수를 $O(n\log n)$에 곱한다. (마찬가지로 직관적으로 곱하면 $O(n^2)$이다.) 자연수 집합의 두 부.. 2023.01.02

• ply 공식문서 6.8절 번역 (번역기 돌림) 불특정 다수에게 공유하려고 번역한 건 아닙니다. 프로젝트 하느라 읽어야 되는데 시간이 없어서 빨리 읽어야 하기 때문에... 만약 필요하다면 최대한 원본과 대조해서 읽으시길 바랍니다. 잘못된 번역이 있을 가능성이 높습니다. 프로덕션에서 사용할 파서를 생성하는 경우 구문 오류를 처리하는 것이 중요합니다. 일반적으로 파서가 단순히 손을 들고 문제의 첫 신호에서 멈추는 것을 원하지 않습니다.프로덕션에서 사용할 파서를 생성하는 경우 구문 오류를 처리하는 것이 중요합니다. 일반적으로 파서가 문제의 징후가 나타나면 손을 들고 멈추기를 원하지 않습니다. 대신 오류를 보고하고 가능한 경우 복구한 다음 구문 분석을 계속하여 입력의 모든 오류가 사용자에게 한 번에 보고되도록 합니다. 이것은 C, C++, Java와 같은 언.. 2022.11.30

• 2022 ICPC 서울 리저널 후기 (짧) 나중에 각 잡고 긴 글로 쓸게요. 최종 결과 6솔, #28 J. 보자마자 실버 5따리 스택 문제인 거 알았다 I. 난 뭔 문제인지도 모르지만, 팀원 선배가 보자마자 한 3분 만에 바로 키보드 잡고 구현 시작함;; 근데 답이 제대로 안 나와서 내가 J 구현하던 중에 우연히 문제가 뭔지 알았다. input 파일 저장 안 해서 계속 같은 답이 나오는 거였음;; I, J 한 번에 솔브. K. 아마 DP인 것 같다. 마찬가지로 팀원 선배가 풀었다. F. 그냥 스위핑한 다음 누적 합을 적절한 배열에 저장해 주고 계속 움직이면서 더해 주면 된다. 이 문제는 심지어 정렬을 미리 해 주기 때문에 더 쉬웠음. // 여기까지 아마 골드인 것 같음 E. 일단 무조건 다익스트라를 써야 한다는 건 알았다. 선배랑 풀이법 의논하던.. 2022.11.19

• 

  2022 아주대학교 프로그래밍 경시대회 (APC) 참가 후기 사실 그렇게 많은 시간을 들이지는 않았다(자고 일어나니까 시험은 이미 시작했는데 저녁 먹어야 했음). 그래도 많이 풀었으니 다행. 전반적으로 문제가 쉬웠는지, 문제를 풀 때 어떤 어려움도 닥치지 않았으므로(...) 그냥 풀이 방법만 나열하겠다. A. O(N) 안에 풀리긴 할 텐데 귀찮으니 정렬 돌려서 O(NlogN)으로 풀 수 있다. B. {index, depth, value} 3개의 항목을 관리해주는 struct를 만들고, 그걸 저장하는 스택을 만들자. depth가 1 늘어날 때마다 스택에 쌓아 주고, depth가 줄어들면 줄어든 만큼 pop해주면 끝. 마지막에 스택 비우는 것 잊지 말자. C. 지문에 장난질 치지 말자. 외국인 학생이 시험 보는 거였으면 어쩌려고... 물론 아니었으니 그렇게 했겠지만... 2022.11.13

• 

  KMP 그림 그리면서 구현 KMP의 Motivation이 무엇인지는 다른 곳에서 쉽게 찾아볼 수 있으니 여기에 굳이 설명을 적지는 않는다. KMP의 까다로운 점은 저 Motivation을 다 알아도 수많은 edge case들 때문에 구현하기가 상당히 까다롭다는 것이다. 유한 오토마타의 개념을 알고 있으면 KMP를 상당히 직관적으로 구현할 수 있다. 일단 ABABCABAC에 대응되는 실패 함수 배열을 살펴보자. A B A B C A B A C pi 0 0 1 2 0 1 2 3 0 실패 함수 := 문자열 s[0:i] 2개를 얼마나 겹치게 놓을 수 있느냐를 숫자로 나타낸 값. 예) i = 7일 때 문자열은 ABABCABA인데 이걸 카피 떠서 하나 더 만들면 ABABCABA ABABCABA임. 그런데 앞 문자열의 뒤 3개랑 뒤 문자열의 .. 2022.11.05

• 

  아름다운 함수형 프로그래밍 정보) 사실 전 함수형 프로그래밍을 이렇게 하는 게 맞는 건지는 잘 모릅니다. 그리고 사실 중간 대체과제의 일부분이라 함수형 프로그래밍 환경도 제대로 구축 못하고 시작했는데, 아마 제대로 짜면 이런 모습이 나올 겁니다. like_data = Flatlist(data) >> find_like >> to_str >> drop(4) >> int print(like_data) 그러니까 결국, 주석이 없어도 이 코드가 "아 대충 전체 데이터에서 좋아요 데이터 찾고 string으로 바꾼 다음에 앞부분 4글자 자르고 int로 바꾸는구나" 정도로 읽힐 수 있다는 게 함수형 프로그래밍의 가장 큰 장점인 것 같음. 2022.11.02

• [C++] TMP로 컨테이너 내부 타입 정보 얻어오기 [템플릿 메타프로그래밍] Motivation 제네릭 프로그래밍을 하고 싶다고 하자. std::vector와 같은 컨테이너 내부의 타입이 몇 바이트인지 확인할 일이 생겼다고 가정해 보자. 컨테이너로 std::vector를 사용한다는 사실을 미리 알고 있다면, 다음과 같이 짜는 것으로 충분하다. sizeof(typename std::vector::value_type) 사실은 이렇게 할 필요도 없으며, 이걸로도 충분하다. sizeof(T) 문제는 우리가 컨테이너로 std::vector가 들어온다는 사실을 모를 때 발생한다. 이렇게 가정해보자. "어떤 타입 X가 들어오는데, 우리는 X가 std::vector 꼴인지 (some custom container) 꼴인지도 모르고 사실 컨테이너인지도 모른다." 이럴 때는 다음의 해결 방법이 우.. 2022.10.22

• 

  [백준 14427] 수열과 쿼리 15 (Gold II) https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 세그먼트 트리 풀이가 정해라고 알려져 있다. 이 글에서는 Tree set 풀이를 다룬다. Tree set 풀이는 Red-black Tree로 구현한 set/map 자료구조가 O(log n) 속도로 최솟값 또는 최댓값을 찾아줄 수 있다는 성질을 이용한다. Red-black Tree는 max height O(log n)을 보장하기는 하지만 세그먼.. 2022.10.18

• 

  PS, 코테 입문자들을 위한 백준 가이드 (시간복잡도, 언어별 추가 시간, solved.ac) (수정 중...) 원래 동아리 활동용으로 남들이 안 알려주는 정보만 모아놨었지만, 생각보다 유입이 많아 보다 더 일반적인 정보도 다룰 수 있게 수정 중입니다 1. 시간복잡도 거의 모든 백준 문제들은 시간복잡도를 명시하지 않습니다. 코드 내용과 실행 시간만 보고 시간복잡도를 100% 정확히 결정하는 일이 불가능하기 때문입니다. 따라서 백준 문제들은 데이터의 크기와 개수를 통해 문제가 요구하는 시간복잡도를 암시하고 있습니다. 예를 들어 지문에서 "시간 제한 : 1초" "첫째 줄에 수열의 길이 n이 주어진다. n은 5,000 이하의 자연수이다." 라고 하면, 문제가 요구하는 시간복잡도는 $O(n^2)$입니다. 다음은 상황에 따라 문제가 요구하는 시간복잡도를 간단히 정리한 표입니다. 시간복잡도 대표 알고.. 2022.10.11

• [C++] 표준 라이브러리 클래스 상속받기 (feat. Maybe 모나드 구현) 나도 몰랐던 사실인데, 표준 라이브러리 클래스를 상속받을 수 있다. 생각해 보면 당연하긴 하다. 표준 라이브러리 클래스도 결국엔 클래스일 테니까... 하지만 그렇게 하는 데는 애로사항이 조금 있을 수 있다. 내부 변수들이 private으로 선언되어 있을 수 있기 때문이다. 이 변수들은 상속받아도 접근할 수 없다. (사실 private이 아니어도 접근하기 어려울 것이다. 어차피 이름을 모르거든...) 하지만 방법은 있다. 이 글에서 C++17 표준 라이브러리 중 하나인 std::optional 클래스를 상속받이 maybe 모나드로 만들어 보자. 일단 std::optional는 값이 있을 수도 없고 없을 수도 있는 객체를 나타내는 클래스이다. 예를 들어 std::string을 int로 바꿔주는 to_inte.. 2022.09.27

• [C++] class Matrix 구현 내가 class Matrix를 아직도 이 블로그에 안 올려놨다니,,, 덧셈, 뺄셈, 곱셈, 스칼라배, 기본행/기본열 연산 등의 기능을 지원한다. 근데 뭐 이거 구현한다고 250줄을 잡아먹냐. template class Matrix { private: T** p; unsigned int n; // size public: explicit Matrix(int _n) : n(_n) { this->init(); } ~Matrix() { if (p) { for (int i = 0; i init(); for (int i = 0; i < n; ++i) { fo.. 2022.09.24

• [C++] 프록시(Proxy) 디자인 패턴 (feat. bitset) 프록시(Proxy)는 대리자라는 뜻을 갖고 있다. 즉 어떤 객체가 하는 일을 그대로 흉내내는 객체이다. C++에서 프록시의 가장 유명한 예시는 바로 스마트 포인터(Smart Pointer)일 것이다. 스마트 포인터는 자신이 소멸될 때 delete 연산자를 알아서 호출해서 메모리 누수를 막는 똑똑한 객체인데, 당연하지만 스마트 포인터 그 자체는 포인터가 아니라 객체이다. 그럼에도 스마트 포인터는 일단 포인터가 할 수 있는 모든 일을 할 수 있도록 설계되어 있다(unique_ptr 같은 경우 복사 연산과 복사 대입 연산이 안 되기는 하지만). 특히 * 연산자와 -> 연산자를 제공하므로 사용자는 스마트 포인터를 그냥 포인터 쓰듯이 쾌적하게 사용할 수 있을 것이다. 이 글에서는 비트셋(bitset)에서 프록시 .. 2022.09.18

• [대학생 수학경시대회] 2011년 제2분야 2번 2. 임의의 $n\times n$ 행렬 $A$에 대하여, $$det\left(\begin{array}{cc}A& A^2\\ A^3& A^4\end{array}\right)=0$$ 임을 보여라. (단, $A$의 모든 성분은 실수이다.) Sol) 주어진 행렬을 다음과 같이 다시 쓸 수 있다. $$\left(\begin{array}{cc}A& A^2\\ A^3& A^4\end{array}\right)=\left(\begin{array}{c}I\\ A^2\end{array}\right)\left(\begin{array}{cc}A& A^2\end{array}\right)$$ 따라서 주어진 행렬은 $2n\times 2n$ 행렬이지만 그 rank가 $n$ 이하이므로 행렬식이 $0$이다. 2022.09.14

• [대학생 수학경시대회] 2016년 제1분야 4번/제2분야 5번 연속함수 $f:[-\frac{\pi }{4},\frac{\pi }{4}]\to [-1,1]$가 구간 $(-\frac{\pi }{4},\frac{\pi }{4})$에서 미분가능할 때, 다음 부등식을 만족하는 점 $x_0$가 구간 $(-\frac{\pi }{4},\frac{\pi }{4})$에 존재함을 보여라. $$|f^{\prime }(x_0)|\le 1+f(x_0{)}^2$$ Sol) 먼저 함수는 단조증가함수 또는 단조감소함수가 아니라면 $f^{\prime }(x_0)=0$을 만족하는 점이 적어도 하나는 존재하게 된다. 그리고 이 점에 대해 부등식이 자동으로 성립.. 2022.09.14

• [C++] Disjoint Set 기초 구현 이건 솔직히 너무 쉬워서 뭐 설명할 게 없음 class DisjointSet { std::vector parent; public: explicit DisjointSet(int n); int get_parent(int idx); bool join(int i, int j); bool _joined_(int i, int j); }; DisjointSet::DisjointSet(int n) : parent(n) { for (int i = 0; i < n; ++i) { parent[i] = i; } } int DisjointSet::get_parent(int idx) { if (idx == parent[idx]) { return idx; } return parent[idx] = get_parent(parent[i.. 2022.09.09

• 

  SUAPC 2022 Summer, 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 Open Contest 참가 후기 최종 결과 : 6솔 (그리고 6솔 중에서 순위 가장 낮음) B번 내비게이션 : 그냥 함수 구현 문제다. std::abs 쓰면 됨. 0:11 B Accepted F번 차의 개수 : 구성적 문제다. 그냥 등비수열이랑 등차수열 출력하면 됨... 0:18 F Accepted C번 패스 : 이것도 구성적 문제다. 간단한 관찰을 통해, 홀수일 때는 항상 불가능하다는 사실을 알 수 있다. 공이 항상 첫 패스한 사람에게 돌아오기 때문. 근데 짝수일 때가 문제였다. 나는 간단한 관찰을 통해 n이 2^k 꼴일 때 2^k부터 1까지 역순으로 출력하면 그게 언제나 답이 된다는 사실을 알았다. 그리고 증명은 안 했지만 "이런 문제는 왠지 곱산술 성질을 가지고 있을 것 같음"이라는 생각을 했다. 그러니까 n=p일 때 참이고 n=.. 2022.09.06

• 

  [백준 22357] 경품 추첨 (UCPC 2021 예선) (Platinum IV) https://www.acmicpc.net/problem/22357 22357번: 경품 추첨 UCPC가 작년에 이어 올해도 온라인으로 열리는 것이 아쉬웠던 청한이는 평행우주를 뒤져서 평소처럼 모두가 한 곳에 모여 대회를 치르는 세계를 찾아냈다. 청한이는 이 세계의 시상식에서 성대 www.acmicpc.net 출력할 수 있는 수의 제한이 500만 이하로 매우 작다는 것에 주목, 번호들을 최대한 구겨넣어서 생성하는 방법을 생각해 보자. 예컨대 K = 2, N = 5라면 다음과 같이 2~26까지의 수를 모두 생성하는 것이 가능하다. 1 6 11 16 21 1 2 7 12 17 22 2 3 8 13 18 23 3 4 9 14 19 24 4 5 10 15 20 25 5 6 11 16 21 26 따라서 등차수열을 .. 2022.09.05

• [대학생 수학경시대회] 2020년 제1/2분야 4번 4. 다음 극한값을 구하여라. $$\underset{n\to \mathrm{\infty }}{lim}{\int }_0^{\frac{\pi }{2}}\frac{{\cos }^{2}x}{1+{\cos }^{2}nx}dx$$ Sol) 먼저, 대칭성에 의해 주어진 식이 $$\frac{1}{2}\underset{n\to \mathrm{\infty }}{lim}{\int }_0^{\pi }\frac{{\cos }^{2}x}{1+{\cos }^{2}nx}dx$$ 와 같음을 관찰한다. 복소수 $x$에 대해 $${\cos }^{2}x=\frac{1}{4}(e^{2ix}+e^{-2ix}+2)$$ 이므로, $z=e^{2ix}$로 치환하면 $$ {{1} \over {2}} \int_0^{\pi} {{\cos^.. 2022.09.03

• 

  [대학생 수학경시대회] 2021년 제2분야 7번 7. 실수 $a,b$에 대하여 행렬 $A$를 다음과 같이 정의하자. $$A=\left(\begin{array}{cccc}a& 1& 1& 1\\ 1& b& 1& 1\\ 1& 1& a& 1\\ 1& 1& 1& b\end{array}\right)$$ 이때 행렬 $A$가 양의 정부호(positive definite)일 필요충분조건은 $a>1$이고 $b>1$임을 보여라. Sol) $(\Leftarrow )$ 행렬 $J$를 모든 성분이 $1$인 $4\times 4$ 행렬이라 하고, 대각행렬 $D$를 $D=A-J$라 하자. 그러면 $D$는 모든 대각성분이 양수인 대각행렬이므로 자명히 양의 정부호이고, 행렬 $J$는 대각화하여 $$.. 2022.09.02

• 

  [백준 25384] 니은숲 예술가 (Diamond V) https://www.acmicpc.net/problem/25384 25384번: 니은숲 예술가 만들 수 있는 조형물의 가짓수를 $998244353$$(=119\times 2^{23}+1)$으로 나눈 나머지를 출력한다. $998244353$은 소수이다. www.acmicpc.net 조형물의 상태로 가능한 것을 아무거나 하나 그려 보았다. 그림과 같이, 네 면 중 인접한 두 면에는 가장 마지막 조각만이 있고, 나머지 두 면에는 연속된 여러 개의 조각들이 나타난다. 따라서 부분 문제를 다음과 같이 정의할 수 있겠다. - $DP(n,i,j)$ : 네 면 중 두 면에 n번째 조각이 나타나고, 한 면에 i~n번째 조각이, 한 면에 j~n번째 조각이 나타남. n = 4, (조각) =.. 2022.08.31

• 

  [대학생 수학경시대회] 2015년 제2분야 8번 임의의 i, j에 대해, 행렬 $X$와, $X$와 관련 없는 임의의 행렬 $A$에 대해 $$\frac{\partial }{\partial x_{ij}}X=E_{ij},\frac{\partial }{\partial x_{ij}}A=O$$ 이다. 여기서 $E_{ij}$는 (i, j)-성분만 1이고 나머지 성분은 0인 행렬이고, $O$는 영행렬이다. 따라서 곱의 미분법에 의해 $$O=\frac{\partial }{\partial x_{ij}}I=\frac{\partial }{\partial x_{ij}}XY=E_{ij}Y+X\frac{\partial }{\partial x_{ij}}Y$$ 로부터 $$ {\partial \over \parti.. 2022.08.29

• 

  [대학생 수학경시대회] 2014년 제1분야 8번 8. 양의 무리수 $\alpha$에 대하여 수열 ${\left\{q_n\right\}}_{n\ge 1}$을 $$q_n=\frac{[n\alpha ]}{n}$$ 로 정의하면 수열 ${\left\{q_n\right\}}_{n\ge 1}$ 은 단조증가수열이 아님을 보여라. Sol) 일반성을 잃지 않고 \( 0 2022.08.29

• 

  [대학생 수학경시대회] 2017년 제1분야 6번 주어진 조건만으로 생각보다 A에 대해 많은 것을 알 수 있는 문제입니다... 2022.08.29

• 

  [대학생 수학경시대회] 2019년 제2분야 7번 7. 벡터 $v_1,v_2,v_3,v_4$는 길이가 각각 2, 3, 4, 5이며 서로 수직이다. 임의의 2차원 부분공간 $W\subset {\mathbb{R}}^4$에 대하여 $v_1,v_2,v_3,v_4$를 $W$에 정사영하여 얻은 벡터들 가운데 적어도 하나는 길이가 1이 아님을 보여라. Sol) 일반성을 잃지 않고 $v_1=2e_1,v_2=3e_2,v_3=4e_3,v_4=5e_4$라 하자. 그리고 선형사상 T를 Tv = (v의 W 위로의 정사영)으로 잡는다. 이제 네 정사영의 길이가 모두 1이라 가정하면 $$ \left\langle e_1, Te_1 \right\rangle = {1 \over 4}, \left\langle e_2, Te.. 2022.08.28

• 

  [대학생 수학경시대회] 2021년 제2분야 6번 대한수학회에서 공식 제공하는 대학생 수학경시대회의 해설은 깔끔한 풀이보다는 색다른 풀이를 선호하는 경우가 많다. 그래서 여러 가지 방법으로 풀 수 있는 문제들에 대해서는 여러 풀이를 알아두는 것이 좋다. '행렬의 고유벡터는 그 행렬을 설명하는 특성 중 하나다'를 잘 나타내주는 문제라고 생각한다. 2022.08.28

• 

  [백준 5615] 아파트 임대 (Feat. 밀러-라빈 소수 판정법) (Platinum I) https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 매우 자명한 어떤 절차에 의해, 2N + 1이 소수가 되는 N을 찾는 문제임을 알 수 있다. Naive한 소수 판별을 짜면 시간복잡도 $O(T\sqrt{N})$이 나와서 TLE가 난다. 시간복잡도를 줄일 수 있는 방법으로 밀러-라빈 소수 판정법을 이용하자. a = 2, 7, 61에 대하여 $n-1=2^{s}d$로 놓는다. $a^d\ne 1\mathrm{mod}n$이고, 모든 r : 0 ~ s.. 2022.08.28

• 

  [백준 9206] 나무 말고 꽃 (Platinum II) https://www.acmicpc.net/problem/9206 9206번: 나무 말고 꽃 선영이와 남자친구의 2주년이 얼마 남지 않았다. 선영이는 그를 위해 특별한 것을 사주려고 한다. 남자친구는 나무에 관심이 매우 많다. 하지만, 선영이는 나무는 선물로 매우 크다고 생각한다. www.acmicpc.net 수치해석 문제들이 다 그렇듯이 수많은 시도를 해야 풀 수 있다... 일단 constexpr로 각종 상수를 정의해 주자. constexpr value들은 컴파일 시점에 평가되기 때문에, #define 같은 매크로의 기능을 거의 모두 쓸 수 있으면서 그것보다 더 안전하다고 할 수 있겠다. constexpr long double PI = 3.1415926535897932384626l; constexpr .. 2022.08.26

• 

  C++로 문서 작성 프로그램 만들기 - 1. 클래스 다이어그램 짜기 [객체 지향 프로그래밍 프로젝트 가이드] Motivation 객체 지향 프로그래밍 과제 프로젝트라 함은 무언가 엄청난 발명을 해서 실용적인 것을 추구하기보다는, 객체 지향 프로그래밍을 잘 이해할 목적으로 만들어지는 것이다. 그러므로 기본적으로 주제 선정에 있어서 4 Pillars of OOP를 마음에 새기는 것이 중요하다. 캡슐화(Encapsulation) 상속(Inheritance) 추상화(Abstraction) 다형성(Polymorphism) 개인적으로 나는 Polymorphism을 써서 만들 수 있는 프로그램이 뭐가 있을지 떠올리는 게 가장 힘들었다. 그러다가, "print() 멤버 함수로 문자열도 출력하고 표도 출력하고 그래프도 출력하는 프로그램이 있으면 재미있지 않을까?"라는 생각이 갑자기 들어서, 그때부터 보고서 작성 프로그램의 기획.. 2022.08.26

• C++ Dynamic Programming 꿀팁 다음과 같이 코드를 짜면, memoization DP를 전역 변수 없이, 불필요하게 많은 함수 인자 없이 안전하게 짤 수 있다. #include int main() { std::vector memo(100, std::optional()); std::function fibonacci = [&fibonacci, &memo](uint32_t i) -> int { if (memo[i].has_value()) { return memo[i].value(); } return i 2022.08.23

• 

  [백준 18222] 투에-모스 문자열 (Silver II) 5줄 안으로 구현하기 https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 문제에서는 숫자를 1부터 세지만 우리는 편의상 숫자를 0부터 세도록 하자. 임의의 자연수 n에 대해, n의 2진수 표현에서 비트 값을 (아무 위치에서나) 1만큼 바꿔 준 수 m을 고려하자. 그러면 n번째 투에-모스 문자열과 m번째 투에-모스 문자열 값은 그 parity가 반대임을 알 수 있다. 따라서 n의 2진수 표현의 비트 수를 세 준 뒤 2로 나눈 나머지를 출력하기만.. 2022.08.20

• 

  [백준 25323] 수 정렬하기, 근데 이제 제곱수를 곁들인 [UCPC 2022 예선] (Platinum V) https://www.acmicpc.net/problem/25323 25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인 양의 정수로 이루어진 길이가 $N$ 인 수열 $A_1,A_2,\cdots ,A_N$이 존재할 때, 다음 행동을 원하는 만큼 반복할 수 있다. $1\le i,j\le N;i\ne j$이면서 $A_i\times A_j$가 제곱수인 $i$, $j$를 선택해, $A_i$와 $A_j$ www.acmicpc.net AB가 제곱수이고, AC가 제곱수이면 BC도 제곱수이다. 증명 : (A^2)BC가 제곱수고, 제곱수를 제곱수로 나누면 제곱수라는 사실로부터 자명하다. 반대로 AB가 제곱수이고, AC가 제곱수가 아니면, BC도 제곱수가 아니다. (증명은 위와 똑같이 하면 된다) -> 수열이 몇 .. 2022.08.20

• 

  [백준 1168] 요세푸스 문제 2 (Platinum III) (Feat. PBDS) - 세그먼트 트리 없이 풀기 https://www.acmicpc.net/problem/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 컴퓨터공학과에서 를 수강한 학생들이라면 std::set이 레드-블랙 트리로 구현되어 있다는 것을 알 것이다. 레드-블랙 트리는 Binary Search Tree다. 즉 원소들이 나름의 순서를 갖추고 정렬되어 있다는 것이다. 정렬되어 있다는 것은, 마치 Binary Search 하듯이 k번째 원소를 O(logn) 안에 접근할 수 있음을 함의한다. 그러나 그것을 하기 위해서는 rb-tree의 각 노드들이 subtree의 개수를 저장하고 있어야 한다. std::set은 이 기능을 제공하.. 2022.08.17

• [C++] Segment Tree 라이브러리 만들기 Segment Tree는 PS에서 정말 자주 사용되는 자료구조 중 하나다. 그러나 Segment Tree에 들어갈 타입도 int, long long, derived-type 등 제각각, 연산도 add, multiply, min, max 등 제각각이므로 그냥 Generic programming으로 클래스 하나를 만들었다. 이 Segment Tree는 타입 T와 함수객체 BinaryOP를 받는다. T에 타입 넣고 BinaryOP에 인자 2개 받는 operator() 정의하면 끝. /* * Segment-tree! */ template class Segment_tree { std::vector tree; int size; public: explicit Segment_tree(const std::vector &.. 2022.08.16

• 

  C++로 문서 작성 프로그램 만들기 [객체 지향 프로그래밍 과제 가이드] 많은 대학에서 객체 지향 프로그래밍을 가르칠 때 프로젝트를 시킨다. 그러나 16주라는 짧은 기간 안에 4 Pillars of OOP도 끝까지 가르치기는 힘들다. 교수님이 잘못하셨다는 게 아니라, 원래 4 Pillars of OOP에 익숙해지는 과정에서 신문법을 다수 익혀야 하다 보니... 그래서 신문법 배우기에 바빠 설계법까지 미처 배울 시간이 없는 경우가 종종 있다. 그래서, 내가 본 어떤 프로젝트에서는 '여자' 클래스를 만든 뒤 '여자' 클래스를 상속받는 '사람' 클래스를 만들기도 하더라. 그래서 훗날 객체 지향 프로그래밍 과제를 하게 될 불쌍한 사람들을 위해 이 게시글을 쓰게 되었다. 프로그램의 소스 코드 길이는 과제를 마친 2022년 6월 19일 기준으로 2280줄이다. 그 중 약 200줄 정도가.. 2022.08.15

• 

  유용한 비트 연산들 출처 : , 안티 라크소넨 x | (1 2022.08.11

• [C++] 볼록 껍질 클래스 구현 임의의 개수의 2차원 점을 input으로 받아, 볼록 껍질 객체를 만들어 주는 클래스이다. using namespace std; class Point { public: long long x, y; Point(long long _x, long long _y) : x(_x), y(_y) {} Point operator-(const Point& rhs) const { return Point(x - rhs.x, y - rhs.y); } bool operator x * rhs.y) { return false; } else { return x * x + y * y < rhs.x * rhs.x + rhs.y * rhs.y; } } bool operator==(const Point& rhs) const { return.. 2022.08.07

• [C++] 다항식 클래스와 라그랑주 보간법(Lagrange Interpolation) 구현 다음 문제를 풀다가 다이나믹 프로그래밍으로 푸는 법이 생각이 안 나서 Lagrange Interpolation으로 밀어붙이려고 했다. 사실 생긴 것만 봐도 다이나믹 어쩌고저쩌고보다는 수학 문제를 닮아 있는 것 같지 않은가? 사실 이 문제에 대한 일반화는 이미 존재하고, 베르누이 수열인가 뭔가를 쓴다고 알고 있지만 그걸 굳이 알고 싶지는 않았다. 그리고 도전 중인 문제가 하나 더 있는데 그 문제에서도 Lagrange Interpolation을 쓰기 때문에 어차피 한 번은 이걸 구현해야 해서, 그냥 오늘 구현하기로 했다. 특이사항으로, class Polynomial을 구현할 때 std::vector를 쓰지 않았다. C++의 이동 연산에 대해 공부하고 있었기 때문에 이동 연산을 구현해야 했기 때문이다. 시간복.. 2022.08.07

• [C++] SCC Maker class 타잔 알고리즘으로 SCC를 만들어주는 클래스. 설명은 나중에 적어야지... class SCCMaker { public: std::vector adj; std::vector id; int next_id; std::stack s; std::vector is_in_scc; std::vector scc; SCCMaker(std::vector &vvi) : id(vvi.size(), -1), next_id(0), is_in_scc(vvi.size(), false) { adj.swap(vvi); for (int i = 0; i < adj.size(); ++i) { if (id[i] == -1) { id[i] = next_id++; dfs(i); } } std::sort(scc.begin(), scc.end(), [.. 2022.08.06

• 

  [백준 18542] Permutant (Ruby III) 풀이 https://www.acmicpc.net/problem/18542 18542번: Permutant Consider an $n\times n$ matrix $A$. Let us denote element in $i$-th row and $j$-th column as $A_j^{(i)}$. You are given a sequence $a_1,\dots ,a_n$ and a permutation ${\pi }_1,\dots ,{\pi }_n$ such that the first row is formed by sequence \(a_k www.acmicpc.net 먼저 주어진 Permutation는 Linear Transform의 일종임을 파악해야 한다. 예를 들어, Permutation {.. 2022.08.04

• [C++] 선분 교차 판정 선분 교차 판정이란 말 그대로 두 선분이 교차하는지 아닌지 판정하는 것이다. 선분 교차 판정을 효율적으로 하기 위해서는 CCW(또는 signed area)에 대한 지식이 필요하다. CCW(또는 signed area)란? 세 점 A, B, C에 대하여 선분 BC가 AB에 대하여 시계 방향으로 휘어져 있는지 반시계 방향으로 휘어져 있는지 판정하는 것으로, 2차원에서 determinant의 개념을 응용하는 기술이다. 두 2차원 벡터 u, v의 determinant는 2가지 정보를 담고 있다. 그 절댓값은 두 벡터 u, v가 생성하는 평행사변형의 넓이를 알려주고, 그 부호는 v가 u에 대하여 시계 방향으로 휘어져 있는지 반시계 방향으로 휘어져 있는지를 알려준다(+: 반시계, -: 시계). PS계에서는 CCW라는.. 2022.08.04

• [C++] 유리수 클래스(class Fraction) 구현 프로그래밍을 할 때 실수를 쓸 일이 있으면 대부분 double을 사용하지만 PS계에서는 스페셜 저지가 붙어 있지 않은 한 이런 행위는 죄악에 가깝다. 대표적인 예시가 바로 4225번. square-root를 다루는 주제에 스페셜 저지도 안 붙어 있어서, 입력값이 10000 이하임에도 불구하고 int128을 써야 하는 괴상한 문제다. 어쨌든 높은 정밀도를 위해서는, long double에 안주하지 말고 더 정확한 값을 얻을 수 있는 방법이 무엇일지를 생각해 놓아야 한다. 오차는 계산할 때마다 계속해서 불어나는 성질이 있다. 2.5를 반올림해서 3으로 표현한다면, 2.5 * 2.5는 실제로는 6.25지만 데이터 상으로는 3 * 3 해서 9가 되는 것이다. double을 쓰면 어쩔 수 없이 오차가 있을 수밖에.. 2022.08.04

• [C++] AVL Tree와 이를 이용한 Ordered-Set 구현 C++을 컴파일할 때 G++ 컴파일러를 쓰는 사람은 PBDS(Policy-Based Data Structure)라고 해서 유용한 연산들을 많이 제공해 주는 자료 구조를 쓸 수 있다. 하지만 난 Xcode를 쓰기 때문에 PBDS를 못 쓴다! 그래서 그냥 내가 만들기로 했다. 밑의 코드는 AVL Tree를 통해 Ordered-Set을 구현한 것이다. Ordered-Set이란? 기존의 Balanced Binary Search Tree 기반의 Set에 몇몇 기능을 추가한 것이다. 주요 기능으로 다음 두 가지 기능이 있다. find-by-order : Set의 n번째 원소가 무엇인지를 O(log n) 안에 찾아준다. order-of-key : Set의 원소 k가 몇 번째로 작은 원소인지를 O(log n) 안에 찾.. 2022.08.04

• [C++] class Modulo: 나머지환에서의 사칙연산을 구현해 보자 설명은 나중에 써야겠다. template class Modulo { private: long long n; public: Modulo() = default; constexpr Modulo(long long _n) : n(_n >= 0 ? _n % P : (P - (-_n % P)) % P) {} constexpr Modulo operator+(const Modulo& rhs) const {return Modulo((n + rhs.n) % P);} constexpr Modulo& operator+=(const Modulo& rhs) {*this = *this + rhs; return *this;} constexpr Modulo operator-() const {return n == 0 ? Modulo(0).. 2022.08.04

• 

  [짤] 치료가 필요할 정도로 심각한 '백준 중독증'입니다. 2022.08.02