본문 바로가기

Computer Science74

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.
상속, 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.
[백준 1285] 동전 뒤집기 \( N \leq 20\)이므로 \(2^N\) 또는 그에 준하는 풀이를 생각해볼 만하다. 가로 \(N\)개의 줄, 세로 \(N\)개 줄 중 무엇을 뒤집을 것인지 생각하는 문제이므로 존재할 수 있는 선택의 개수는 \(2^{2N}\)이다. 그중에서 가로줄과 세로줄 중 하나가 몇 번 줄을 뒤집을지 그 상태가 이미 정해졌다면(편의상 세로줄이라 하겠다), 가로줄에 H가 더 많으면 가만히 놔두는 것을 선택하고 T가 더 많으면 뒤집는 것을 선택하는 그리디 알고리즘을 생각할 수 있다. 이것이 성립하는 이유는 세로줄이 이미 선택된 이상 모든 가로줄은 서로 영향을 주지 않는 독립이므로 순간의 최적 선택이 전체 최적 선택을 담보하기 때문이다. 한 번 그리디 알고리즘을 시행할 때마다 전체 셀 개수인 \(O(N^2)\)의 시간.. 2024. 1. 10.
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.
[백준 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.
[백준 2336] 굉장한 학생 (Platinum II) https://www.acmicpc.net/problem/2336 일단 등수대로 적혀 있던 것을 나름대로 잘 해석해서 함수 개개인에게 점수를 부여한다. 점수는 Student 구조체 하나를 만들어서, 거기다 저장할 수 있다. 이제 문제를 단순화해서 만약 시험 결과가 2개만 주어진다면 문제를 어떻게 풀지 생각해보자. 나라면 아마 다음과 같은 그림을 그려서 풀 것이다. 그림의 화살표가 나타내는 것은 알고리즘의 흐름이다. 우선 x좌표가 가장 큰 점에서부터 출발해, x좌표가 점점 작아지는 순으로 각 점들을 방문해 나간다. 이렇게 하기 위해서는 당연하지만 정렬이 필요하다. 이렇게 하면 x좌표에 대한 비교가 이미 끝났으므로 y좌표에 대한 비교만 하면 된다는 사실을 알 수 있다. 점 하나를 방문할 때마다 그 점이 이전.. 2023. 3. 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. 3. 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. 3. 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. 3. 2.
[백준 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. 2. 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. 2. 7.
Heap과 Priority Queue의 차이, 그리고 Abstract Data Type이란 무엇인가 얼마 전까지만 해도 나도 헷갈렸던 부분이다. 일단 배경지식이 어느 정도 필요하다. C++에서 스택(std::stack)은 어떻게 구현되어 있을까? std::vector 구현체처럼 그냥 공간을 뭉탱이로 할당해 놓고 공간 부족해지면 늘려서 할당하고 그런 식으로 구현되어 있지 않을까? 대부분의 자료 구조 강의에서도 stack을 그런 식으로 구현하니 말이다. 하지만 실제로는 이렇게 생겼다. 왜 이렇게 끔찍하게 생긴 방식으로 구현되었을까? 사실 이 구현은 양쪽에서 모두 원소를 뽑아 쓸 수 있는 큐인 deque(double-ended queue)에서 한쪽을 막아놓는다는 이상한(?) 방식이다. std::queue 구현도 마찬가지다. 대체 왜 그냥 자료 구조 교과서에 있는 스택을 안 만들고 굳이 deque를 만든 다음.. 2023. 2. 7.
[백준 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. 2. 6.

티스토리툴바