Dior2ky의 it's IT

백준 2580번 스도쿠 문제이다. 스도쿠에 대한 규칙은 일반 스도쿠와 동일한 것으로 보인다. 빈칸을 0으로 표시하고 있다. 빈칸에 숫자를 하나씩 넣어가면서 확인해주는 백트래킹 방식이다. 이번에도 하나씩 넣어가는 solve 함수와 다음 빈칸에 숫자를 넣으러 넘어갈지를 판단해주는 promise 함수로 이루어져 있다. promise 함수에서는 가로 세로, 포함된 3x3 칸에 숫자가 있는지 확인하여 있다면 false를 리턴하여 다음으로 넘어가지 않도록 하였다. 여기서 3x3칸을 확인할 때에는 가로 세로 값인 i 와 j를 3으로 나눈 몫을 확인하여 0, 1, 2 값으로 3구역으로 나뉘기 때문에 어느 3x3 구역인지 확인하도록 하였다. import sys def promise(i, j, k): for m in ra..

백준 9663번 N-Queen 문제이다. 백트래킹으로 가장 유명한 문제라고 할 수 있는 체스판에 퀸을 놓는 문제이다. 이번 문제에서는 하나씩 놓아가면서 놓았을때 퀸이 놓일 수 있는 조건을 확인해서 놓도록 해주었다. func 함수를 통해 재귀 방식으로 하나씩 놓아가도록 하였고 promising 함수를 통해 놓는것이 가능한지 파악하였다. 언어는 C++을 사용하였다. #include using namespace std; int n; int result = 0; int arr[15] = {0,}; bool promising(int i){ for(int j = 0; j < i; j++){ if(arr[i] == arr[j] || abs(arr[i] - arr[j]) == (i - j)){ return false;..

백준 15652번 N과 M (4) 문제이다. 역시 N과 M 문제이다. 단계별로 풀어보기 백트래킹 항목에 있는 마지막 N과 M 문제이다. (다른 N과 M 문제들은 더 있다...) 이번에는 비 내림차순이라고 한다. 다른말로 하면 오름차순에 중복까지 가능하다고 생각하면 된다. 역시 백트래킹 문제이므로 비슷하게 풀어준다. N과 M (2) 문제와 비교하면 편할 것 같다. (2) 문제에서는 숫자 하나를 사용하면 그 숫자까지의 check 배열을 증가 시켰지만, 이번에는 그 숫자가 중복이 가능하므로 그 숫자 하나 아래 값 까지만 check 배열의 값을 증가시킨다. 이번 문제는 ruby 언어를 사용하였다. def func(cnt) if cnt == $m for i in 0...$m print $arr1[$arr2[i]]..

백준 15651번 N과 M (3) 문제이다. 문제는 다음과 같다. 이전 N과 M 문제들과 비슷하다. 이번에는 중복이 허용되어 있다. 역시 같은 백트래킹 문제이다. 이번에는 중복이 허용되기 때문에 check 배열이 필요가 없다.(만들어놓고 쓰질 않았다...) 그대로 모든 경우를 돌려 수열이 완성되면 출력하도록 만들어주었다. 언어는 java를 이용하였다. 입출력을 System을 이용하여 했더니 시간초과가 나와서 Buffer를 사용해주었다. 백준에서 풀때는 항상 이 방법을 사용하도록 해야겠다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader..

백준 15650번 N과 M (2) 이다. 이전 N과 M (1)과 문제가 비슷하다. 이번에는 오름차순이어야 한다는 조건이 추가되었다. 이번에도 역시 백트래킹 문제이다. 이번에는 한 숫자를 골랐다면 다음자리에는 그보다 작은 숫자가 올 수 없기 때문에 check 배열에서 고른 숫자 이하의 자리는 모두 +1 해주고 빠져나오면 -1을 해 주었다. 물론 고를때에는 1이 아닌것으로가 아닌 0인지로 판단해주었다. 언어는 python을 사용하였다. def func(cnt): if cnt == m: for i in range(m): print(list1[list2[i]], end = ' ') print() for i in range(n): if check[i] == 0: for j in range(i+1): check[j..

백준 15649번 N과 M (1) 문제이다. 문제는 다음과 같다. 문제만으로 규칙을 모르겠다면 입출력을 봐주자. 문제가 파악되었다면 문제를 풀어보자. 이번 문제는 백트래킹 문제이다. 두번째 입력값인 m이 수열의 길이이기 때문에 이 값을 하나씩 증가시키며 모든 경우를 살펴보고 조건에 맞다면 출력하도록 짜준다. 언어는 C++을 이용하였다. #include using namespace std; int n, m; int arr[8]; int arr2[8]; int check[8] = {0,}; void func(int cnt){ if(cnt == m){ for(int i = 0; i m; for(int i = 0; i < n; i++){ arr[i] = i + 1; } ..

Lena Reversing tutorial 20_8 마지막 8번째 파일은 UnPackMe_Fusion4.0.00.c 이다. Ollydbg로 열어준다. 이번에도 ESP를 이용하여 언패킹을 해본다. F8을 눌러 ESP가 처음으로 바뀌는 부분을 찾는다. PUSH EBP 수행후 ESP 값이 0012FFC0로 바뀐다. 이 값에 hw bp를 걸어준다. F9를 눌러주면 다음과 같이 break가 걸린다. 이 주소가 OEP로 추정된다. Ollydump를 통해 dump 해준다. Rebuild Import는 해제하고 dump 해준다. 끝.

Lena Reversing tutorial 20_7 7번째 프로그램은 UnPackMe_Exe32Pack1.42 이다. Ollydbg로 열어준다. 이번에도 ESP를 이용한 언패킹을 수행한다. 진행하다보면 다음 PUSH EBP가 수행되고 나면 ESP가 0012FFC0으로 바뀌게 된다. 여기에 hw bp를 걸고 실행해준다. 다음과 같은 주소에 break가 걸린다. 같은 ESP를 비교했기 때문에 다음 분기문에서 분기가 일어난다. 이동하게 되면 바로 다시 한 번 분기가 일어난다. 이 주소가 OEP로 추정된다. 이제 Ollydump를 통해 dump 해준다. 이번엔 Rebuild Import를 체크 해제 해주고 dump 해준다. 끝.

Lena Reversing tutorial 20_6 6번째 프로그램은 UnPackMe_NoNamePacker.d.out 이다. Ollydbg로 열어준다. 실행을 해보면 다음과 같은 이상한 창이 나온다. 아무 문구도 없다.. 이상해서 디버거를 종료시키고 실행해보았다. 아까와는 다른 창이 나온다. 실행중인 디버거를 탐지하는 코드가 내부에 들어있는 것으로 보인다. 따라서 이번 프로그램은 안티 디버깅 기법을 우회하고 언패킹도 해주어야 한다. 쭉 진행하다보면 다음과 같이 IsDebuggerPresent 함수가 Call 된다. 이 함수를 통해 디버거가 실행중인지 판단하여 분기하는 것으로 보인다. 여기서 OR EAX, EAX 수행 전 EAX는 1이다. 디버거가 실행중임을 나타낸다. 이 값을 0으로 바꾸어 진행해준다...

Lena Reversing tutorial 20_5 5번째 프로그램은 UnPackMe_NsPack3.5 이다. 프로그램을 Ollydbg로 열어준다. 이번엔 시작부분이 PUSHFD, PUSHAD로 시작한다. 따라서 언패킹 루틴이 끝날때는 POPAD 명령어가 나올것이다. control + f를 눌러 검색을 해준다. POPAD 또는 POPFD 를 검색해준다. 여러개가 검색되기 때문에 control + l 을 눌러주면서 하나하나 확인해준다. POPAD, POPFD 가 나온후 해당 프로그램의 .text 범위 내의 주소로 분기해야한다. 다음과 같이 찾을 수 있다. 004271B0로 분기하고 있고 이 주소가 OEP로 생각할 수 있다. 이번에도 Rebuild Import는 체크하고 dump 해준다. 끝.