본문 바로가기

분류 전체보기91

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. 7. 6.
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. 3. 31.
Mac에서 Launchpad가 하단 바에서 디폴트로 안 보일 때 해결법 Launchpad도 응용 프로그램이다. 따라서 해결법은 아무 응용 프로그램을 하단 바에서 디폴트로 나타나게 하는 법과 같다. Finder에서 [응용 프로그램] 탭 들어가서 Launchpad를 찾은 뒤 하단 바로 드래그하면 된다. 2024. 3. 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. 3. 4.
확실히 등단하고 나서 내 인생이 달라졌다 원래는 대학교때 짝사랑하는? 교수님 눈도 못 마주치고 쓰레기 아무데나 버리고 조던피터슨한테 침 찍찍 뱉고 했는데 시와편견 신인문학상 등단패 오너가 되고나니깐 품위유지하려고 스스로 노력할려고한다. 방금도 내가 3달 전에 썼던 에리히프롬 까는 초고 버려져있길래 주워서 쓰레기통에 버리고왔다. 학생때는 한병철이든 자청이든 맘에 안 들면 다 깠는데 이제는 동아리원들(특징: 철학서 나보다 많이읽음) 눈도 못 마주친다. 아무리 말하고 싶은 얘기가 있어도 샤워하면서 혼자 나는 누구? "시와편견 신인문학상 등단패 오너" 하니까 겁나 부담스럽네 이래서 자리가 사람을 만든다는말이 나온것같다. 2024. 3. 2.
철학은 자기 공격성을 포장하기 위한 수단이 아니에요 그냥 내 시처럼 자기가 공격성 있다는 걸 쿨하게 인정하든가 아니면 그냥 처음부터 뺨 때린 사람에게 다른 쪽 뺨도 내줄 기세로 사고하든가 자기 도덕성이 점점 진보하고 있다고 믿는 사람과 대화하는 것만큼 고통스러운 일이 없어요 2024. 2. 1.
상속, 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. 1. 30.
무슨 컴공 글을 써야 사람들이 원하는 글을 쓸 수 있을까 자료구조론, 알고리즘 아니면 파이썬 고급 feature들 아니면 C++만의 고유 디자인 패턴 사실 잘 모르겠음 (주제 추천 받아요) 2024. 1. 28.
[백준 1285] 동전 뒤집기 \( N \leq 20\)이므로 \(2^N\) 또는 그에 준하는 풀이를 생각해볼 만하다. 가로 \(N\)개의 줄, 세로 \(N\)개 줄 중 무엇을 뒤집을 것인지 생각하는 문제이므로 존재할 수 있는 선택의 개수는 \(2^{2N}\)이다. 그중에서 가로줄과 세로줄 중 하나가 몇 번 줄을 뒤집을지 그 상태가 이미 정해졌다면(편의상 세로줄이라 하겠다), 가로줄에 H가 더 많으면 가만히 놔두는 것을 선택하고 T가 더 많으면 뒤집는 것을 선택하는 그리디 알고리즘을 생각할 수 있다. 이것이 성립하는 이유는 세로줄이 이미 선택된 이상 모든 가로줄은 서로 영향을 주지 않는 독립이므로 순간의 최적 선택이 전체 최적 선택을 담보하기 때문이다. 한 번 그리디 알고리즘을 시행할 때마다 전체 셀 개수인 \(O(N^2)\)의 시간.. 2024. 1. 10.
글쟁이를 위한 해시태그 이게 뭐시여~ 원래 여기는 inverted.h가 주인장인 코딩/개발 블로그인데 이번만큼은 박예담 빙의해서 작성함 1. 글을 쓰게 된 계기 인간에 대해 이해하고 싶어서일 거임 아마 2. 하루에 쓰는 분량 시 쓰는 사람은 하루에 그렇게 많이 쓰지 못해가주구 요즘은 2주에 한 편꼴로 쓰고 있는 것 같습니다 이것보다 더 많이 쓸 수 있긴 한데, 시인의 딜레마라는 게 쌓인 일이 많다 -> (+) 얻을 수 있는 글감이 많다 (-) 시 쓰기 전에 그 일을 해야 한다 쌓인 일이 적다 -> (+) 시 쓸 시간이 많다 (-) 얻을 수 있는 글감이 적다 이 굴레에서 벗어날 수가 없음 3. 슬럼프 극복하는 방법 극복을 안 했음 4. 작업곡 / 노동요 시 쓸 때만큼은 노래 안 듣습니다 단어 하나하나에 초집중해야 해서 집중한 꼬.. 2024. 1. 6.
2023 제2회 미적확통컵 출제 후기 귀찮으니까 빨리 적어야지 미적확통컵 특) 플래 겁나많음 1회 미확컵보다 솔브드 기여 난이도는 낮게 잡힐 것 같은데 1회 때 웰노운이 많았던 것과 달리 2회 때는 그런 게 없어서 사람들이 좀 고전하는 것 같았다 60분 이내에 솔브가 나지 않은 문제가 1회 3개 -> 2회 5개로 늘었고 푼 사람이 1자리 수인 문제가 1회 3개 -> 2회 6개(...)로 늘었다 CD 결혼식이 끝나고 PE 최고의 크리스마스트리 두 문제를 출제했다 결혼식이 끝나고 퍼솔 84분, 푼 사람 8명 내가 미적확통컵에 맨 마지막으로 들어간 출제진이다. 정확히 말하면 추가합격인데 8월쯤에 출제진 한 분이 빠지셔서 추가모집 때 내가 들어갔어요 이것도 사실 겨우겨우 들어갔음 하루님이 메일을 보내셨는데 스팸메일함으로 쏙 들어가버린겁니다 그래서 .. 2023. 12. 24.
흑흑흑 보호되어 있는 글 입니다. 2023. 12. 15.
흑흑 보호되어 있는 글 입니다. 2023. 12. 13.
흑 보호되어 있는 글 입니다. 2023. 12. 12.
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. 8.
[C++] 객체지향, 제네릭 세그먼트 트리 라이브러리 구현하기 이 글에서는 재사용 가능한 제네릭 세그먼트 트리 라이브러리를 구축하는 방법에 대해 알아본다. 세그먼트 트리를 사용할 어떤 상황이 나와도 최대한 복붙만으로 문제를 해결할 수 있게 하는 것을 목표로 한다. 세그먼트 트리의 작동 원리 자체에 대해 설명하는 글은 아니기 때문에 독자가 세그먼트 트리에 대해 어느 정도 이해하고 있다고 가정한다. Motivation 세그먼트 트리는 point update & range query를 O(log N)에 처리할 때 유용하게 사용 가능한 자료구조다. 여기서 range query는 다음과 같은 것들이 주어질 수 있다: 구간 a[l..r]의 합/곱/xor을 구하기 구간 a[l..r]의 최솟값/최댓값을 구하기 구간 a[l..r]의 최대 부분연속합을 구하기 (속칭 금광세그) 구간 .. 2023. 10. 3.
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. 9. 8.
[백준 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. 8. 27.
[백준 28399] 황혼 (UCPC 2023 본선; Platinum IV) 원본 그래프 G의 복사본을 만들어 각각 G1, G2라고 이름붙여줄 수 있다. 만약 주어진 사람이 단순 경로를 처음부터 따라 이동하는 중이라면 그 사람을 G2 위로 보내고, 아니라면 G1 위로 보내자. 그러면 이것은 그냥 그래프이므로, 다익스트라를 돌리면 한 점 위에서 나머지 2n개의 정점으로 향하는 최단 경로의 길이를 구할 수 있다. 다 구한 다음에는 그래프를 다시 하나로 합쳐 주고, 정점에 부여된 가중치는 두 정점의 최솟값으로 잡으면 된다. 이 문제는 체감상 다익스트라를 돌리는 과정보다 구현이 더 까다로웠다. 예를 들면, 내가 지금 주어진 단순 경로 위에 있는지, 있다면 주어진 단순 경로의 다음 정점은 몇 번인지를 어떻게 O(1)에 구하는가? 이 문제를 해결하기 위해 vector를 2개 만든다. 첫 번.. 2023. 8. 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. 7. 29.
[짧은 글] 용필남 사태가 알려주는 것들 판사님 저는 용필남이 무엇의 줄임말인지 얘기 안 했습니다. 1. 극단주의 유튜버들의 구독자는 생각보다 유튜버에게 충성하지 않을 수 있다 이것은 '용'의 유튜브 구독자 수가 날아가고 있는 것으로 설명이 된다. 내가 한 4년 전쯤인가 자기계발 유튜버들을 계속 보면서 느꼈던 게 하나 있는데(그때는 내가 고3이었고, 유튜브 자기계발 유튜브의 현실을 잘 몰라서 가능한 일이었음) 유튜버들이 설명하는 내용들 중에서 내가 틀렸다고 생각하는 게 하나 있다고 하더라도 바로 구독을 취소하지는 않는다. 무언가 잘못 설명하는 내용들이 계속 쌓이고 쌓여서 뭔가 잘못됐다는 생각이 들었을 때쯤에야 탈출을 감행한다. 그러는 이유는 아마도 내가 구독해서 얻는 이익이 잘못된 정보를 받음으로써 얻는 손해보다 더 크다고 생각했기 때문일 것이.. 2023. 7. 23.
[백준 13261] 탈옥 (분할 정복을 사용한 최적화) (Platinum I) 분할 정복을 사용한 최적화 입문 문제인 탈옥이다. 분할 정복을 사용한 최적화는 한 번 읽어서는 도무지 어떤 방식으로 코드를 짜야 할지 감이 오지 않는다(적어도 나에게는 그랬다). 나에게 있어서 이해를 방해하는 가장 큰 사실은 분할 정복과 DP가 도저히 어울리지 않는 것 같다는 사실이었다. 예컨대 피보나치 DP 문제를 살펴보자. 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> ... 이렇게 한 칸을 계산하는 일이 다음 칸의 계산에 영향을 미친다. 이 DP 문제를 억지로라도 분할 정복으로 계산할 수 있을까? 힘들어 보인다. 애초에 문제의 분할 자체를 어떻게 정의해야 할지도 모르겠다. 일단 탈옥 문제의 DP 식은 다음과 같다. i명의 간수를 사용해서 j번째 감옥까지 감시를 한다면, .. 2023. 6. 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. 5. 1.
[백준 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. 4. 30.
[백준 12963] 달리기 (Platinum III) https://www.acmicpc.net/problem/12963 최대 유량의 정의를 알고 있다면, 이 문제는 최대 유량을 구하는 문제의 특수한 버전이라는 것을 쉽게 알 수 있다. 그런데 최대 유량 최소 컷 정리에 의해 최대 유량의 값은 최소 컷의 값과 같다. 간선의 value가 3^i 꼴로 주어지기 때문에, 최소 컷의 값을 그리디 알고리즘으로 구하기가 상당히 쉽다. 최소 컷을 구하는 것은 가장 적은 비용의 간선을 자르는 것이므로, 가장 많은 비용의 간선을 살린다고 생각할 수도 있다. 그렇다면 가장 먼저 살려야 할 간선은 가장 value가 큰 간선임이 명백하다. 이는 value가 3^i 꼴로 주어지기 때문에 성립하는 것이고, 일반적인 상황에서는 성립하지 않는다. 이 사실을 증명하는 것은 쉽다. 최종 결.. 2023. 4. 27.
제1회 와쿠컵 출제 후기 어쩌다가 제1회 와쿠컵으로 출제 데뷔전을 치르게 되었습니다. 그런데 제1회 와쿠컵에 거의 600명이나 되는 사람들이 몰리면서 지금 상당히 부담스러워 하고 있습니다. 이번 와쿠컵에서 K. I LOVE JavaScript O. 지연 평가 이렇게 두 문제를 출제하게 되었습니다. 사실 5문제 정도를 만들었는데 가장 난이도가 낮고 퀄리티가 높다고 생각한 두 문제를 뽑았습니다. O. 지연 평가 이 문제를 첫 번째로 만들었습니다. 아마 5문제 중에 3번째로 만든 문제였던 것 같은데 둘 다 골드 넘어갈 것 같아서 그냥 혼자서 버리기로 결정했습니다. 그렇게 해서 만든 문제가 이 문제였는데 사실 이 문제도 골드를 갈 뻔했습니다. 버전이 총 3개가 있었는데 세상에 나온 버전은 그중에 가장 쉬운 버전이었습니다. 처음에 출제진.. 2023. 4. 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. 4. 17.
Codeforces 블루 후기 후기...? 가 있어야 되는데 잘 모르겠어요... 전 그냥 문제가 주어지면 풀었을 뿐임... 그리고 Div.2보다 Div.3, Div.4를 많이 참가했으니 저 같이 얍삽한 방법으로 블루 찍지 마세요 2023. 4. 6.

티스토리툴바