-
djm03178's profile image
djm03178
January 16, 2022
Python 3의 String 라이브러리 둘러보기
개요 이전에 Python 3에서 문자열 내의 부분 문자열을 빠르게 찾기 위한 fastsearch 기법에 대한 글을 쓴 적이 있습니다. 그 글에서는 문자열 중에서도 특정 기능에 대한 심도 있는 분석을 해보았었는데, Python의 철학이 담긴 대단히 세밀한 디자인과 구현체를 볼 수 있었습니다. 하지만 그것만으로는 Python의 str이 가진 수많은 특징 중 극히 일부 단면만을 보인 듯한 느낌이 들었습니다. 그래서, 이번에는 좀더 str의 전체적인 모습을 두루 살펴볼 수 있도록 보다 큰 그림을 통해 Python 3의 str의 구조는 어떻게 되며, string...
-
djm03178's profile image
djm03178
December 18, 2021
프로그래밍 대회 출제 체크리스트
개요 PS가 보다 대중에게 친숙해지면서 여러 종류의 프로그래밍 대회도 점점 많아지고 있습니다. 특히 기관이나 기업이 아닌 일반인이 주최하는 대회가 부쩍 늘었는데, 대표적인 것이 대학교 대회라고 할 수 있습니다. 모두에게 친숙한 백준 온라인 저지에서도 BOJ Stack을 통해 손쉽게 대회를 준비할 수 있는 플랫폼을 만들어 어느 정도 PS에 경험이 있다면 누구나 쉽게 대회 개최에 참여할 수 있게 되었습니다. 반면에 아마추어가 쉽게 대회를 열 수 있다는 점은 반대로 준비가 덜 된, 낮은 퀄리티의 문제가 쉽게 양산될 수도 있다는...
-
djm03178's profile image
djm03178
November 21, 2021
컴퓨터 과학의 미해결 문제들
개요 수학에는 많은 난제들이 있습니다. 전세계적으로 유명한 밀레니엄 문제가 대표적입니다. 인지도 있고 학술적 가치가 높은 난제는 하나를 해결하는 것이 평생의 업적이 되기도 합니다. 많은 난제들이 꾸준히 풀리고 있지만, 새로운 문제가 창조되는 것에도 역시 끝이 없습니다. 난제의 범위를 컴퓨터 과학으로 좁혀봅시다. 대표적인 것으로는 밀레니엄 문제의 일부이기도 한 P-NP 문제가 있습니다. P-NP 문제는 너무나 유명해서 이 글을 읽을 사람이라면 누구나 한 번쯤은 들어보았을 것입니다. 하지만 그 외에 다른 컴퓨터 과학 난제는 그다지 널리 알려진 것이 없는 것...
-
djm03178's profile image
djm03178
October 22, 2021
다른 사람의 코드의 문제점 찾아주기
개요 저는 백준 온라인 저지의 질문 게시판에서 풀라는 문제는 안 풀고 오랜 기간 많은 답변을 해왔습니다. 그러면서 느꼈던 것 중 하나는 문제 풀이 실력과는 별도로 처음 보는 코드를 분석하는 실력이 많이 늘었다는 점입니다. 예전에는 타인의 코드를 읽는 것이 마냥 어렵기만 했다면, 지금은 그 코드가 제 코딩 스타일과 크게 다르더라도 작성자의 의도를 파악하며 보다 객관적으로 코드를 읽는 능력이 향상되어 더 빠르게 답변을 해줄 수 있게 되었습니다. 부분적으로는 제 코드를 돌아보고 디버깅을 하는 데에도 도움이 됐다고 생각합니다....
-
djm03178's profile image
djm03178
September 18, 2021
printf 구현체의 분석
개요 C언어를 처음 배울 때, 가장 처음으로 구현하게 되는 Hello World 코드에 반드시 들어가는 함수가 있습니다. 바로 printf 함수입니다. 처음부터 배울 정도로 기초적인 함수이지만, 다양한 형식의 출력을 담당한다는 점에서 일반적인 프로그램들에서도 필수적으로 사용되는 중요한 함수라고 할 수 있습니다. 게다가 이 함수의 사용법을 정확히 숙지하는 것은 매우 어렵습니다. 출력의 목적지와 문자열의 종류 등에 따라 printf, sprintf, vprintf, wprintf 등의 다양한 변형이 있을 뿐 아니라, ‘%’ 문자를 통해 제공되는 출력 서식 또한 매우 다양한 종류와 구체적인 명세가...
-
djm03178's profile image
djm03178
August 18, 2021
Python 3의 문자열 fastsearch 기법들
개요 Python 3는 내장된 수많은 기능을 통해 사용자에게 편의성을 제공합니다. 여기에는 문자열 자료형인 str과 관련 라이브러리들이 포함되는데, 대부분의 기능이 언어 자체에 내장되어 일반 리스트처럼 대괄호를 사용한 인덱스 접근도 가능하고, ‘문자’와 ‘문자열’의 구분도 없으며, 널 문자같은 귀찮은 요소도 신경쓰지 않아도 되고 마음대로 인덱스를 지정해 잘라내거나(slicing) + 연산자로 이어붙이고 심지어는 * 연산자로 반복까지 할 수 있는 등 만능의 성격을 갖추고 있습니다. 이처럼 높은 접근성을 고려한 구현은 CPython의 문자열 구현체에서도 드러나는데, 문자열 내에서 문자열을 검색하기 위한 find 기능이...
-
djm03178's profile image
djm03178
July 9, 2021
재귀 함수에 대한 이해
개요 재귀 함수는 알고리즘 문제 풀이뿐만 아니라 프로그래밍 전반에 있어 매우 중요한 기법 중 하나입니다. 여러 복잡해 보이는 문제들을 재귀 함수 하나면 손쉽게 구현할 수 있는 경우가 많기 때문에 매우 ‘강력하다’는 표현을 자주 쓰게 됩니다. 문제 풀이에서는 DFS를 구현하는 가장 기본적인 방법으로 널리 사용되기 때문에 최근에 핫한 코딩 테스트들에서도 사용 빈도가 매우 높습니다. 그러나 재귀 함수는 알고리즘 초보가 쉽게 벽을 느끼게 될 수 있는 기법이기도 합니다. 순차적으로 그냥 실행 흐름을 따라가면 되는 다른 코드들과는 달리,...
-
djm03178's profile image
djm03178
June 20, 2021
대회/코딩 테스트용 간이 테스터 만들기
개요 프로그래밍 문제를 풀다 보면 종종 맞왜틀 (맞았는데 왜 틀려요)의 벽에 부딪히게 됩니다. 예제도 다 맞고, 열심히 생각해서 넣어본 여러 케이스들도 맞는데도 제출만 하면 틀렸다고 하고… 도무지 반례가 안 보일 때의 답답함은 말로 표현할 수가 없습니다. 연습용으로 문제를 풀 때에는 그나마 Polygon과 같은 전문 도구를 사용해서 스트레스를 돌리거나 견고하게 짜여진 테스트용 도구를 로컬에서 실행해보면서 반례를 찾을 수도 있습니다. Polygon의 사용법은 Acka1357 님의 글 문제 출제를 위한 플랫폼 - Polygon 사용하기에서 자세하게 확인할 수 있습니다. 하지만...
-
djm03178's profile image
djm03178
May 14, 2021
testlib 사용하기
개요 testlib는 Polygon에서 프로그래밍 문제를 만들기 위한 유틸리티를 한데 모아놓은 라이브러리입니다. Generator, validator, checker 및 interactor 제작에 공통적으로 사용되며, 신뢰도 높은 랜덤 함수, 안정성 있으며 정규표현식을 지원하는 문자열 파싱, Polygon 및 채점 시스템과의 상호작용 등의 다양한 기능을 갖추고 있으며 Polygon과 GitHub 페이지에서 다양한 사용 예제들도 제공해 줍니다. 문제 출제를 위한 플랫폼 - Polygon 사용하기 글에 간단한 사용 예시가 나와있습니다. 유용한 기능을 많이 갖추고 있고 코드의 주석 또한 훌륭한 반면에 testlib에 대한 별도의 문서화는 이루어지지 않았습니다....
-
djm03178's profile image
djm03178
April 10, 2021
Generator 문제 풀이 / 후기 (스포일러 주의)
개요 Generator 문제는 수많은 PS 문제들 중에서도 오로지 ‘구현’만으로 악랄한 난이도를 성립시킨 것으로 유명합니다. solved.ac 기준 Diamond III라는 상당한 고난도의 평가를 받고 있지만 이 문제를 풀기 위한 사전 지식이나 개별 테크닉은 높아야 Platinum 중상위권으로 생각하며, 문제의 난이도는 대부분 구현, 관찰, 그리고 요구하는 끈기와 인내심에 의해 결정된다는 점에서 다른 구현 위주의 고난도 문제들과는 차별이 되는 문제입니다.1 최근 문제 풀이를 연습할 시간이 부족했던 저에게 갑자기 이 문제를 당일치기로 풀어내는 것은 상당히 어려운 일이었고, 비록 주말이긴 했으나 거의...
-
djm03178's profile image
djm03178
March 20, 2021
흥미로운 데이터 추가 모음
개요 2017년 여름 본격적으로 BOJ에서 문제 풀이를 시작한 이래로 저는 많은 문제들에 데이터 추가 요청을 해왔습니다. 조금 사악한 취미일지도 모르겠으나, 문제를 풀어서 ‘맞았습니다!!’를 받는 것 이상으로 즐거웠던 것이 추가한 데이터에 의해 많은 ‘맞았습니다!!’를 받았던 코드들이 ‘틀렸습니다’ 내지는 ‘시간 초과’, 또는 ‘런타임 에러’ 등으로 바뀌는 것을 지켜보는 것이었습니다. 문제를 더 견고하게 만들었다는 뿌듯함과, 많은 분들이 놓쳤을 법한 포인트를 찾아 특이한 형태의 데이터를 제작하는 과정이 즐거웠습니다. 추가한 데이터들 중에는 단순히 기존의 데이터가 빈약해서 그다지 특이할 것 없는...
-
djm03178's profile image
djm03178
February 19, 2021
'틀렸습니다'를 받지 않기 위한 팁
개요 이전 글들에서 시간 복잡도를 고려한 코드 설계 전략과 PS에서의 런타임 에러와 디버깅에 대해 각각 다루어 보았습니다. ‘시간 초과’와 ‘런타임 에러’는 모두 오답 판정 중 특수한 경우에 해당하기 때문에 코드의 어떤 부분에 초점을 맞추어 디버깅을 해야 할지가 비교적 명확하고, 문제가 될 수 있는 유형도 어느 정도는 제한적이고 빈번히 발생하는 패턴들이 존재합니다. 특히 ‘런타임 에러’의 경우에는 백준 온라인 저지에서 얼마 전부터 런타임 에러의 종류를 공개하기 시작해서, 문제의 원인을 파악하기가 이전보다 훨씬 용이해졌습니다. 오답 판정 중 가장...
-
djm03178's profile image
djm03178
January 22, 2021
시간 복잡도를 고려한 코드 설계 전략
개요 알고리즘 문제에는 여러 가지 제한이 주어집니다. 여기에는 입력으로 주어지는 값의 범위, 그 값들이 가지는 성질 등의 조건도 있지만, 대부분의 경우 메모리 제한과 시간 제한이 같이 주어집니다. 많은 문제들에서는 이 제한을 크게 고려하지 않고도 답을 찾아내는 로직만을 생각하여 코드로 구현하면 통과할 수 있지만, 일부 문제에서는 시간 제한 때문에 직관적인 해결책으로는 통과할 수 없는 경우도 존재합니다. 따라서 알고리즘 문제를 풀 때에는 코드를 작성하기 전후로 로직과 코드의 시간 복잡도를 계산하는 것이 중요합니다. 시간 복잡도는 알고리즘을 공부할 때...
-
djm03178's profile image
djm03178
December 15, 2020
Codeforces Round #688 개최 후기
개요 Codeforces Round #688 (Div. 2) Announcement Editorial (이전 글) Codeforces Round #620 개최 후기 (이전 글) Codeforces Round #578 개최 후기 올해 초 Codforces에서 개최했던 620번 라운드는 제게는 잊을 수 없는 기분 좋은 추억입니다. 처음으로 단독 출제자를 해본 대회에 무려 14612명이 등록해서 좋은 반응을 이끌어냈었다는 것이 정말 좋았습니다. 그 기분을 다시 느끼고 싶어서 라운드가 종료되고 얼마 지나지 않아 바로 다음 라운드를 준비하기 시작했고,1 12월 4일 22시 05분(KST)부터 2시간 15분에 걸쳐 Codeforces Round #688 (Div....
-
djm03178's profile image
djm03178
November 20, 2020
Codeforces 레이팅의 경향 분석
서론 이전 글에서 Codeforces의 레이팅 계산법에 대해 다루어 보았습니다. 이번 글에서는 기존 라운드들에서의 통계를 이용하여 이 레이팅 체계가 어떤 경향을 보이고 있는지 살펴보고, 여기서 발견되는 구조적인 문제점의 원인을 분석해 보려고 합니다. 어떤 레이팅 시스템이 이상적이라면 각 참가자가 해당 라운드에서 기록한 ‘성적’에 따라 레이팅의 변화가 이루어져야 할 것인데, 많은 사람들의 경험에 의하면 특정 종류의 라운드에 참가하는 것이 다른 종류의 라운드에 참가하는 것에 비해 레이팅을 얻기가 훨씬 쉽다고 합니다. 이 현상이 어느 정도 심각한지를 집중적으로 조사해 보았습니다....
-
djm03178's profile image
djm03178
October 24, 2020
동적 계획법 모델화하기
서론 세상에는 수없이 많은 알고리즘 문제가 있습니다. 그러나 새로운 문제를 볼 때마다 항상 지금껏 보지 못한 새로운 기법을 사용해야 하는 것은 아닙니다. 문제의 특성을 파악하고, 조건들을 이용하여 자신이 아는 문제로 변환한 뒤, 이전에 다른 문제를 풀 때 사용했던 기법을 비슷하게 적용하여 풀 수 있기도 합니다. 이처럼 많은 문제는 몇 가지 정해진 전형적인 형태로 모델화 되는 경우가 많습니다. 반면에 큰 알고리즘 분류 중에 많은 사람들이 처음 접할 때 큰 벽을 느끼는 분야가 있습니다. 바로 동적 계획법(dynamic...
-
djm03178's profile image
djm03178
September 19, 2020
PS에서의 런타임 에러와 디버깅
서론 알고리즘 문제를 온라인 저지에서 풀다 보면 다양한 종류의 채점 결과 (verdict)를 받게 됩니다. 백준 온라인 저지의 경우 통상적으로 볼 수 있는 채점 결과만 ‘맞았습니다!!’, ‘틀렸습니다’, ‘시간 초과’, ‘메모리 초과’, ‘컴파일 에러’, ‘런타임 에러’, ‘출력 초과’, ‘출력 형식이 잘못되었습니다’ 등 8가지나 됩니다.1 그런데 애석하게도 이 중에 좋은 결과는 오로지 ‘맞았습니다!!’ 하나뿐이고, 나머지는 모두 안 좋은 결과입니다. 이 안 좋은 결과들의 의미는 대부분 명확합니다. ‘틀렸습니다’는 말 그대로 출력 내용이 정답이 아니었던 것이고, ‘시간 초과’는 말 그대로...
-
djm03178's profile image
djm03178
August 16, 2020
임의의 원소를 수정할 수 있는 우선순위 큐
서론 힙 (Heap)은 그 간단한 구조와 시간 / 공간 측면에서의 여러 장점들 때문에 문제 풀이뿐만 아니라 실무에서도 우선순위 큐로서 널리 애용되는 자료구조입니다. C++의 std::priority_queue, Java의 java.util.PriorityQueue, Python의 heapq1 등 고수준 언어의 자료구조 라이브러리에서 웬만하면 지원을 해주기도 합니다. 우선순위 큐를 라이브러리로만 접하면 기능이 매우 적은 것에 대해 실망할 수도 있습니다. 대체로 원소를 삽입하는 기능과, 최대 혹은 최솟값을 확인하고 제거하는 연산이 전부이기 때문입니다. 그런데 사실 힙에는 그 외에도 많은 가능성들이 숨어있습니다. 단순한 형태의 구현체에서는 수행하기 어려운 연산들을...
-
djm03178's profile image
djm03178
July 18, 2020
Codeforces 레이팅
서론 현존하는 알고리즘 대회 사이트 중 최대 규모라고 할 수 있는 Codeforces는 유저들의 랭킹을 결정하기 위한 자동화된 레이팅 시스템을 가지고 있습니다. 각 유저가 대회를 참가할 때마다 그 성적에 따라 레이팅이 변화하는 방식으로, 비교적 합리적인 결과를 보여주지만 때로는 논란이 될 수 있는 행동을 보이기도 합니다. 이 글에서는 Codeforces의 레이팅을 산출하는 공식에 대해 분석해 보고, 이 공식이 가진 특징과 경향, 그리고 한계와 문제점을 예시를 통해 확인해 보도록 하겠습니다. Elo 레이팅 Codeforces의 레이팅은 Elo 레이팅에 기반을 두고 있습니다....
-
djm03178's profile image
djm03178
June 11, 2020
부동소수점에 대한 이해 2
서론 지난 글에서는 부동소수점 자료형이 무엇이고, 이들의 대표적인 표준인 IEEE 754에서 규정한 이진법 16비트 자료형의 세부적인 구조 및 10진수와 서로 변환하는 법 등을 알아보았습니다. 이번 글에서는 지난 글에 이어, 부동소수점 자료형으로 나타낸 수들끼리의 사칙연산을 수행하는 과정을 알아보고, 실제 프로그래밍 언어에서의 수학 라이브러리 함수를 보며 비교적 간단한 연산들을 어떻게 구현하게 되는지에 대해 알아보도록 하겠습니다. 사칙연산 사칙연산과 같은 기본적인 연산은 CPU, 또는 FPU (floating-point unit)에 내장되어 있기 때문에 별도의 라이브러리 없이도 사용이 가능합니다. 이 문단에서는 부동소수점 자료형을...
-
djm03178's profile image
djm03178
May 15, 2020
부동소수점 자료형에 대한 이해 1
서론 많은 프로그래밍 언어들에서 우리는 부동소수점 자료형을 사용하게 됩니다. 대표적으로 C, C++의 float와 double, 그리고 long double이 있습니다. 이러한 자료형들을 사용할 때에는 항상 듣는 주의사항이 있습니다. “오차가 발생할 수 있으니까 주의해야 해!” 이러한 경고는 듣는 것만으로는 잘 와닿지 않지만, 부동소수점 자료형들을 실제로 사용해보면 상식적으로는 이해되지 않는 어처구니 없는 상황을 목격하게 됩니다. 대표적으로 0.1 + 0.2 == 0.3이 거짓이라거나, 1.0 / 7.0을 7번 더했는데 1.0과 다르다고 나오는 것들을 보면서 비로소 이 자료형은 이런 간단한 연산 하나...
-
djm03178's profile image
djm03178
April 13, 2020
루트로 문제 뚫기
서론 수준급의 알고리즘 문제를 풀다 보면 다양한 장벽에 가로막히곤 합니다. 어려운 문제들 중에는 특히 쿼리형1의 문제가 많은데, 이런 문제들은 단순한 방법으로 답을 도출해내는 것은 쉽지만 시간 복잡도를 줄이는 데에 복잡한 자료구조가 요구되어 난이도가 매우 높아지는 경우가 많습니다. 이러한 문제들의 의도는 주로 특수한 형태의 트리2나 이분 탐색 등을 활용하여 $O(Q\log^K{N})$ 꼴의 시간 복잡도를 만들어내도록 하는 것이지만, 일부 문제의 경우 $O((N+Q)\sqrt{N})$과 같이 루트가 시간 복잡도에 포함되는 것이 정해인 경우도 있습니다. 대표적인 것이 이전에 소개한 바 있는 Mo’s...
-
djm03178's profile image
djm03178
March 17, 2020
GCC 확장 기능 2
서론 지난 글에서는 GCC에서 다양한 목적들을 가진 방대한 양의 확장 기능들을 제공한다는 것을 보았습니다. 이번 글에서는 지난 글에 이어 더 많은 확장 기능들을 살펴보고 어떻게 활용할 수 있을지에 대해 설명하도록 하겠습니다. 포인터를 사용한 goto 표준에서 goto문은 이름을 지정한 레이블로만 점프가 가능합니다. GCC에서는 이를 확장시켜서, 레이블이 위치한 주소를 얻어와 포인터를 사용하여 goto를 할 수 있도록 만들어 줍니다. 예시 코드는 다음과 같습니다. #include <stdio.h> int main(void) { int i = 0; void *ptr = &&start; start: printf("hello\n");...
-
djm03178's profile image
djm03178
February 17, 2020
Codeforces Round #620 개최 후기
개요 Codeforces Round #620 (Div. 2) Announcement Editorial Codeforces Round #578 개최 후기 작년 여름, nong (전 hyunuk) 님과 함께 개최한 Codeforces Round #578 (Div. 2)은 저의 문제 풀이 경력에서 가장 멋진 경험이었다고 해도 과언이 아닙니다. 항상 문제를 푸는 입장에서 참여하고 비교적 소규모의 대회 몇 개에만 부분 출제 및 검수를 해본 것이 전부였던 저에게 만 천 명이 넘게 등록한 대회의 문제 반을 출제하여 성공적으로 개최한 것은 굉장한 일임이 분명했습니다. 하지만 후기글에 남겼던 것과 같이 문제마다...
-
djm03178's profile image
djm03178
January 17, 2020
GCC 확장 기능
서론 프로그래밍을 하면서 C나 C++의 레퍼런스를 찾다 보면 표준의 디테일에 놀라게 되는 경우가 많습니다. 평소에는 무심하게 사용해왔던 문법에 들어있는 다양한 제약 조건이나, 키워드들의 알지 못했던 쓰임새들을 종종 보게 됩니다. 그런데 그렇게 방대한 스펙을 가지고도 사람들은 더 많은 것을 바라기 마련입니다. 표준상으로는 지원되지 않는 문법을 통해 더욱 편리한 코드를 만들거나, 어셈블리 명령을 직접 적어넣지 않아도 프로세서의 좋은 기능을 컴파일러가 최대한 살릴 수 있게 보장해 주었으면 하는 등 끝없이 더 많은 기능을 원하고 있습니다. 이를 충족시키기 위해...
-
djm03178's profile image
djm03178
December 12, 2019
Heavy-Light Decomposition
서론 알고리즘 문제를 풀다 보면 많은 경우에 문제를 그래프 문제로 모델화할 수 있음을 보게 됩니다. 여러 요소들간의 관계가 주어지는 경우에는 각 요소를 정점으로, 관계를 간선으로 두는 방식의 모델화가 자주 사용되고, DP 문제는 대다수의 경우 DAG(Directed Acyclic Graph)의 형태로 각 상태가 이어지게 되므로 역시 그래프 문제의 일종으로 볼 수 있습니다. 그런데 특별한 제약 조건이 없는 그래프 문제의 경우 이 모델화에 성공하면 대체로 문제가 쉬워지거나, 전형적인 알고리즘을 요구하는 문제로 바뀌게 됩니다. 오히려 제약 조건이 추가된 형태일수록 그...
-
djm03178's profile image
djm03178
November 13, 2019
더 빠른 문제 풀이 코드를 위한 상수 줄이기 2
개요 지난 글에서는 문제 풀이에 있어 상수가 가지는 의미와, 상수 차이에 의해 현저히 드러나는 퍼포먼스의 차이를 몇 가지 실험을 통해 보았습니다. 먼저 입출력 방법에 따라 수십 배 이상도 차이가 벌어질 수 있음을 보았고, std::set과 같이 Red–black tree를 쓰는 자료구조는 std::priority_queue에 비해 같은 연산을 하더라도 훨씬 느리다는 것을 보았습니다. 또한 광범위한 영역의 메모리를 빠르게 특정 값으로 채우거나, 복사하거나, 옮기는 데에는 1바이트씩 반복문을 통해 수행하는 것보다 memset, memcpy, memmove 등의 함수를 사용하는 것이 월등히 빠르다는 것도 살펴보았습니다....
-
djm03178's profile image
djm03178
October 17, 2019
더 빠른 문제 풀이 코드를 위한 상수 줄이기
개요 알고리즘을 공부하면 언제나 등장하고, 항상 신경써야 하는 요소가 있습니다. 바로 시간 복잡도 입니다. 공간 복잡도도 중요한 요소이기는 하지만, 메모리 사용량만큼의 시간이 걸리는 알고리즘은 효율적이지 않은 경우가 많기 때문에 상대적으로 덜 언급되곤 합니다. 하지만 어느 분야나 그렇듯이 이론과 현실에는 거리가 있기 마련입니다. 정확히는 알고리즘을 공부할 때 배우는 요소들은 문제를 푸는 수학적인 방법만을 고려한 것이지만, 문제 풀이를 할 때는 그 알고리즘을 프로그래밍 언어로 구현해내야 하고, 실제로 컴퓨터를 통해 실행시켜야 하기 때문에 시간 복잡도를 계산해서 예측한 속도와는...
-
djm03178's profile image
djm03178
September 16, 2019
Codeforces Round #578 개최 후기
개요 Codeforces Round #578 (Div. 2) Announcement Editorial 지난 8월 11일, 현재 세계 최대 규모의 사설 프로그래밍 대회 사이트인 Codeforces에서 hyunuk (aka. jwvg0425) 님과 제가 공동 개최한 Codeforces Round #578 (Div. 2)가 열렸습니다. 이전까지 소규모 대회 개최에 출제자나 검수자로 참여해보기는 했었으나, 백 명 내외가 참가했던 기존 대회들과는 달리 무려 만 명이 넘게1, 그것도 전세계에서 참가하는 대회였기에 본격적이었습니다. 이 글에서는 이 라운드가 개최되기까지의 전 과정을 돌이켜보며 생각을 서술하고, 문제별로 간단한 솔루션과 함께 코멘트를 남겨보려고 합니다. 역사...
-
djm03178's profile image
djm03178
August 17, 2019
Python의 큰 정수 표현법 3 - 기타 연산
이전 글 Python의 큰 정수 표현법 1 Python의 큰 정수 표현법 2 개요 지난 글들에서는 Python의 int가 큰 정수를 표현하기 위해 어떤 구조를 사용하고, 그 값을 C의 기본 자료형이나 문자열로 변환하는 방법이 무엇인지, 오브젝트끼리의 비교를 어떻게 하는지, 사칙연산은 어떻게 적용시키는지 등에 대해 알아보았습니다. 이번 글에서는 한 걸음 더 나아가, 지금까지 다루지 않은 몇 가지 연산들과 기타 기능들에 대해 알아보겠습니다. 단항 연산자 본격적으로 어렵고 복잡한 연산자들에 들어가기 전에, 간단한 단항 연산자들을 몇 가지 살펴봅시다.. 부호 변경...
-
djm03178's profile image
djm03178
July 21, 2019
Python의 큰 정수 표현법 2 - 사칙연산
개요 지난 글에 이어, 이번 글에서는 Python의 int가 실제로 여러 가지 연산을 수행하는 방법에 대해 파헤쳐 보겠습니다. 이전에 살펴본 것처럼 Python은 큰 정수를 표현하기 위해 크기를 변화시킬 수 있는 배열을 사용하고, 배열의 각 원소는 4바이트의 크기를 가지며 $0$ 이상 $2^{30}-1$ 이하의 값을 가집니다. $i$번째 원소를 $i$제곱하여 더한 값이 그 int가 나타내는 실제 값이라고 했었습니다. 당연하지만 CPU가 이런 구조에 대한 직접적인 연산을 지원하지 않기 때문에, 간단한 연산, 비교 연산이나 사칙연산조차도 CPU가 계산할 수 있는 단위까지 쪼개어...
-
djm03178's profile image
djm03178
June 16, 2019
Python의 큰 정수 표현법 1
개요 대부분의 프로그래밍 언어, 특히 거의 모든 저레벨 언어에는 정수형 크기에 제한이 있습니다. 대체로 바이트 단위로 끊어서 1바이트, 2바이트, 4바이트, 8바이트 정도의 정수형들을 사용할 수 있고, 언어와 컴파일러에 따라서는 16바이트 정수형이 제공되기도 합니다. 이와 같은 제한은 현대 프로세서들의 연산 능력을 고려하여 디자인된 것이라고 할 수 있습니다. 최근까지도 32비트/64비트 프로세서들이 주류를 이루고 있고, 이는 곧 프로세서가 연산을 수행하는 레지스터의 크기가 4/8바이트 정도이며 한 번의 연산 단위가 될 수 있다는 뜻이 됩니다. 따라서 이 크기에 맞추어 자료형을...
-
djm03178's profile image
djm03178
May 6, 2019
특별한 정렬 알고리즘들 2
개요 이번 글에서는 지난 달 글에 이어서 조금 더 다양한 정렬 알고리즘을 소개해 보려고 합니다. 저번 글에서도 언급했지만 정렬의 종류는 엄청나게 다양하며, 이 글에서 소개하는 정렬 알고리즘들은 그들 중 극히 일부에 불과합니다. 개중에는 병렬 처리가 되거나 쓰기 연산이 극도로 비싼 등 매우 특수한 실행 환경에서만 이득이 되는 것들도 있고, 데이터가 거의 정렬된 상태에서 매우 효율적인 알고리즘, 또는 현실 세계의 데이터들에 적합하도록 고안된 알고리즘 등도 있었고, 마지막에 잠깐 언급한, 그저 재미를 위해서만 만들어낸, 비효율적이기만 한 알고리즘들도...
-
djm03178's profile image
djm03178
April 10, 2019
특별한 정렬 알고리즘들
개요 정렬(Sorting)은 알고리즘 문제 풀이뿐 아니라, 어떤 분야의 프로그래밍을 하면서도 수없이 마주치는 문제입니다. 일반적으로 정렬에 대해 공부할 때는 $O(N^2)$이지만 기본 개념을 설명하기 위해 배우는 버블 정렬(Bubble sort), 삽입 정렬(Insertion sort), 선택 정렬(Selection sort) 등과, 보다 효율적으로 $O(NlogN)$ 시간에 해결해주는 퀵정렬(Quicksort), 병합 정렬(Merge sort), 힙정렬(Heapsort), 그리고 비교 기반이 아닌 자릿수(digit) 기반으로 $O(N)$에 해결하는 기수 정렬(Radix sort), 카운팅 정렬(Counting sort) 정도를 배우게 됩니다. 굉장히 많은 종류의 정렬을 배운 것 같지만, 정렬에 대해 더 깊이 파고 들어가보면 이...
-
djm03178's profile image
djm03178
March 9, 2019
효율적인 긴 문자열 연산을 위한 Rope 자료구조
로프와 쿼리 최근 백준 온라인 저지에 로프와 쿼리라는 이름의 베타 문제가 올라왔습니다. 그런데 문제 본문의 어디를 보아도 로프라는 단어는 쓰이지 않고, 줄과 관련되어 보이는 부분도 없습니다. 그저 문자열의 일부를 잘라서 앞이나 뒤로 옮기는 쿼리를 수행하는 문제일 뿐입니다. 그러면 이 문제의 이름은 왜 로프와 쿼리인 걸까요? 일반적인 문자열 자료구조로는? 우선 이 문제를 단순한 std::string 객체로 해결을 시도해 봅시다. #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int q; cin...
-
djm03178's profile image
djm03178
February 9, 2019
Mo's Algorithm
개요 Mo’s algorithm은 평방 분할 (sqrt decomposition)의 일종의 활용 기법으로, 오프라인으로 구간 쿼리 문제를 해결할 때 사용할 수 있습니다. 어떤 구간에 대한 정보를 빠르게 얻기 어려워 그 구간에 속한 $O(N)$개의 원소를 매번 모두 확인해야 하는 경우, $Q$개의 쿼리를 나이브하게 처리하려면 $O(QN)$의 시간이 소요될 것을 $O((N+Q)sqrt(N))$ 시간에 해결할 수 있게 해주는 마법의(?) 알고리즘입니다. 평방 분할 (sqrt decomposition) 우선 평방 분할에 대해 간단하게 소개하겠습니다. 평방 분할은 길이 $N$인 전체 구간을 $\sqrt N$개의 같은 크기의 블록으로 쪼개는 기법입니다....
-
djm03178's profile image
djm03178
January 9, 2019
잘못 구현한 다익스트라 알고리즘 저격하기
개요 다익스트라 알고리즘은 음이 아닌 가중치가 있는 그래프에서 최단 경로를 찾는 가장 기본적이고 효율적인 알고리즘으로 널리 알려져 있습니다. 정점의 수가 $V$, 간선의 수가 $E$일 때 다익스트라 알고리즘은 구현하는 방법에 따라 매 루프마다 전체 정점을 탐색해서 최단 거리의 정점을 선택하여 $O(V^2+E)$, 힙을 사용한 우선순위 큐로 구현하여 $O(VlogE+ElogE)$, 피보나치 힙을 사용해 시간복잡도를 줄이지만 큰 상수 때문에 실제로는 거의 사용되지 않는 $O(VlogV+E)$ 등의 시간복잡도를 가질 수 있지만, 이 중 가장 대중적이면서도 대부분의 문제에 사용해도 무리가 없는 버전은 힙을...