+ 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!

 + 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!

 + 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~

 + '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.

 + 혹시라도 문제가 된다면 바로 조취를 취할테니, 말해주시면 감사하겠습니다!


우리가 StackOver Flow나 다른 개발 서적에서 흔히 볼 수 있는 Hooking이란 뭘까?


<Hooking>


[What?]

 + Hooking은 OS나 SW등에서 발생하는 함수호출이나 메시지 전달, 이벤트 등을 중간에 가로채서 내용을 바꾸거나 데이터를 얻거나 다른 후처리를 하는 것.


 + 이런 작업을 하는 코드를 Hook이라고 한다.


 + 진행 과정 중, "갈고리로 중간을 낚는다"고 생각하면 된다!


 + 크래킹(불법적인 해킹)에서는 대상 컴퓨터의 메모리 정보, 키보드 입력 등으로 중요한 정보를 빼낼 때 사용한다.


 + 특정 API를 후킹하면, 해당 API의 리턴값을 조작하는 등의 행동이 가능!


후킹에 여러 방법이 있는데 여기를 참고할 것!

https://ko.wikipedia.org/wiki/%ED%9B%84%ED%82%B9



[Example - Windows]

 + Windows를 예시로 들면, 우리가 Windows에서 SW를 실행할 때, 수 많은 데이터를 SW와 OS가 주고 받는다. 

그것은 함수의 호출일 수 있고, 키보드나 마우스의 이벤트일 수 있고, 메모리를 읽고 쓰는 것일 수 있다.

그런 작업의 중간에 실행될 수 있는게 Hooking이다.


 + Hook은 메시지를 가로챌 범위에 따라 지역 훅(Thread Specifin)과 시스템 전역 훅(System Wide)로 나눈다.

특정 쓰레드에서 발생하는 메시지만 받거나, 모든 메시지를 받거나 할 수 있는 것!


 + Hook을 사용하기 위해서는 기본적으로 해당 SW에 설치해야한다.

SW에 따라 여러 훅을 설치할 수 있는데, 이런 Hook들은 OS에서 Hook Chain으로 관리된다.

등록된 여러 Hook들이 서로 엮여있고, 메시지가 전달 될 때마다 순서대로 Hook을 지나가면서 메시지를 감시한다.

이런 과정에서 메시지가 변질되거나 없어질 수 있으니 조심할 것!



*** 참고해야할 점

 - 여러 Hook을 사용하는 경우, 당연히 느려기게되니, 꼭 필요한 상황이거나 사용 목적을 달성한 후에는 제거하는 것이 좋다!

 - 'callback'은 Hook의 타입 중 하나다.

 - 프로그램의 성능을 분석할 때 많이 사용한다.



** 참고사이트 **

 - http://jinuine.blogspot.com/2014/05/hooking-hooking.html

 - https://ko.wikipedia.org/wiki/%ED%9B%84%ED%82%B9

 - https://whatis.techtarget.com/definition/hook

 - https://stackoverflow.com/questions/467557/what-is-meant-by-the-term-hook-in-programming


Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.

저작자표시 비영리 변경금지

2020년까지 앞으로 약 16일 정도 남았다.



2019년 처음 '게임 프로그래머'로 사회에 발을 들이고,


벌써 1년이라는 시간이 흘렀구나...



1년동안 우여곡절이 많았지만, 그 만큼 배운 것도 많았던 한 해였다.



배운 대부분을 정리하지 않고 메모만 해뒀는데,


다시금 정리하면서, 내가 배운 것들을 되돌아보고 지식으로 습득해야할 것 같다.



다시 해보자!

저작자표시 비영리 변경금지

'Daily' 카테고리의 다른 글

LINUX 개발자가 많은 이유?  (0) 2018.05.12
Notepad Update - Unix 기반 텍스트 파일의 End-Line을 지원  (0) 2018.05.09

 + 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!

 + 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!

 + 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~

 + '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.

 + 혹시라도 문제가 된다면 바로 조취를 취할테니, 말해주시면 감사하겠습니다!


<Union-Find>


[What?]

 + Union-Find는 Disjoint set(서로소 집합) 또는 Merge Find Set(병합 찾기 집합)이라고도 불리는 서로 연관되어있는 것끼리만 묶여있는 자료구조를 뜻합니다.


 + 무분별한 노드(하나의 개체)들이 있을 때, 각 노드들은 자신의 집합의 root정보를 가지고 있고, 그 정보를 비교해서 원하는 결과를 얻으려고 할 때, 사용하는 자료구조입니다.


 + 모든 노드들은 자신의 root정보로 집합이 엮여있으므로, 트리구조(2진트리X)를 따릅니다.


 + 예를 들자면,

1)  A,B,C,D,E 와같이 5개의 노드가 있다고했을 때, 각 노드는 자신을 하나의 집합이라고 생각하고, 그 집합의 루트 정보를 가지고 있습니다. 그 루트 정보를 가지고 같은 집합인지 비교하는 것입니다.

=> A(A), B(B), C(C), D(D), E(E)


2) 여기서, A와 B를 비교해서 root가 다르면 같은 집합으로 묶어주고, C와 D를 비교해서 root가 다르면 같은 집합으로 묶어줍니다.

=> {A(A), B(A)}, {C(C), D(C)}, E(E)-여기서 누가 root가 될 건지는 개발자 마음입니다.


3) 여기서 E와 A의 루트와 비교해서 root가 다르다면 같은 집합으로 묶어 줍니다.

=> {A(A), B(A), E(A)}, {C(C), D(C)}


 + 위와 같은 방법으로 자료구조를 형성하여 사용하는 것이 Union-Find입니다.


[Use]

 + 일반적인 구조는 아래와 같은 형태를 가집니다.
void findFunc(int x) {
    if (parent[x] == x) return x;
    return find(parent[x]);    // 자신의 root를 찾아서 반환합니다.
 
void uniFunc(int x, int y) {
    parent[y] = x;    // 자신의 root를 x로 바꿔, 해당 집합으로 들어갑니다.
}

 + 이렇게 하면 1열로 늘어진 자료구조가 나올 수 있습니다.(시간복잡도 n)왜냐하면, uni할 때 마다 부모인 노드가 다른 노드의 자식으로 들어가버리니까요.

 + 그걸 방지하고자, 각 집합의 부모를 찾아서, 그 부모의 자식이 되도록 설정합니다.
void uniFunc(int x, int y) {
    x = find(x);
    y = finx(y);
    if (x == y) return;
    parent[y] = x;
}

 + 이 방법에서 더 진보된 방법이있습니다. 그건, 각 집합의 높이를 비교해서 낮은 쪽을 높은 쪽으로 합치는 것입니다. 그렇게 되면, 합친 트리의 높이가 증가하지 않습니다. 시간복잡도가 더 늘어나지 않기 때문에, 위의 방법보다 더 빠른 찾기가 가능합니다.
void uniFunc(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) parent[x] = y;
    else parent[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
}
 + 여기서 rank는 높이를 뜻하고, 마지막의 rank비교문에서 x를 증가시켜주는 것은, 높이가 같을 때, x의 자식으로 y가 들어가도록 설정해두었기 때문입니다. 그렇기에 자신의 상황에 따라서 수정하면 됩니다.

 + 유니온 파인드에서 부모를 한 번 설정하면 끝까지 부모로 설정됩니다. 그렇기 때문에, 한 번 find()해서 루트 부모를 찾으면, 평생 루트 부모로 존재할 것이고, 내 부모가 될 수 있습니다. 그렇기에, 한 번 찾을 때, 최종 루트 부모를 찾아서 설정해둔다면 빠른 찾기가 가능할 것입니다.(참고로 최고 루트는 자기자신이 부모로 설정되어있다.)

void uniFunc(int x, int y) {
    x = find(x);
    y = finx(y);
    if (x == y) return;
    if (rank[x] < rank[y]) parent[x] = y;
    else parent[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
}
 
int findFunc(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

[Comment]
 + 대부분의 경우도 마찬가지지만, Union-Find는 자료구조이기에, 어떤 식으로 구성되어있는지만 익혀두고, 사용은 개발자분들 알아서, 상황에 맞게 변경해서 사용하셔야 합니다!!!

[문제추천]


** 참고사이트 **

 - https://twpower.github.io/115-union-find-disjoint-set

 - http://weeklyps.com/entry/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Unionfind

 - 

 - 


Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.

저작자표시 비영리 변경금지

'요리 레시피 > Algorithm' 카테고리의 다른 글

[BaekJoon] 이항계수, 페르마의 소정리, 거듭제곱 feat.11401번(이항계수3)  (0) 2018.05.12
[다익스트라] 다익스트라 - 유명한 최단거리 찾기 알고리즘!!!  (0) 2018.03.27
[DFS][BFS] DFS 와 BFS  (0) 2018.03.27
[Dp] DP에서 배열 사용  (0) 2018.03.26
[BackJoon] 충격의 N-Queen 문제 feat.9663번(N-Queen)  (0) 2018.03.26

+ Recent posts

티스토리툴바