-
알고리즘 문제 풀이
알고리즘 문제 풀이 3월에 푼 재미있는 문제들의 풀이를 써보았습니다. BOJ 1352번 문자열 아래와 같은 $dp$를 정의합니다. $dp(x, sum)$ := $0$~$x-1$번째 인덱스까지 처음으로 사용한 문자들의 인덱스합이 $sum$ 일 때, $x$번째 ~ 마지막까지를 적절히 정하여 길이 $N$의 ideal string 을 만들수 있는지 여부(가능하면 1, 불가능하면 0) 이 $dp$의 transition은 어떻게 될까요? 각 상태에서 선택할 수 있는 것이 무엇인지 고민해 봅시다. 각 상태에서 우리가 정해야 하는 것은 $x$번째 인덱스에 들어올 문자입니다. 우리가 이 $dp$에서 알고자 하는 것은 최종적으로...
-
기본적인 Git 사용법과 Pull Request를 통해 프로젝트 기여하기
VCS? Git? GitHub? Git이란 버전 관리 시스템(VCS, Version Control System)의 한 종류입니다. 그렇다면 여기서 말하는 버전 관리란 무엇이고, 왜 필요할까요? 버전 관리란 이름 그대로 여러 파일을 하나의 버전으로 묶어 관리합니다. A라는 소스코드의 묶음이 있을 때, 이를 버전1이라는 이름으로 저장해봅시다. 이후 버전1에서 파일을 추가하거나, 삭제하거나, 수정하는 등의 작업을 거쳐 버전2라는 이름으로 저장합니다. 마찬가지로 버전2에서 버전3를 만듭니다. 아차, 그런데 버전2에서 수정한 파일 때문인지 오류가 생겼습니다. 이때 우리는 이전에 저장해둔 버전1을 불러와 다시 작업할 수 있습니다. 만약 문제가...
-
LD_PRELOAD 를 이용한 후킹
안녕하세요. 오늘은 리눅스 환경에서 LD_PRELOAD 환경변수를 이용해서 후킹을 하는 방법에 대해 간략히 포스팅해볼까 합니다~ 후킹이란? 후킹(영어: hooking)은 소프트웨어 공학 용어로, 운영 체제나 응용 소프트웨어 등의 각종 컴퓨터 프로그램에서 소프트웨어 구성 요소 간에 발생하는 함수 호출, 메시지, 이벤트 등을 중간에서 바꾸거나 가로채는 명령, 방법, 기술이나 행위를 말한다. 이때 이러한 간섭된 함수 호출, 이벤트 또는 메시지를 처리하는 코드를 후크(영어: hook)라고 한다. 크래킹(불법적인 해킹)을 할 때 크래킹 대상 컴퓨터의 메모리 정보, 키보드 입력 정보 등을 빼돌리기 위해서 사용되기도...
-
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등 다양한...