자료구조에 대해서 공부를 시작하려는데 책하나를 가지고 앞에서부터 주욱 공부해 나가는게 좋은 방식이겠지만...
어떤 계기가 있어서 해싱에 대해서 좀 찾아보게 됐고 공부야 뭐 여러가지 그림이나 이해를 돕기위한 자료들로 했지만 일단은 내 머리속에서의 흐름대로 정리하기 위해 간단하게 글로 포스팅한다.
일반적으로 탐색 알고리즘은 키값을 비교해서 그 데이터의 주소를 얻는다.
그래서 속도를 빠르게 하려고 비교 횟수를 줄이기 위한 노력들을 많이 하는데... 주로 데이터를 미리 정렬해놓고 이진검색을 하거나 보간검색을 하는 등 확률적으로 최대한 키값을 빨리 찾아내도록 알고리즘을 만든다.
하지만 해싱을 이런 방식과는 완전히 다르게 탐색시간을 획기적으로 줄일 수 있는 듯 하다.
해싱은 해시테이블에 데이터를 집어넣을 때 일정한 규칙을 가지고 키값을 연산하여 해당 주소에 집어넣는다.
그러므로 해당 키값에 대한 데이터를 찾을때는 키값을 연산하여 주소를 구할수 있고 옵티멀한 경우 한번의 연산만으로도 데이터의 주소를 얻을 수 있다.
이때 연산하는 규칙으로 주로 mod연산을 많이 사용한다고 한다.
하지만 연산에 의한 값이므로 다른 키값에 대한 연산결과가 테이블의 같은 주소를 가르킬 수도 있다.
이런 경우를 충돌이라고 하는데 이 충돌을 해결하기 위해서 충돌 발생시 비어있는 다른 주소를 찾아주는 선형조사법, 이차조사법, 이중 해싱법 등을 사용한다.
선형조사법은 충돌 발생시 바로 다음 주소에 데이터를 집어넣는 방식이다. 단순한 방식이지만 데이터가 특정 구간에 몰리는 clustering 현상이 발생하기 쉽다.
상식적으로 생각해봐도 데이터를 그 바로 다음 부분에 집어넣으면 해시테이블에서 데이터가 들어있는 부분들이 붙어있게 되고 그 붙어있는 덩어리가 커질수록 새로운 키 연산결과가 그 큰 덩어리 가운데 어딘가일 확률도 높아진다. 그냥 덩어리만 붙어있으면 별 상관이 없겠지만 덩어리 바로 다음부분의 빈공간을 찾을때까지 계속 1씩 증가하며 확인과정을 거쳐야 하므로 연산 효율이 크게 떨어진다.
이차조사법은 선형조사법의 군집화 문제를 피하기 위해서 1씩 증가된 주소에 넣는것이 아니라 1 4 9 16 이런식으로 제곱단위로 증가된 주소에 데이터를 넣는 방식이다. 완전히 극복되지는 않는듯.
이중 해싱법은 새로운 연산, 보통 C - key mod C(C는 테이블 크기보다 약간 작은 소수) 이런식으로 많이 정해서 쓰는데 이 연산의 값만큼 뒷쪽 주소에서 빈공간을 찾는 방식이다. 마찬가지로 완전히 극복되지는 않는 듯.
또 아예 충돌이 발생하면 뒷쪽에 연결리스트로 달아버리는 체이닝 기법도 있다. 보통 모든경우에 결과가 위 방식들보다 빠르다고 알고있다.
dll injection에 대해서 공부하면서 여러가지 시도해본 것중에 하나. 예전에 만들었었는데 워게임 위주로 포스팅을 하다보니 깜빡하고 있었다.
내용을 간단히 소개하면 KeyHook이라는 dll파일을 하나 생성하고 keyboard proc이라는 콜백 함수를 통해서 키보드 메시지를 후킹하고 타겟 프로세스에 대해서 로그로 기록하거나 키입력이 다른 문자를 출력하는 등 기능을 구현한다.
그리고 이 dll을 로딩시켜주는 프로그램을 만들어 KeyHook.dll 에 미리 정의해둔 HookStart, HookStop 함수를 읽어와서 후킹을 시작하고 종료시키는 내용이다.
당시 만들자마자 테스트했던 영상.
notepad와 카카오톡 pc버전 2개 프로세스를 대상으로 코드를 짰었는데 해당 프로세스가 32비트용으로 제작되었는가 64비트용으로 제작되었는가에 따라서 dll의 컴파일도 맞춰줘야 한다. 그리고 q를 받아 종료하는 로더 역시 프로세스이므로 이 프로세스도 dll과 32/64비트 호환이 되지 않으면 정상적으로 입력을 받아 종료할 수 없다. 여러가지로 허술한 프로그램이긴 하지만 그래도 winapi를 처음 공부하는 과정에서 참 뿌듯했던 결과물 중 하나다.
타겟이 notepad인것과 카카오톡인것 두가지 버전의 dll과 로더를 각각 만들었었는데 spy등으로 카카오톡 하위 윈도우 핸들을 잡아왔던거랑 몇가지 사소한 차이 빼고는 코드가 거의 같으므로 메모장을 대상으로 하는 키로거의 소스만 소개한다.
주석으로는 설명이 부족한 것 같아 덧붙이자면 입력 행렬 matrix를 받고 이 행렬에서 0이 오른쪽으로 몇개 연속되는지를 나타내는 행렬 matrix2를 새로 만든다.
matrix2에서 각 원소의 값은 matrix에서 해당 인덱스의 원소 포함 오른쪽으로 0인 원소가 몇개인지를 나타내므로
matrix2(i, j)=n이라고 할때 matrix2(i+1, j)가 n보다 크거나 같다면 i+1번째 행을 포함하는 가로가 n인 직사각형을 만들 수 있다는 뜻이다.
이런 점을 이용해서 matrix2의 모든 원소에서 자신보다 크거나 같은 원소가 아랫쪽으로 몇개가 연속되는지 구하고 그 갯수*자신의 값 n을 해서 직사각형의 넓이를 구하고 그 최대값을 출력하는 방식이다.
#-*-incoding:utf-8-*-
#python
import sys
def count_zero (arr, j, width, cnt): #행에서 연속되는 0의 갯수를 찾아주는 함수
if j==width-1: #마지막 원소일경우
return cnt
if arr[j+1]==0:
return count_zero(arr, j+1, width, cnt+1)
else:
return cnt
def count_num (matrix, i, j, height, cnt, num): #같은열 아래에 자신보다 큰 숫자가 몇개 연속되는지 반환
if i == height-1:
return cnt
if matrix[i+1][j]>=num:
return count_num(matrix, i+1, j, height, cnt+1, num)
else:
return cnt
size=raw_input().split()
height=int(size[0])
width=int(size[1])
matrix=[[0 for col in range (width)] for row in range (height)] #입력받을 행렬
matrix2=[[0 for col in range (width)] for row in range (height)] #0이 연속되는 갯수를 저장할 행렬
for i in range (height): #입력행렬을 받는 부분
arr=sys.stdin.readline().split()
for j in range (width):
matrix[i][j]=int(arr[j])
for i in range (height): #입력행렬에서 자신으로부터 오른쪽으로 0이 연속되는 갯수를 matrix2에 저장
for j in range (width):
if matrix[i][j] == 0:
matrix2[i][j]=count_zero(matrix[i], j, width, 1)
max_size=0
for j in range (width):
for i in range (height):
tmp=count_num(matrix2, i, j, height, 1, matrix2[i][j]) #tmp: 사각형의 높이, matrix2[i][j]: 넓이
if tmp*matrix2[i][j] > max_size:
max_size = tmp*matrix2[i][j]
print max_size
#-*-incoding:utf-8-*-
#python
import sys
num=int(raw_input())
matrix=[[0 for col in range (num)]for row in range (num)] #num 사이즈의 2차원 배열
for i in range (num): #배열을 읽어들이는 부분
arr=sys.stdin.readline().split()
for j in range (num):
matrix[i][j]=int(arr[j]) #matrix에 값을 넣어줌
for i in range (num):
for j in range (num-1, -1, -1):
print matrix[j][i], # y축을 그대로 x축으로 출력하고 x축은 y축을 역순우로 출력
print ''
#-*-incoding:utf-8-*-
#python
import sys
def check_lock(matrix, i, j): #갇혀있는지 확인하는 함수
for y in range (i-1, i+2): #(i-1)~(i+1)까지 검사
for x in range (j-1, j+2):
if y==i and x==j: #자기자신이 1인것은 넘어간다
continue
if matrix[y][x]==1:
return 0
return 1
pos=raw_input()
tmp=pos.split()
pos_int=list()
size_y=int(tmp[0])
size_x=int(tmp[1])
matrix=[[0 for col in range(size_x)] for row in range(size_y)] #2차원 배열 생성
for i in range (size_y): #입력값을 matrix에 넣어준다
tmp2=sys.stdin.readline() #여러줄 입력시 EOF문제를 해결하기 위해서
tmp3=tmp2.split()
for j in range (size_x):
matrix[i][j]=int(tmp3[j]) #matrix에 값 넣어줌
for i in range (1, size_y-1): #1~ size-1인 이유는 가장 바깥쪽 라인은 갇힐 수 없기 때문
for j in range (1, size_x-1):
if check_lock(matrix, i, j):
print "%d,%d" % (i+1, j+1) #i, j가 0부터 시작하기 때문에 1씩 더해준다.
#-*-incoding:utf-8-*-
#python
import sys
str_input=raw_input()
arr=str_input.split()
arr2=list() #숫자단위로 쪼개 넣을 리스트
for i in range (len(arr[0])): #각각 자릿수별로 쪼개서 arr2로 넣어줌
arr2.append(arr[0][i])
for i in range (len(arr[1])):
arr2.append(arr[1][i])
arr2.sort() #오름차순 정렬
arr2.reverse() #뒤집어서 내림차순으로
for i in range (len(arr2)):
sys.stdout.write(arr2[i]) #붙여서 출력하기 위해서
print ''
