-
특별한 정렬 알고리즘들 2
개요 이번 글에서는 지난 달 글에 이어서 조금 더 다양한 정렬 알고리즘을 소개해 보려고 합니다. 저번 글에서도 언급했지만 정렬의 종류는 엄청나게 다양하며, 이 글에서 소개하는 정렬 알고리즘들은 그들 중 극히 일부에 불과합니다. 개중에는 병렬 처리가 되거나 쓰기 연산이 극도로 비싼 등 매우 특수한 실행 환경에서만 이득이 되는 것들도 있고, 데이터가 거의 정렬된 상태에서 매우 효율적인 알고리즘, 또는 현실 세계의 데이터들에 적합하도록 고안된 알고리즘 등도 있었고, 마지막에 잠깐 언급한, 그저 재미를 위해서만 만들어낸, 비효율적이기만 한 알고리즘들도...
-
그래프 색칠과 NP-Completeness
서론 현실의 여러 대상들은 그래프로 추상화 할 수 있다. 그래프를 색칠하는 것은, 서로 인접한 두 정점이 같은 색을 같지 않도록 색칠 하는 것이다. 이 그래프를 색칠하는 문제는, 다양한 스케쥴링 문제 혹은 컴파일러의 레지스터 배치, 패턴 매칭, 시험/수업 시간표 작성 등 다양한 문제를 해결할 수 있다. 이런 문제들이 다항시간안에 검증이 가능하지만, 다항 시간안에 풀리는지는 밝혀지지 않는 NP-Complete 문제라는 것을 알아보자. 그래프 그래프는, 정점을 나타내는 집합 $V$와, 간선을 나타내는 집합 $E$의 원소인, $G = (V, E)$로 나타낸다....
-
알고리즘 문제 풀이
알고리즘 문제 풀이 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)라고 한다. 크래킹(불법적인 해킹)을 할 때 크래킹 대상 컴퓨터의 메모리 정보, 키보드 입력 정보 등을 빼돌리기 위해서 사용되기도...