남남서의 블로그

도입 std::pair는 원소 두 개짜리 구조체예요. 2차원 평면 상의 점, 수직선 상의 구간, 선분의 양 끝점 등, 두 개로 묶는 자료 구조를 간편하게 사용할 수 있어요. 사용하기 아래와 같이 헤더 파일을 인클루드합니다. #include 사용 예시를 볼게요. #include #include using namespace std; int main() { pair p; p.first = 3; p.second = 4; cout

제가 PS를 할 때 사용하는 여러 코딩 팁을 소개하려고 합니다. 일반 0/1-based zero-based와 one-based 중 무엇을 써야 하는지에 대한 질문을 종종 봐요. 저는 one-based로 일단 가다가, 몇 가지 사정이 생기면 zero-based로 바꾸는 편이에요. circular array, 환형 배열. 크기가 n인 배열이 있는데, 마지막 원소 다음이 첫 번째 원소인 것처럼 원형으로 취급하고 싶다고 합시다. zero-based에서 i번째 원소의 다음 원소는 (i+1)%n, 이전 원소는 (i+n-1)%n입니다. one-based에서 i번째 원소의 다음 원소는 (i%n)+1, 이전 원소는 (i+n-2)%n+1입니다. zero-based가 훨씬 깔끔해요. 나눗셈 연산은 삼항 연산자(ternary..

도입 vector("벡터")는 간단하게 말하면 기능이 몇 개 추가된 배열입니다. 수학에서 말하는 벡터, "기하와 벡터" 할 때의 그 벡터를 떠올리는 분도 있겠지요. 관련이 완전히 없는 것은 아니지만 크게 중요하지는 않아요. 사용 방법 코드 첫 줄에 다음을 적습니다. #include 벡터는 배열과 비슷하게 변수처럼 선언합니다. 단 타입명을 꺽쇠로 감싸서 명시해 주어요. 아래 코드는 벡터를 쓰지 않은 코드입니다. #include using namespace std; int a[100]; int main() { cin >> a[0]; cin >> a[1]; cin >> a[12]; cout a[0]; cin >> a[1]; cin >> a[12]; cout

도입 C++는 Standard Template Library (STL)라는 라이브러리를 제공합니다. STL을 사용하면 복잡한 구현도 간결하게 할 수 있고, 시간복잡도나 실제 성능이 우수한 코드를 만들 수 있습니다. PS에서 STL은 더할 나위 없이 중요합니다. 조금만 난이도가 올라가면 STL 없이 구현하기 까다로운 문제가 왕왕 등장해요. STL을 사용하기 위해서는 적절한 헤더 파일의 #include가 필요합니다. 이 점이 Java, Python, Javascript 등의 언어와 달라요. 예를 들어 Java의 String, Python의 dict ({"a": 5}), Javascript의 array ([1, 2, 3]) 등은 import 없이 사용할 수 있지만, C++ STL의 std::string, st..

PS 분야의 사람들이 일상적으로 하는 말 중에 자연수 두 개가 요사이 부쩍 눈에 띕니다. 옛날의 제게 물어봤다면 1,000,000,007과 1,000,000,009를 들었겠지만, 아쉽게도 이들은 아닙니다. 998,244,353과 1,048,576도 아닙니다. 훨씬 작은 숫자입니다. 69와 420입니다. 네, PS 분야에 한정된 이야기가 아니라 훨씬 많은 사람들이 공유하는 인터넷 밈이 맞습니다. 그렇지만 콕 집어서 PS 분야를 언급하는 이유가 있습니다. PS 분야에 몸담은 사람이 많아지기는 했으나 커뮤니티에서 활발히 활동하는 사람은 소수입니다. 그리고 이들 사이에서 이게 즐거운 농담에 불과한 것으로 치부되어 간다고 느꼈습니다. 커뮤니티의 분위기는 영향력 강한 소수의 사람들이 좌우하며, 한 번 굳어지고 나면..

sparse table(스파스 테이블)이라고 불리는 기법이 있습니다. 이 기법에 대해 설명하는 글입니다. 예제를 통해 알아봅시다. 방향 그래프가 있습니다. 모든 점마다 나가는 화살표가 꼭 한 개씩 있습니다. 정점 하나에 말을 놓고, 이 말을 한 칸씩 움직일 거예요. 현재 있는 점에서 나가는 화살표가 한 개 있으니, 그걸 타고 새로운 점으로 갑니다. 새로운 점에서, 그 다음으로 갈 수 있는 곳도 하나밖에 없습니다. 나가는 화살표가 한 개니까요. 이렇게 나가는 화살표를 타고 계속 이동할 수 있습니다. 잘 생각해 보면, 무한히 여러 번 이동할 수 있습니다. 그렇다면 어떤 점 v에서 시작해, k번 전진했을 때 어디에 도착할까요? 이 질문에 빠르게 대답할 수 있을까요? 이런 그래프를 functional graph..