-
psb0623's profile image
psb0623
August 27, 2024
PS에서 C++ 상속 활용하기
C++에는 클래스가 있고, 클래스에는 상속이 있다는 사실은 대부분 알고 계실 것입니다. 상속의 개념을 Animal, Dog, Cat의 관계로 설명하는 것을 한 번쯤은 보셨을 것입니다. 하지만 실제 PS를 할 때 C++의 상속 개념을 활용하는 경우는 그닥 많지 않습니다. 그러나 상속을 잘 활용하면, PS에서도 더 편하고 깔끔하게 코드를 짤 수 있게 됩니다. 이 글에서는 PS에서 실용적으로 상속을 활용할 수 있는 몇 가지 사례를 소개합니다. 모든 원소에 특정 값 더하기 아래의 쿼리를 해결하는 문제를 생각해봅시다. 배열에 $x$ 추가하기 배열에서...
-
psb0623's profile image
psb0623
June 27, 2024
Run Enumerate로 문제를 풀어보자
이 포스트는 Run Enumerate의 구현 및 활용에 대해 다루며, koosaga님의 포스트를 기반으로 쓰여졌습니다. 이 글에서는 Run Enumerate를 문제 풀이에 활용하는 방법을 위주로 다루며, 증명이나 기타 자세한 내용에 대해서는 다루지 않으므로 다른 글을 참고하시길 부탁드립니다. Run Enumerate란? Run Enumerate는 문자열 내부에 연속하여 존재하는 모든 반복 또는 반복의 일부를 찾고 싶을 때 쓰는 알고리즘입니다. 예를 들어, $\rm{mississippi}$라는 문자열을 생각해봅시다. 이 문자열에는 어떤 반복이 존재할까요? 한번 나열해 봅시다. $[2, 4)$ 구간과 $[5,7)$ 구간에 해당하는 부분 문자열은 $\rm{ss}$로, 길이...
-
psb0623's profile image
psb0623
May 27, 2024
Suffix Automaton으로 Suffix Array 문제들을 풀어보자 2
이 포스트에서는 이전 글인 Suffix Automaton으로 Suffix Array 문제들을 풀어보자 1에 이어서, Suffix Automaton과 함께 사용할 수 있는 여러 테크닉들에 대해 설명합니다. Suffix Automaton이 무엇인지에 대해서는 제 이전 글을 참고하셔도 좋고, 아래 글을 읽어보셔도 좋습니다. https://koosaga.com/314 https://cp-algorithms.com/string/suffix-automaton.html DAG + Small to Large Suffix Automaton의 DAG에서 DP를 진행할 수도 있지만, 관리해야 하는 것이 어떤 값이 아닌 목록인 경우 Small to Large 테크닉을 활용할 수 있습니다. DAG에서 Small to Large를 활용하게 되는 대표적인 경우는, $n$개의 문자열 $S_1,...
-
psb0623's profile image
psb0623
April 25, 2024
Suffix Automaton으로 Suffix Array 문제들을 풀어보자 1
최근 공부 중에 Suffix Automaton이라는 자료 구조를 새로 알게 되어, Suffix Array 태그가 붙은 문제들을 전부 Suffix Automaton으로 풀어보려 시도했습니다. 그리고 꽤 많은 문제들이 Suffix Automaton을 사용할 때 훨씬 편리하게 풀린다는 것을 발견했습니다. 그 과정에서 알게 된 여러 테크닉들을 정리하고자 합니다. 이 글에서는 Suffix Automaton 자체에 대한 상세한 설명보다는 문제 풀이에 필요한 개념 위주로 간략하게 설명합니다. 아래에 Suffix Automaton에 대해 자세히 설명된 글이 있으니, 참고하시면 좋을 것 같습니다. https://koosaga.com/314 https://cp-algorithms.com/string/suffix-automaton.html Suffix Automaton이란? Suffix Automaton을 간단히...
-
psb0623's profile image
psb0623
August 22, 2021
람다 표현과 처치 인코딩(2)
이전 글에 이어서, 자연수와 그 연산들을 어떻게 함수로 인코딩하는지 알아보도록 하겠습니다. 자연수 인코딩(Church Numerals) 처치 인코딩에서는 다음과 같이 자연수를 정의합니다. \[0 = \lambda f. \lambda x. x\] \[1 = \lambda f. \lambda x. f \, x\] \[2 = \lambda f. \lambda x. f \, (f \, x)\] \[3 = \lambda f. \lambda x. f \, (f \, (f \, x))\] \[\vdots\] \[n = \lambda f. \lambda x. f^{n} \, x\] 간단히 말하자면, 처치 인코딩에서 자연수...
-
psb0623's profile image
psb0623
June 21, 2021
람다 표현과 처치 인코딩(1)
람다 표현(Lambda Expression)이란? 간단히 설명하자면, 람다 표현은 어떤 함수를 이름 없이 표현하는 방식이라 할 수 있습니다. 이런 특징으로 인해, 람다 표현은 종종 익명 함수(anonymous function)라고 불리기도 합니다. ‘이름 없이 표현한다’는 의미를 좀 더 와닿게 하기 위해, 한 가지 예시를 들어보도록 하겠습니다. 만약 $x$를 받아서 $x+1$을 내놓는 함수를 표현하고 싶다면 어떻게 해야 할까요? 보통의 경우, 아래와 같이 수학적인 표현법을 사용할 수 있습니다. $ f(x) = x + 1 $ 눈치채셨을지도 모르지만, 어느새 이 함수에는 $f$라는 이름이...
-
psb0623's profile image
psb0623
May 18, 2021
CORDIC(Volder's Algorithm)
자주 있는 일은 아니지만, 살면서 적어도 한 번쯤은 삼각함수를 사용하는 코드를 작성해야 할 일이 있을 것입니다. C++의 math.h 헤더나 Python의 math 모듈같이, 대부분의 언어에서 삼각함수를 비롯한 여러 기능을 지원하는 수학 라이브러리가 기본으로 제공됩니다. >>> from math import * >>> sin(1) # usage of sin function in Python 0.8414709848078965 그런데, 주어진 각도가 $ \pi/6 $, $\pi/4$, $\pi/3$과 같이 딱 떨어지는 특수각이 아닐 때에도 컴퓨터는 어떻게 삼각함수의 값을 구할 수 있는 걸까요? 위 예시에서 $\sin 1$의 값은...
-
psb0623's profile image
psb0623
March 21, 2021
Quine: 자기 자신의 소스코드를 출력하는 프로그램
우리가 주로 프로그래밍을 하는 목적은 문제를 효율적으로 풀거나, 특정 작업을 편리하게 처리하기 위해서일 것입니다. 그러나 어디서나 재미를 추구하는 것은 사람의 본능이기에, 오직 호기심과 흥미만을 목적으로 전혀 실용적이지 않은 코드를 짜는 경우도 꽤나 있습니다. 얼마나 창의적이게 이상한 C언어 코드를 작성했는지 겨루는 IOCCC라는 대회가 존재할 정도입니다. 이 글에서는, 쓸모는 없지만 신기한 프로그램의 대표적 예시인 ‘콰인(Quine)‘과 그 이론적 배경에 대해 알아보도록 하겠습니다. 콰인이란? 콰인(Quine) 은 실행했을 때 자기 자신의 소스 코드를 출력하는 프로그램을 이르는 말로, 미국의 철학자이자 논리학자인...