모든 글
-
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
-
100문 100답 (2024.01.24 ver.)
1. 이름 : 송혜근 2. 키 : 182cm 3. 몸무게 : 90+kg (부정확함) 4. 혈액형 : O+ 5. MBTI : INTJ 6. 고향(태어난 곳) : 수원 7. 현재 사는 곳 : 대전 카이스트 옆 궁동 어딘가 (조만간 사라짐) 8. 안 가봤지만 가보고 싶은 곳 : 잘 모르겠음 사람 사는 데가 뭐 얼마나 다를 거라고 9. 가봤지만 또 가고 싶은 곳 : 샌프란시스코 10. 생년월일 : 2001/01/10 (작년에는 주민번호 6자리 유출하는 기분이라 쓰기 싫다고 해 놨군 이 정도는 충분히 주지 뭐) 11. 시력 : 나도몰라 근시 왼쪽 마이나스 얼마 오른쪽 마이나스 얼마 난시 얼마 이걸 어케 다 기억하냐고 2020 기준으로 시력 공익 가능할 만큼 나쁨 12. 신발 사이즈 : 280 13. 가족 관계 :..
2024.01.24
-
[백준 1285] 동전 뒤집기
\( N \leq 20\)이므로 \(2^N\) 또는 그에 준하는 풀이를 생각해볼 만하다. 가로 \(N\)개의 줄, 세로 \(N\)개 줄 중 무엇을 뒤집을 것인지 생각하는 문제이므로 존재할 수 있는 선택의 개수는 \(2^{2N}\)이다. 그중에서 가로줄과 세로줄 중 하나가 몇 번 줄을 뒤집을지 그 상태가 이미 정해졌다면(편의상 세로줄이라 하겠다), 가로줄에 H가 더 많으면 가만히 놔두는 것을 선택하고 T가 더 많으면 뒤집는 것을 선택하는 그리디 알고리즘을 생각할 수 있다. 이것이 성립하는 이유는 세로줄이 이미 선택된 이상 모든 가로줄은 서로 영향을 주지 않는 독립이므로 순간의 최적 선택이 전체 최적 선택을 담보하기 때문이다. 한 번 그리디 알고리즘을 시행할 때마다 전체 셀 개수인 \(O(N^2)\)의 시간..
2024.01.10
-
검은 invrtd든 흰 invrtd든 버그만 잘 잡으면 그만이다
컴퓨터공학에 대한 작은 고찰 0. 난 내가 컴공을 2021년 9월부터 시작했다고 말하지만, 실은 전에도 스크래치나 파이썬을 깔짝거려 본 경험 정도는 있었다. 중학생 때 스크래치 노가다로 스도쿠 푸는 프로그램 같은 걸 만들어본 적 있었고(6x6 허접임), 고등학생 때 파이썬은 대체로 수학 소논문 같은 거 쓸 때 시뮬레이션 용도로 썼었다. 예를 들면 "클래시 로얄 점수 분포가 정규분포가 아님을 증명한 그 소논문" 같은 데서 점수 시뮬레이션 돌리거나 할 때. 그랬기 때문에 난 컴공을 그 시절부터 배웠다고 말하는 걸 꺼린다. 인간은 언제 컴퓨터를 제대로 알게 되나, 하고 물어본다면 나는 이렇게 대답하고 싶다. 시간복잡도를 알았을 때 컴공이 된다고. 왜냐하면 그 시점이 되어서야 컴퓨터는 긍정하기만 하는 기계가 아..
2024.01.08
-
글쟁이를 위한 해시태그
이게 뭐시여~ 원래 여기는 inverted.h가 주인장인 코딩/개발 블로그인데 이번만큼은 박예담 빙의해서 작성함 1. 글을 쓰게 된 계기 인간에 대해 이해하고 싶어서일 거임 아마 2. 하루에 쓰는 분량 시 쓰는 사람은 하루에 그렇게 많이 쓰지 못해가주구 요즘은 2주에 한 편꼴로 쓰고 있는 것 같습니다 이것보다 더 많이 쓸 수 있긴 한데, 시인의 딜레마라는 게 쌓인 일이 많다 -> (+) 얻을 수 있는 글감이 많다 (-) 시 쓰기 전에 그 일을 해야 한다 쌓인 일이 적다 -> (+) 시 쓸 시간이 많다 (-) 얻을 수 있는 글감이 적다 이 굴레에서 벗어날 수가 없음 3. 슬럼프 극복하는 방법 극복을 안 했음 4. 작업곡 / 노동요 시 쓸 때만큼은 노래 안 듣습니다 단어 하나하나에 초집중해야 해서 집중한 꼬..
2024.01.06
-
231225, [민트초코 프라페]
기계로 얇게 갈아 만든 파랑을 씹는다 잘근잘근 다리를 떨고 애플펜슬로 낙서를 하고 오도방정을 다 하면서 세상이 그렇지 않니 뭘 구분하는 데는 두 가지 색이면 충분해 민트색 아님 초코색이다 이거지 금방 몸에 녹아버리는 설렘 뭔가 입에서 부서질 때만 나오는 세상 젤 예쁜 폭발 아 힘겹다아 민트초코에 내가 녹아버리고 싶을 만큼 요거트 위에 강원에서 산지직송한 날것의 과육 넌 씹는다 잘근잘근 난 빨강과 하양에서 민트와 초코를 찾지 생각이 넘 많아 흘러 넘쳐버리겠어어어서 당신 행복해 보여 딸기는 딸기 케이크 그리고 딸기 바나나 딸기 와플 아님 딸기 아이스크림까지 어딜 가도 그리 아픈 맛은 아닐 것 같아서 하늘을 봐 민트색 배경에 초코 색 구름 또는 딸기 색 별에 요거트 색 안개 색이 많단 건 알아 민트랑 초코 말..
2024.01.01
-
2023 제2회 미적확통컵 출제 후기
귀찮으니까 빨리 적어야지 미적확통컵 특) 플래 겁나많음 1회 미확컵보다 솔브드 기여 난이도는 낮게 잡힐 것 같은데 1회 때 웰노운이 많았던 것과 달리 2회 때는 그런 게 없어서 사람들이 좀 고전하는 것 같았다 60분 이내에 솔브가 나지 않은 문제가 1회 3개 -> 2회 5개로 늘었고 푼 사람이 1자리 수인 문제가 1회 3개 -> 2회 6개(...)로 늘었다 CD 결혼식이 끝나고 PE 최고의 크리스마스트리 두 문제를 출제했다 결혼식이 끝나고 퍼솔 84분, 푼 사람 8명 내가 미적확통컵에 맨 마지막으로 들어간 출제진이다. 정확히 말하면 추가합격인데 8월쯤에 출제진 한 분이 빠지셔서 추가모집 때 내가 들어갔어요 이것도 사실 겨우겨우 들어갔음 하루님이 메일을 보내셨는데 스팸메일함으로 쏙 들어가버린겁니다 그래서 ..
2023.12.24
-
카이스트 교환 12-14주차 - 냉장고사회
유년 시절을 샌프란시스코에서 살다 철학 박사학위를 받고 나서야 처음으로 한국에 방문한 철학자 김예원은 한국을 냉장고사회 (Refrigerator Society)로 진단했다. 그 이유는 ㅈㄴ 춥기 때문이다. 요새 나도 한국이 냉장고사회라는 것을 뼈저리게 느끼고 있는데 패딩을 입지 않으면 얼어 죽을 것 같다는 목숨의 위협을 느낀다. 하지만 패딩이 없다. 옷 옮길 때 안 예쁘다는 이유로 후순위로 미뤄뒀던 게 이렇게 되돌아오는 것이다. 하지만 어쩌겠는가 그냥 그런 대로 살아야지 오늘의 일기 스타트 11/15 수 카이스트에서 뭔가를 한다고 했다. 근데 그게 학생들이 부스 운영하고, 푸드트럭 오고, 이런 건 알겠는데 그게 뭐였는지 기억 안 난다. 설영이랑 같이 부스 잠깐 들렀다. 쿠키 장식 만들고 뭐 만들고... ..
2023.12.03
-
ICPC 2023 본선 후기 (망함)
팀 멤버는 armyantking (P1), invrtd_h (D1), 172635 (P5). 내가 작년에 리저널 28등을 했음에도 불구하고 (팀명은 codingMinsu) 올해도 그만큼의 성적을 기대하긴 힘든 상황이었다. 가장 큰 전력이었던 bbb1293 (D5) 형님이 졸업하셔서 더 이상 ICPC를 치지 못하시기 때문. 그래서 대회 치기 전에는 30-40등을 기대하고 있었는데(물론 목표는 28등 위로 올라가는 것) 예상보다 더 꼴아박은 49등이 나왔다. 여러 가지 이유가 있었는데, 일단 내가 카이스트 교환학생을 가 있었기 때문에 팀 연습이 아주 힘들었다는 것. 내가 172635 이 분을 열심히 갈궈서(?) 훈련을 시켰어야 했는데 그럴 여건이 안 됐다. 172635 이 분에게 큰 기대를 걸고 있었던 이유..
2023.11.26
-
카이스트 교환 10-11주차 - 인생망했음
안녕하세요 저는 카이스트에서 공부를 '안' 하고 있는 inverted.h입니다 (갑자기 닉네임 길이 늘어난 이유: 변수명에 줄임말을 쓰지 말라는 클린코드 원칙에 따라 닉네임 바꿀까 생각 중;;) 인생이 망했다는 선언은 대부분의 경우 삶에는 자신이 인지하지도 못하는 제3의 길이 있다는 것을 망각한 인간의 한탄 정도로 그 뜻이 축소된다. (내가 실제로 그렇게 살아왔다) 그럼에도 불구하고 자신이 정말로 인생 망했다는 선언을 하고 싶다면, 그것을 증명하기 위해 우리는 어떤 노력을 해야 하는가? 개인적 측면에서, 사회적 측면에서 어떤 노력을 해야 사람들에게 자기 인생이 망했다는 것을 설득시킬 수 있을까? 오늘의 일기 스타트. 시험 성적이 대충 나오고 있긴 한데요 카이스트 OTL에 들어가보면 과목 후기를 남길 때 ..
2023.11.12
-
[재귀함수가 뭔가요?]
독일의 사업가 R씨는 다음과 같이 연설했다. 여러분, 우리는 더 일할 필요가 없습니다! 인공지능이 모든 일을 해결해줄 테니까요. 모든 직업은 없어지고, 인공지능에 넣을 데이터를 정제하는 직업만이 살아남을 것입니다. 그리고 끝내 그 직업도 사라지고 말겠죠. 인공지능에 넣을 데이터를 정제하는 인공지능이 나타날 테니까요. 모든 인류는 인공지능에 넣을 데이터를 정제하는 인공지능에 넣을 데이터를 정제하는 직업만을 갖게 될 것입니다. 그리고 인공지능은 끝끝내 그 직업까지도 먹어버릴 것입니다! 인공지능에 넣을 데이터를 정제하는 인공지능에 넣을 데이터를 정제하는 인공지능이 등장하고 나서는 말입니다. 결국 우리는 인공지능에 넣을 데이터를 정제하는 인공지능에 넣을 데이터를 정제하는 인공지능에 넣을 데이터를 정제하는 직업을..
2023.11.10
-
카이스트 교환 9주차 - 기록이 쌓이면 뭐시기가 된다
안녕하세요 저는 카이스트에서 공부를 하고 있는 내 이름이 뭐였더라? 하지만 이름이 없더라도 일기는 계속되어야 한다 당신의 인생은 카이스트 거위보다 아름다웠나? 난 아니었다. 오늘의 일기 스따뜨 10/20 금 카이스트 교환 9주차 - 라는 제목을 갖고 있는 이 일기는 빡대가리 같게도 8주차 금요일부터 시작한다. 언어학자 소쉬르는 이런 사실을 밝혀냈다. "노랑"과 "녹색"을 생각해보자. 그러면 노랑과 녹색 사이에 있는 테니스공 같은 색은 어디부터 노랑이고 어디부터 녹색이라고 할 수 있을까? 소쉬르에 따르면 그것은 정해진 것이 아니다. 문화마다 다르기 때문에 외국인이 옵틱 옐로라고 이름붙인 색을 보고 한국에 있는 코 큰 할아방탱이가 녹색이라고 왕발진하는 일이 생긴다. 의미의 지도는 연속적이고 단어는 그 의미의..
2023.10.28
-
카이스트 교환 7-8주차 - 흐트러지기
안녕하세요 저는 카이스트에서 공부를 하고 있는 INVRTD.H입니다 (my id is case insensitive) 카이스트에 온 지 절반이 지나가고 있고, 안타까운 사실은, 내가 왜 여기 왔는지 슬슬 까먹기 시작하고 있다. 물론 지난번에도 말했듯이 난 지스트에서 도망친 게 맞지만, 시인은 자신이 만든 세계로 도망친 뒤 그 세계를 몰고 지구를 들이받는 사람이기 때문에(??) 카이스트에서 랩실을 찾든 뭘 하든 아무튼 해야 한다. 사는 대로 생각해서는 안 된다. 아시겠어요 오스트랄로피테쿠스 씨? 오늘의 일기 스타트사람에게는 몇 시간의 공부가 필요한가7-8주차라는 도발적인 제목에서 알 수 있듯 나는 시험기간이었고, 시험기간이란 시험을 제외한 모든 것이 잼이있어지는 기간이다. 이를 극단적으로 보여주는 사례 하..
2023.10.22
-
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
-
230421, [아무래도 나르시시즘의 시대]
그러니까 글쎄 내가 오늘 뭘 봤냐면, 대학생따리가 30만 원은 돼 보이는 옷을 입고 등교하는 걸 봄. 대학생따리가. 자기 분수(magnetic fountain)에 맞는 삶을 살아야지 아무래도. 예, 보시는 것처럼 요즘 대학가에는 자신의 수준도 모르고 과소비를 즐기는 사람들이 넘쳐나는데요, 이처럼 노답 인생을 살고 있는 한 대학생 단체가 있다고 해서 화제가 되었습니다. 이 단체는 한 대학교에 설립된 동아리로, 요즘 대학생들 사이에서 빠르게 퍼지는 ‘기부’ 문화를 실행하는 동아리라고 합니다. ‘기부’는 영어 단어 ‘give’에서 온 말로 사회적 약자에게 자신의 노동력을 나눠준다(give)는 뜻인데요, 이처럼 이들이 문화 사대주의에 빠지며 자신의 노동력을 낭비하는 이유는 대학생 사이에서 빠르게 퍼지는 나르시시..
2023.10.06
-
[C++] 객체지향, 제네릭 세그먼트 트리 라이브러리 구현하기
이 글에서는 재사용 가능한 제네릭 세그먼트 트리 라이브러리를 구축하는 방법에 대해 알아본다. 세그먼트 트리를 사용할 어떤 상황이 나와도 최대한 복붙만으로 문제를 해결할 수 있게 하는 것을 목표로 한다. 세그먼트 트리의 작동 원리 자체에 대해 설명하는 글은 아니기 때문에 독자가 세그먼트 트리에 대해 어느 정도 이해하고 있다고 가정한다. Motivation 세그먼트 트리는 point update & range query를 O(log N)에 처리할 때 유용하게 사용 가능한 자료구조다. 여기서 range query는 다음과 같은 것들이 주어질 수 있다: 구간 a[l..r]의 합/곱/xor을 구하기 구간 a[l..r]의 최솟값/최댓값을 구하기 구간 a[l..r]의 최대 부분연속합을 구하기 (속칭 금광세그) 구간 ..
2023.10.03
-
카이스트 교환 4-5주차 - 서랍 속에 넣어둔 꿈 한 조각
안녕하세요 저는 KAIST에서 공부를 하고 있는 인버트입니다 지스트라는 안전지대를 떠나 처음 온 카이스트라는 환경은 모든 것이 낯설기만 합니다 는 개뿔 그냥 대학이잖아! 다른 곳에서도 같은 것을 공부하고 같은 언어를 쓰며 살아갈 수 있다는 것은 축복일까 권태의 징조일까 이번 주의 일기 시작 9/18 별 일은 없다 하늘이 예뻐서 찍어 보았다 하늘이 예쁘다 음... 버클리의 하늘보다는 덜 예쁘다 근데 이런 하늘마저도 그렇게 자주 주어지는 것은 아니다 최근 한동안 비가 너무 자주 와서 기분이 우울했었다 비구름은 마치 야외에조차도 천장을 규정하는 힘 같다 마치 잘 만들어진 판옵티콘이다 비 오는 날씨는 탁 트인 날씨가 좋았다 예쁜 것은 사람을 의존적이게 만든다 닭볶음탕을 먹었다 사실 닭도리탕이 표준어다 사실 닭뭉..
2023.09.27
-
카이스트 교환 2-3주차 - 인생이라는 망겜에서 낙오되지 않기
안녕하세요 저는 카이스트에서 공부를 하고 있는 학부생 invrtd.h입니다 요즘 일기를 많이 쓰죠? 보고 싶은 사람들이 많기 때문이야 내가 아무래도 선톡을 하는 걸 어려워하는 스타일이다 보니까 내가 좋아하는 사람들도 날 대하기 부담스러워하지 않았을까, 하는 생각을 잠깐 해 봤어 (그래서 제가 엄청난 인스타 예찬론자입니다 서로에게 선톡을 할 계기를 제공해 주니까) 그럼에도 불구하고 항상 이 글을 읽는 여러분들께 고마워하고 있다는 걸 알아줘요 (나 짜증나게 한 사람들 제외) 가자 알수없는 세계로 중간에 급발진해서 Splay Tree 자료구조를 설명하거나, 김영하와는 다르게 내가 짜증이라는 단어를 좋아하는 이유에 대해 설명하거나(이유: 어린애가 된 것 같아서 좋아함), 한병철 까거나 해도 이 사람이 좀 스트레..
2023.09.16
-
한병철 [피로사회]가 자폐인 비하한 건 알고 갤질하냐
아... 이쯤 되면 참담한 수준임 (참고로 51페이지랑 52페이지 사이에 대놓고 서번트증후군 비하한 내용 있음 서번트증후군 사람이 계산만 할 줄 알고 사유할 줄 모르는 이유는 ㅇㅈㄹ. 즉 저 자폐는 실제 질병 자폐를 말하는 게 맞음ㅋㅋ) 아니 푸코가 말하길 정신병은 사회가 규정하는 거기 때문에 다른 사회에서 다양성으로 인정받을 수 있는 것들이 우리 사회에서 정신병이 된다고 했거든요 근데 왜 푸코를 계승했다는 한병철은 지가 스스로 정신병을 비하하고 있음? 왜 자폐인들을 악으로 규정하고 지 ㅈ대로 만든 ㅈ같은 시스템에서 배제시켜 버리는 거임? 자폐에 대해 조금이라도 관심이 있었어도 현대사회 긍정성이랑 자폐는 1도 관계 없고 현대사회가 자폐화된다는 것도 ㅈㄴ 개소리인 걸 알 수 있을 텐데 [이상한 변호사 우영..
2023.09.15
-
나르시시즘에서 벗어나기
자기가 나르시시스틱한 인간이라고 생각해본 적 있나요 난 없는데요 상식적으로 2021시즌을 우울증, 자기비하로 개고생한 인간이 어떻게 나르시시스틱할 수가 있겠습니까 ???: 우울증은 나르시시즘적인 질병이다 그럼 제목이 왜 저러냐고요?? 이 글의 주제는 주제가 왜 나오지?? 사실 자기가 나르시시스트가 아님에도 불구하고 자기를 나르시시스트로 규정하면서 스스로 자존감을 깎아먹는 불쌍한 우리들에 대한 것입니다 현대인들은 자기를 사랑하는 방법을 잘 모르지 않습니까 항상 과열되어 있고 경쟁에서 뒤쳐지면 그것은 곧 죽음을 의미하는데, 사랑하기는 어렵고 우리는 상처받기를 무서워하는데, 윗세대는 출산율 떨어진다고 뭐라 하고 젊은이들이 사랑하는 법을 모른다고 꼰대질하고 그런 것임. 연애를 신격화하는 사람들을 경계하십시오! ..
2023.09.10
-
230105, [배추(背秋)]
그날도 여전히 눈은 눈부시게 오고 바람은 새파라지게 불고, 난 새해가 왔는데도 아직도 헌해를 묻지 못해서, 찌질해보이더라도 마음이 마음대로 안 되는 걸 뭐 어쩌겠어요. 그리고 내가 망가져있을때면 넌 말하곤 했지-그거 알아 불가능은 배추 셀 때나 쓰는 말이래, 그런 널 보고 내 맘은 다시 배춧잎처럼 구겨졌겠지만 넌 역시 그냥저냥하겠지. 난 언제나 너에게 내 모든 것을 비춰주는 투명망토 같은 인간이었으니까(그래, 해리포터의 속마음을 읽는 사람은 많아도 누가 투명망토의 속마음을 읽을 수 있겠냐고?), 하지만 뭐 어쩌겠어, 우린 그냥 다른 거야. 내가 생각하고 생각하는 동안 넌 아직도 그 토익 문제집을 풀고 있잖아, 배추 세는 듯한 소리를 내며 페이지를 넘기면서… 그렇담 너는 관짝에 묻힐 때까지 언제까지나 그렇..
2023.09.10
-
220901, [분할-정복]
그저 멍하니 바라보고만 있어야 한다 빈 화면을 아무것도 없는 곳을 응시하면서, 그저 언젠가 무언가가 손에 잡히기를 기다리며, 한가득 쌓인 문제상황들을 모두 체스터 속에 썰어넣어버리고 남은 것들도 다 냉장고에 소분해서 넣은 뒤 나는 행복합니다 행복합니다 외치면 행복해질까 사랑스런 것은 책상 맨 앞에 보기 싫은 것은 쓰레기통에 그거면 다인 걸까 그저 없다고 믿으면 지워지는-인생은 그런 것일까 날마다 회신할 수 없는 부류의 우편을 받는다 수능 성적표, 친구 소유의 6년 된 연애편지, 타지의 인생네컷에서 찍은 사진 내가 그것들을 보기 싫다면, 영영 못 보도록 치워 놓을 수 있을까 사랑스런 것은 책상 맨 앞에 보기 싫은 것은 쓰레기통에 사랑스러운 것과 혐오스러운 것 사랑스러운 사랑과 혐오스러운 혐오 사랑스러운 혐..
2023.09.09
-
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
-
카이스트 교환학생 1주차 일기
안녕하세요 저는 카이스트에서 공부를 하고 있는 컴공 학부생 invrtd.h입니다 오늘의 주제는 카이스트 교환학생의 힘듦에 대한 것인데요 원래 집 떠나면 다 힘듭니다 버클리 때도 그랬고 지금도 절실히 느끼고 있지만 지스트라는 장소는... 나한테는 안 맞는 부분이 많았을 수도 있지만 참 소중한 장소였어요 암튼 일기를 시작해보세 먼저 살펴볼 것은 제 시간표인데요 세상이 날 살해하려는 악의가 가득 담겨 있는 것 같아 사실 그정도는 아님 가장 중요한 것은 동시성 프로그래밍 수업인데요 왜냐하면 내가 노리는 랩실이 바로 이 교수님 랩실이기 때문입니다 어쩌다가 그렇게 됐는지 나중에 얘기를 하도록 하겠음 데베, 시프, 확통은 컴공이라면 이 정도는 할 줄 알아야 하는 것이네 이런 느낌으로 듣는 거고 최적화이론은 선대의 연..
2023.09.04
-
[백준 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
-
나는 무엇으로부터 도망치고 있나
8월 25일 일기 카이스트 교환학생을 가기로 결심하고 나서 주변 사람들한테 "나는 도망치는 거다"라고 얘기하고 다녔는데 대체 무엇으로부터 도망치고 있단 말인가. 사실 별 거 없음. 알고리즘 동아리 터지고 나서 수업을 참여해 봤는데, 음... 내가 무슨 폴란드 망명 정부의 지폐처럼 느껴지더라고. 쿠데타 실패한 프리코진의 기분으로 몇 달을 살았음. 그러니까 여러분은 노력해도 안 되는 것에 대해서는 꿈을 꾸지 말도록 하시오. 4월쯤인가 이미 카이스트로 가기로 결심함. 그리고 마침 카이스트에 내가 짝사랑하는 교수님이 한 분 계셨는데 본인은 좋아하는 사람에게 감정 표현을 잘 못하기 때문에(??) 열심히 랩실에 넣어달라는 편지를 준비해 보기로 결심했음. 그리고 열심히 CV를 적었지. 그리고 CV를 적으며 느낀 사실..
2023.08.25
-
[짧은 글] '왕의 DNA'와 우뇌의 신격화
내일 이산수학 시험인데 왜 또 이런 처참한 사건이 터지는지 모르겠다. 빨리 주절거리고 시험공부 하러 가야겠다. 사이비과학은 사람들을 설득시키기 위해 상식에 최대한 의존하려 한다. 이번 사건에서 가장 주목해야 할 단어는 '극우뇌'라고 생각한다. '왕의 DNA'라는 표현이 정말 임팩트가 있기는 하지만 잘 살펴보면 '극우뇌' 이론이 먼저 생겨났고 거기서부터 '왕의 DNA' 같은 표현이 따라나오는 것 같다. 대체 지금이 2023년인데 왜 아직도 사람들은 좌뇌-우뇌 이항대립을 신봉하면서 그걸로 또 굳이 이데올로기를 만들어 가지고 좌뇌를 폄하하고 우뇌를 신봉하는가? 모르겠다. 안아키도 2023년에 존재하는데 뭐... 아무튼 지금 좌뇌-우뇌 이항대립에 기생하는 이데올로기가 이 사달을 만들고 있으니 무엇이 이 이데올로..
2023.08.11
-
[백준 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
-
(뻘글) 시집 시 한줄해석 적어 봄
시는 30분 만에 휘갈기는 것이다 아무리 사랑시를 많이 쓴다고 해도 결국 실제 좋아하는 사람과 나 사이에서 벌어지는 문제를 해결할 수 없을 때, 그 무기력함에 대한 시다. 실제로 30분 만에 썼다. 여섯 개의 단어로 된 사전 지구멸망의 평범성에 대한 시다. 사람들은 일상 속의 오브제가 얼마나 위험한 것을 상징하는지 잘 모르더라. 설레는 사랑시 나르시시스트에 대해 썼다. 나르시시스트로부터 받은 상처를 극복하는 방법은 오히려 세상으로부터 상처를 받아서(...) 이 세상이 나르시시스트가 주장하는 자기 중심의 아름다운 세계관이 아님을 증명하는 것(...)이라는 뜻을 담고 있다. 재귀함수가 뭔가요? 인공지능으로 돈을 벌기 위해 인공지능의 능력을 과장하거나 축소하는 사람들의 자기모순에 대해 썼다. 사랑에 사랑을 더..
2023.07.18
-
[백준 13261] 탈옥 (분할 정복을 사용한 최적화) (Platinum I)
분할 정복을 사용한 최적화 입문 문제인 탈옥이다. 분할 정복을 사용한 최적화는 한 번 읽어서는 도무지 어떤 방식으로 코드를 짜야 할지 감이 오지 않는다(적어도 나에게는 그랬다). 나에게 있어서 이해를 방해하는 가장 큰 사실은 분할 정복과 DP가 도저히 어울리지 않는 것 같다는 사실이었다. 예컨대 피보나치 DP 문제를 살펴보자. 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> ... 이렇게 한 칸을 계산하는 일이 다음 칸의 계산에 영향을 미친다. 이 DP 문제를 억지로라도 분할 정복으로 계산할 수 있을까? 힘들어 보인다. 애초에 문제의 분할 자체를 어떻게 정의해야 할지도 모르겠다. 일단 탈옥 문제의 DP 식은 다음과 같다. i명의 간수를 사용해서 j번째 감옥까지 감시를 한다면, ..
2023.06.11
-
시집 [하늘에서 떨어지는 1, 2, ..., R-L+1개의 별]을 GitHub에서 즐기세요!
https://github.com/invrtd-h/1-2-...-R-L-1-Stars-Falling-from-the-Sky GitHub - invrtd-h/1-2-...-R-L-1-Stars-Falling-from-the-Sky: 시집 [하늘에서 떨어지는 1, 2, ..., R-L+1개의 별]의 PDF 시집 [하늘에서 떨어지는 1, 2, ..., R-L+1개의 별]의 PDF 파일. Contribute to invrtd-h/1-2-...-R-L-1-Stars-Falling-from-the-Sky development by creating an account on GitHub. github.com ㅈㄱㄴ
2023.05.22
-
230518, [예쁜 것들의 신]
김파랑 씨는 마법진 연구에 몰두했다. 김파랑 씨의 스승은 말했다. 명심해 진을 좆 같이 그려도 베이비 드래곤은 튀어나오지만 그건 우리가 원하는 답이 아니야. 마법진을 예쁘게 그려야 해. 잠깐 눈을 감았다 뜨면 육망성과 카디오이드와 정십칠각형 등이 머릿속을 헤집고 튀어버린다. 별빛을 봐도 네 생각이 나서, 김파랑 씨는 자신이 설레버렸음을 직감했다. 그래서 숨을 들이키면 한 번에 네가 스며들고, 한 번에 네가 습관이 되고, 한 번에 그렇게 녹슬어가는 것. 김파랑 씨는 마법진 연구에 몰두했다. 김파랑 씨는 수천 개의 삼각형과 사각형, 수백 개의 테서랙트의 평면 위로의 정사영 등을 그렸다. 허리가 굽고 손이 떨린다. 천재 마법사였던 김망고 씨의 저서 [추상마법진 입문]에는 다음과 같은 서술이 있다- 인간이 태생..
2023.05.22
-
시현하다를 찍었습니다
시현하십시오
2023.05.10
-
[백준 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
-
(화이트데이 기념) 정수 FFT 돌리기 좋은 소수 모음
정수 FFT 관련해서는 여기에 아주 잘 설명해 놓은 글이 있어서 소개합니다. https://algoshitpo.github.io/2020/05/20/fft-ntt/ 정확도 높은 FFT와 NTT FFT에서는 실수 자료형을 사용하기 때문에 실수 오차가 발생할 수 있고, 이는 즐거운 PS생활에 큰 지장을 줄 수 있습니다. 특히 FFT 문제에서 수가 너무 크기 때문에 M으로 나눈 나머지를 출력한다. algoshitpo.github.io 높은 정확도의 convolution이 필요할 때 보통 다항식을 2^15진법 위에서 쪼개거나 NTT를 돌리거나 하는데, 저 같은 경우는 IEEE 754를 제대로 숙지하지 못한 탓인지(?) 첫 번째 방법의 구현이 잘 되지 않아서 그냥 NTT를 하기로 했습니다. NTT를 할 때에는 다..
2023.03.14
-
[백준 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 ≤ n ≤ 70\,000$), 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
-
<여성이라는 난제 : 얄팍한 성기를 넘어선 범주를 상상하기>를 읽음
https://view.pong.pub/17 여성이라는 난제 : 얄팍한 성기를 넘어선 범주를 상상하기 지난 6월 3일에서 13일까지의 아주 짧은 기간, 김현주의 이라는 전시는 여성과 사회인으로서 느낀 곤란을 점묘 드로잉을 통해 그려내고 있었다. (작가의 말에 따르면 한 작업 당 6개월에서 2년까 view.pong.pub (내가 관심 있는 부분에 대해서만) 4줄 요약: 남녀를 불문하고 각 진영에서 신본질주의가 퍼지는 것은 현재 젠더 담론의 큰 문제다 페미니즘과 결합한 어떤 종류의 신본질주의는 여성의 문제를 여성기의 문제로 치환함으로써 자신의 잠재력을 스스로 제한한다 여성에 대해 논하기 위해서는 역설적으로 여성과 별 관련 없어 보이는 문제들(ex. 노동자)에 대해서도 논해야 한다 신본질주의라는 단어는 이 글..
2023.02.19
-
[백준 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 {\left( pi \bmod q \right)} \)의 값을 구하는 문제. 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, \ldots, 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
-
[짧은 글] '야가다사교클럽'은 도둑맞은 가난인가 (아님)
http://web.humoruniv.com/board/humor/read.html?table=pds&number=1179571 서울대 야가다사교클럽 출범.jpg 헉 web.humoruniv.com 야가다사교클럽은 짤에서 볼 수 있다시피 상하차 뛰고 비싼 걸 사먹는 클럽이다. 일단 난 팔로우를 했으니 이 클럽에 가입한 거긴 한데(?) 서울대생이 아니라서 활동을 할 리가 없다. 당연히 장난으로 팔로우한 거다. 짤에 글씨가 작은데 읽어보면 "가장 1차적인 노동인 야가다를 조지고 난 뒤, 서비스 산업의 최고점에 위치하고 있다고 할 수 있는 오마카세를 즐기는, 그 격차에서 나오는 카타르시스와 low-high (...가려짐) 인문학적 교양, 건강한 육체, 그리고 미식이라는 3가지 요소의 융합을 통해 우리는 다가오..
2023.02.04
-
충격!) 파이썬에서 오버로딩(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
-
100문 100답 (2023.01.30 ver.)
출처 : https://theqoo.net/square/1964578591 1. 이름? 송혜근 2. 한문은? 다 알고 있긴 하지만 이름 뜻에 연연하지 않는다 (내 시집 부록 참고) 3. 생년월일? 이거 쓰면 내 주민등록번호 13자리 중 6자리가 유출되는 기분이라 쓰기 싫음 4. 혈액형? O+ 5. 태어난곳? 경기도 수원 6. 주소? 니 마음속 7. 나의 장점은? 대가리가 잘 굴러감 8. 나의 단점은? 안티티티티 프래질 프래질하지 못함 9. 취미나 특기가 있어? 시를 씁니다 10. 하루 중 가장 행복할 때는? 11. 현재 가장 불만은 모야? 살면서 별의별 이상한 일을 다 겪다 보니 웬만한 작은 불만은 감지조차 못하는 사람이 되어버렸다 12. 기분이 안 좋을 때 하는 일? 뭐 유튜브나 봐야지 어쩌겠습니까. ..
2023.01.30
-
[백준 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
-
221015, [사랑에 사랑을 더하면 팔랑]
아직도 네가 날 노려다보며 내 심장에 주사를 들이대는 듯해. 거칠게 찔려도 더는 아파하지 않는 척하는 어른처럼 나는 순순히 내 피를 내어줄 듯해. 다리는 떨리고. 세상은 어지럽고. 따갑게 부드러운 향은 잔인하게도 내 감정을 흔들어대는. 아직도 너는 프리즘을 깨부술 때 튀어나올 마지막 빛깔같이 예쁘고, 네가 나에게 던지는 의미없는 낱말들의 연속에 내 피부는 파란색으로 물들어가는데. 여름이 오기 전까지는 숨기고 다닐 수 있는, 남들보다 빠르게 뛰는 심장으로 일상을 살 때면 때때로 칵테일 한 잔에 다 녹여내버리고 싶은. 그리고 하루의 마지막에, 완전한 어둠(또는 완전한 빛) 속에서 샤워할 때면 그제야 새어나오는 파란색 자국 말야. 벚꽃이 팔랑 하고 떨어질 때면 너는 벚꽃이 예쁘냐고 네가 예쁘냐고 물어봐. 내가..
2023.01.19
-
[백준 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 \leq 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
-
2022년에 내가 썼던 산문 연말결산
그래서 나는 그에게 동조해야 했다. 비록 K가 소시오패스라고 믿을 이유가 없긴 했지만, 내가 모르는 무엇인가가 있을 가능성이 높기 때문이다. 그런데 이것은 틀렸다. 나는 그가 처한 상황에 대해 모를수록 오히려 K는 소시오패스가 아니라고 주장해야 했다. 왜냐하면 내가 그 사람에 대해 하나도 모르는 상태에서 P(b->a) / P(~b->a)의 값은 당연히 1이고, 따라서 그녀가 소시오패스일 확률은 변동 없이 1:24, 즉 4%이기 때문이다. -[사랑과 이해와 베이즈주의] 2022.02.20. 야 '화가 나는'을 영어로 하면 뭔지 아냐? I'm an artist. -[복소함수학 줌 주소는 417 717 110] 2022.03.12. **이(내 친구)가 짝사랑하는 여자 두고 결혼하고 싶다고 말한 거 보고, 내가..
2023.01.08
-
고속 푸리에 변환, 이론부터 구현까지
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
-
(실험) ChatGPT는 고등학교 수학 문제를 풀 수 있을까? (ChatGPT 시리즈 1부)
ChatGPT는 인간에 맞먹는 작문 능력을 갖고 있다고 알려져 있지만 그 결과가 빅데이터에서 긁어오는 건지 ChatGPT가 자체 생성한 건지가 확실하지 않았다. 이걸 테스트해 보려면 새롭게 만든 문제들을 갖고 ChatGPT에 넣어봐야 할 것 같다는 생각이 들었다. 마침 내가 옛날에 수능 자작문제 만들기 활동을 많이 했기 때문에, 그 문제들을 넣어보자는 생각을 했다. 과연 결과는 어떨까? 1. 일단 대학생 수준의 선형대수학 문제를 넣어보았다. 번역 : n x n 행렬 A가 det(A^2 - A) 5번으로 넘어가는 부분에서 lambda^2 - lambda를 lambda로 멋대로 치환해버리면서 그 이후 풀이..
2022.12.20
-
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
-
GDSC GIST 2기에 떨어졌습니다!
몇몇 사실들을 되짚어봅시다. 나는 분명히 GDSC GIST 2기에 지원했고, 떨어졌습니다. 그 사실을 알고 나서 맨 처음 한 일은 내 인스타그램 계정에 이 사진을 올린 뒤, 그것을 프로필 상단에 고정하는 일이었습니다. 나는 이 행동은 대부분의 사람들이 하지 않는 비일상적인 행동이라는 것을 알고 있고, 그럼에도 불구하고 합리적인 행동이라는 사실을 알고 있습니다. 나도 부끄러움 같은 인간적 감정을 느낍니다만, 적지 않은 케이스에서 감정은 합리적 사고를 하는 데 방해가 되고 저는 이번의 사례 또한 그런 사례 중 하나라고 느꼈습니다. 요컨대 합리적 사고를 하려면 부끄러움을 뛰어넘을 필요가 있다는 것입니다. 하지만 설명이 약간 부족한 것 같습니다. 이 사실을 집어들고 나서 내가 무슨 생각을 했는지에 대해 여기에 ..
2022.10.13
-
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 \begin{pmatrix} A & A^2 \\ A^3 & A^4 \end{pmatrix} = 0 $$ 임을 보여라. (단, \( A \)의 모든 성분은 실수이다.) Sol) 주어진 행렬을 다음과 같이 다시 쓸 수 있다. $$ \begin{pmatrix} A & A^2 \\ A^3 & A^4 \end{pmatrix} = \begin{pmatrix} I \\ A^2 \end{pmatrix} \begin{pmatrix} A & A^2 \end{pmatrix} $$ 따라서 주어진 행렬은 \( 2n \times 2n \) 행렬이지만 그 rank가 \( n \) 이하이므로 행렬식이 \( 0 \)이다.
2022.09.14
-
[대학생 수학경시대회] 2016년 제1분야 4번/제2분야 5번
연속함수 \( f : \left[ -{\pi \over 4}, {\pi \over 4} \right] \rightarrow \left[ -1, 1 \right] \)가 구간 \( \left(-{\pi \over 4}, {\pi \over 4} \right) \)에서 미분가능할 때, 다음 부등식을 만족하는 점 \( x_0 \)가 구간 \( \left(-{\pi \over 4}, {\pi \over 4} \right) \)에 존재함을 보여라. $$ \left| f'(x_0) \right| \leq 1 + f(x_0)^2 $$ Sol) 먼저 함수는 단조증가함수 또는 단조감소함수가 아니라면 \( f'(x_0) = 0 \)을 만족하는 점이 적어도 하나는 존재하게 된다. 그리고 이 점에 대해 부등식이 자동으로 성립..
2022.09.14
-
[220911] 저주하는 인연들을 위해
있잖아, 난 카카오톡 차단 버튼이 왜 이렇게 불친절한 곳에 만들어졌는지 모르겠어, 친구 목록에서 그 사람을 일일이 찾아서 제거해야 한다는 게 너무 비효율적으로 느껴져, 왜 그 사람 프로필 바로 옆에 차단 버튼을 박아놓지 않는 거야? 그리고 차단 해제는 왜 그렇게 쉬운 일인지도 모르겠어, 무릇 차단이란, 그리움을 차단하고 순수함을 지키는 훌륭한 발명품 아냐? 근데 차단 해제가 이렇게 쉽다는 게 윤리적으로 말이나 되는 거냐고, 이게 다 카카오톡의 도덕적 해이 때문에 지금 온 세상에 전 남친들의 ‘자니?’가 넘쳐흐르고 있는 거잖아, 왜 차단 해제 버튼에는 지문 인식과 20자 이상의 비밀번호와 ‘로봇이 아닙니다’와 100자리 수의 소인수분해 문제 등이 적용되어 있지 않지? 떠나갈 사람은 뒤도 돌아보지 말고 떠나..
2022.09.11
-
[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
-
나를 지배하는 생각들
나는 2001년생이기 때문에 20xx년에 xx살이다. [2016~] 공리(Axiom)주의적 사고. 공리주의라는 말은 정치철학에서도 나오고 수학에서도 나오는데 내가 말하는 것은 후자다. "점은 넓이가 없는 위치이다" 같이 수학의 기초로 쓸 만한 것들을 공리로 정해 놓은 다음, 이들에 대해서는 별다른 의심을 하지 말자는 생각이다. 러프하게 표현하면, "수학은 진리가 아니며 공리들을 갖고 하는 일종의 게임이다"라는 생각이라고 할 수 있겠다. 사실 당시에는 공리주의적 사고 그 자체보다는 그 '게임'이 어떻게 진행되느냐에 더 영향을 많이 받았다. 다시 말해 명제 논리와 1차 술어 논리를 배웠다는 뜻. 나는 수학적 증명의 규칙을 꽤 일찍 배웠고, 그 결과 남들의 말에서 형식적 오류를 꽤 잘 찾는 사람이 되었다. 그..
2022.09.04
-
[대학생 수학경시대회] 2020년 제1/2분야 4번
4. 다음 극한값을 구하여라. $$ \lim_{n \rightarrow \infty} \int_0^{\pi \over 2} {{\cos^2 x} \over {1 + \cos^2 nx}} dx $$ Sol) 먼저, 대칭성에 의해 주어진 식이 $$ {{1} \over {2}} \lim_{n \rightarrow \infty} \int_0^{\pi} {{\cos^2 x} \over {1 + \cos^2 nx}} dx $$ 와 같음을 관찰한다. 복소수 \( x \)에 대해 $$ \cos^2 x = {1 \over 4} \left( e^{2ix} + e^{-2ix} + 2 \right) $$ 이므로, \( z = e^{2ix} \)로 치환하면 $$ {{1} \over {2}} \int_0^{\pi} {{\cos^..
2022.09.03
-
[대학생 수학경시대회] 2021년 제2분야 7번
7. 실수 \(a, b\)에 대하여 행렬 \(A\)를 다음과 같이 정의하자. $$ A = \begin{pmatrix} a & 1 & 1 & 1 \\ 1 & b & 1 & 1 \\ 1 & 1 & a & 1 \\ 1 & 1 & 1 & b \end{pmatrix} $$ 이때 행렬 \(A\)가 양의 정부호(positive definite)일 필요충분조건은 \(a > 1\)이고 \(b > 1\)임을 보여라. Sol) \( (\Leftarrow) \) 행렬 \(J\)를 모든 성분이 \(1\)인 \(4 \times 4\) 행렬이라 하고, 대각행렬 \( D \)를 \( D = A - J \)라 하자. 그러면 \( D \)는 모든 대각성분이 양수인 대각행렬이므로 자명히 양의 정부호이고, 행렬 \(J\)는 대각화하여 $$..
2022.09.02
-
이야~~ 상탐
https://gistnews.co.kr/?p=5893 시는 30분 만에 휘갈기는 것이다(제3회 광주과기원 문학상 – 시 가작) 시는 30분 만에 휘갈기는 것이다 송혜근(소재, 20) 말하자면 시는 세상을 뒤엎어야 한다는 것이다, 지금도 어딘가 한글을 한 조각 한 조각 깎아내어 유물 캐듯이 시를 쓰는 사람이 있겠지만 언 gistnews.co.kr (링크에는 시가 없습니다. 나중에 면디자인 나오고 지스트신문에 게재되면 바꿈) 제목이 인 이유는 진짜로 저 시를 2022년 4월 26일 새벽에 30분 만에 썼기 때문이다. 내가 보통 시를 쓸 때 2일 정도를 쓰는 것에 비추어 볼 때 이례적으로 짧은 시간이다. 그리고 30분 만에 쓴 시인 연유로, 시 곳곳에서 불친절한 설명과 급진적인 주제 변환이 난무한다. 그래서..
2022.09.01
-
[백준 25384] 니은숲 예술가 (Diamond V)
https://www.acmicpc.net/problem/25384 25384번: 니은숲 예술가 만들 수 있는 조형물의 가짓수를 $998\, 244\, 353$$(=119\times 2^{23}+1)$으로 나눈 나머지를 출력한다. $998\, 244\, 353$은 소수이다. 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 \)에 대해 $$ {\partial \over \partial x_{ij}} X = E_{ij}, {\partial \over \partial x_{ij}} A = O $$ 이다. 여기서 \( E_{ij} \)는 (i, j)-성분만 1이고 나머지 성분은 0인 행렬이고, \( O \)는 영행렬이다. 따라서 곱의 미분법에 의해 $$ O = {\partial \over \partial x_{ij}} I = {\partial \over \partial x_{ij}} XY = E_{ij} Y + X {\partial \over \partial x_{ij}} Y $$ 로부터 $$ {\partial \over \parti..
2022.08.29
-
[대학생 수학경시대회] 2014년 제1분야 8번
8. 양의 무리수 \( \alpha \)에 대하여 수열 \( \left\{ q_n \right\}_{n \geq 1} \)을 $$ q_n = {[n \alpha] \over n} $$ 로 정의하면 수열 \( \left\{ q_n \right\}_{n \geq 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