-
bash 단축키 뜯어보기
bash같은 쉘은 정말 강력한 기능을 지니고 있고, 이러한 터미널 및 쉘이 *nix 계열의 심장이라 해도 과언이 아닙니다. 유명한 sudo나 rm -rf /, apt-get, git clone, pip install, gcc -O2 -Wall -o test test.c, echo Hello World! 등등 수많은 커맨드들이 오늘도 전 세계에 컴퓨터에서 돌아가고 있습니다. GUI에서 다양한 클릭과 스크롤을 통해서 진행되는 일들이 CLI에서는 한 줄의 명령어로 된다는 점이 매력이라 할 수 있겠습니다. 쉘은 커맨드 측면에서도 다양한 편의성을 제공하지만, 간단한 단축키를 통해서도 수많은 ‘방향키-지우기-다시 쓰기’를 한...
-
Graph, SCC and BCC
목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 DFS Numbering에 대한 많은 재미있는 사실들이 있다. 최근에 고급 알고리즘이라는 과목을 들으면서 DFS에서 Numbering을 할때 가지는 자체적인 성질과 그에 관련된 알고리즘들을 공부하게 되었다. SCC와 BCC가 그런것들이다. 이들은 PS에서 매우 유용하게 쓰일 수 있으며, 다양한 상황에 적용할 수 있고, 알아두는 것만으로 풀 수 있는 문제영역이 넓어진다. 또한 DFS Numbering 자체가 구현 자체가 쉬우므로 보통 Dynamic Programming 이나, 2-SAT등 다양한...
-
Web Worker-Postable 라이브러리 작성기
필자는 최근 Electron 플랫폼을 기반으로 한 오픈소스 영상 편집 프로그램을 만들고 있습니다. 프리미어 프로의 저질 짝퉁 버전이라고나 할까요. 웹 생태계의 특성상 새로운 기술들이 빠르게 적용되긴 힘들지만, 동시에 웹에 대한 많은 관심이 수년간 이어지면서 이에 대한 논의와 도입이 활발하게 이루어지고 있는것은 굉장히 즐거운 일이라고 생각합니다. 저같이 뭣도 모르는 녀석도 영상 편집 프로그램 같은걸 만들 생각도 할 수 있게 해주니까요. 이 프로그램에서 핵심이 되는 부분 중 하나는 OffscreenCanvas 이라는 기술입니다. 영상 편집 프로그램은 당연히 영상을 렌더링해서 보여주는...
-
빠른 다항식 나눗셈
들어가며 두 다항식의 곱셈에는 다양한 방법들이 있습니다. 항을 하나씩 곱해서 더하는 $O(N^2)$ 알고리즘부터, 분할 정복을 이용해 $O(N^{\log_2 3})$의 시간에 동작하는 카라츠바 알고리즘(Karatsuba algorithm), 빠른 푸리에 변환(Fast Fourier transform)을 이용해 $O(N \log N)$의 시간에 동작하는 알고리즘까지 다양합니다. 이 글에서는 다항식의 곱셈을 빠르게 하는 방법을 알고 있다는 것을 전제로, 다항식의 나눗셈을 빠르게 하는 방법을 소개하고, 얼마나 더 빠른지를 비교해 볼 것입니다. $O(N^2)$ 알고리즘 본격적으로 시작하기 전에, 빠른 다항식 나눗셈 알고리즘이 얼마나 빠른지를 비교해 보기 위해서 $O(N^2)$ 알고리즘을...
-
특별한 정렬 알고리즘들
개요 정렬(Sorting)은 알고리즘 문제 풀이뿐 아니라, 어떤 분야의 프로그래밍을 하면서도 수없이 마주치는 문제입니다. 일반적으로 정렬에 대해 공부할 때는 $O(N^2)$이지만 기본 개념을 설명하기 위해 배우는 버블 정렬(Bubble sort), 삽입 정렬(Insertion sort), 선택 정렬(Selection sort) 등과, 보다 효율적으로 $O(NlogN)$ 시간에 해결해주는 퀵정렬(Quicksort), 병합 정렬(Merge sort), 힙정렬(Heapsort), 그리고 비교 기반이 아닌 자릿수(digit) 기반으로 $O(N)$에 해결하는 기수 정렬(Radix sort), 카운팅 정렬(Counting sort) 정도를 배우게 됩니다. 굉장히 많은 종류의 정렬을 배운 것 같지만, 정렬에 대해 더 깊이 파고 들어가보면 이...