※ 작년에 작성한 라이트업입니다. ※ 

Basic RCE L04이 프로그램은 디버거 프로그램을 탐지하는 기능을 갖고 있다. 디버거를 탐지하는 함수의 이름은 무엇인가?

1.     04.exe 파일을 올리 디버거로 열고 f8을 누르다 보면 어느 순간부터 ‘디버깅 당함’이라고 뜨는 것을 볼 수 있다.

2.     오른쪽마우스-Search for-All intermodular calls를 클릭해서 함수를 확인하면 아래 이미지와 같은 결과가 나온다. 이 함수들 중에서 디버거를 탐지하는 함수는 IsDebuggerPresent이다.

※ 작년에 작성한 라이트업입니다. ※ 

Basic RCE L03 비주얼 베이직에서 스트링 비교함수 이름은? 

1. 올리 디버거에서는 03.exe 파일이 열리지 않으니 HxD를 통해서 파일을 연다.

2. Decoded text를 읽다 보면 여러 함수 이름들이 나오는 부분이 있다. 이 중에서 스트링 비교함수의 이름은 vbaStrCmp이다.

※ 작년에 작성한 라이트업입니다. ※ 

1. 02.exe.파일을 올리 디버거로 열어보지만 열리지가 않는다.

2. HxD는 손상된 파일도 열 수 있는 디버거다. HxD를 사용하니 파일이 열리는 것을 확인할 수 있다.

3. Decoded text를 읽어보면 패스워드를 확인할 수 있다. JK3FJZh가 패스워드가 된다.

 HxD 프로그램을 통해서 실행이 되지 않는 파일도 읽을 수 있다. 

※ 작년에 작성한 라이트업입니다. ※ 

1. 01.exe 파일을 올리 디버거로 연다.

2. F8로 하나씩 실행해보면서 확인한다.

3. EAX와 ESI를 비교해서 같을 경우 0040103D로 점프를 하도록 되어 있다.

4. 그대로 실행을 할 경우 EAX의 값과 ESI의 값이 동일하지 않기 때문에 점프를 하지 않고 넘어가 “Nah.. This is not a CD-ROM Drive!” 라는 에러 메시지를 띄운다. 메시지를 띄우지 않도록 하기 위해서는 점프 명령이 실행되어 에러 메시지를 건너 뛰고 바로 성공 메시지를 띄우는 부분으로 넘어가야 한다.

5. JE를 JNE로 바꿔서 일치할 경우가 아니라 일치하지 않을 경우에 점프를 하도록 한다.

6.      오류 메시지 대신 “Oh, I really think that your HD is a CD-ROM :P”라고 뜨는 것을 확인할 수 있다.

 cmp는 sub 연산을 통해 비교하는 명령이다. 이는 sub 명령과 동일하지만 오퍼랜드에 영향을 미치지 않는다.

 이때, ZF는 제로 플래그로 연산의 결과가 0과 같을 경우 설정되고, 그 외에는 0 값을 가진다. CF는 캐리 플래그로 연산의 결과가 대상 오퍼랜드에 너무 크거나 작을 경우 설정되며 그 외에는 0이다. 

 또한 jz와 jnz 명령은 ZF 플래그의 값에 따라 결정된다. jz는 ZF가 1일 경우, jnz는 ZF가 0일 경우 점프 명령이 실행된다. 따라서 코드를 바꾸지 않고 ZF의 값을 변경해도 문제가 풀린다. 

 이렇게 ZF 플래그의 값을 조정하는 방법도 있고, JE 명령이 실행되도록 하여 파일이 정상적으로 실행되게 할 수도 있다. cmp EAX, EAX 등 항상 참으로 나오도록 해도 문제가 풀린다. 

https://www.acmicpc.net/problem/10451

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해

로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 20001;

int N, M; // N: 정점의 개수, M: 간선
vector<int> adj[MAX]; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

int ans = 0;

void dfs(int node) {
	if(visited[node] == 1) ans++;

	visited[node] = 1;

	for(int i = 0; i < adj[node].size(); i++) {
		int next = adj[node][i];
		if(visited[next] == 0) dfs(next);
	}
}

int main(void) {
	int k;
	cin>>k;

	for(int i = 0; i < k; i++) {
		cin>>N;

		for(int j = 1; j <= N; j++) { // 인접행렬 (j, M) (M, j)
			cin>>M;
			adj[j].push_back(M);
			adj[M].push_back(j);
		} 

		for(int j = 1; j <= N; j++)
			if(visited[j] == 0) {
				visited[j] = 1;
				dfs(j);
			}


		cout<<ans<<'\n';

		// 인접 행렬, 방문 노드, ans 초기화
		for(int j = 0; j <= N; j++) {
			adj[j].clear();
			visited[j] = 0;
			ans = 0;
		}
	}
}

https://www.acmicpc.net/problem/1707

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 20001;

int N, M; // N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점
vector<int> adj[MAX]; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:r그룹1, -1:그룹2)

void dfs(int node, int set) {
	visited[node] = set;

	for(int i = 0; i < adj[node].size(); i++) {
		int next = adj[node][i];
		if(visited[next] == 0) dfs(next, -set);
	}
}

bool bipartite() {
	for(int i = 0; i < N; i++)
		for(int j = 0; j < adj[i].size(); j++) {
			int next = adj[i][j];
			// 정점 i와 j가 연결되어 있고 둘의 그룹이 같을 경우 이분그래프가 아님
			if(visited[i] == visited[next]) return false;
		}

	return true;
}

int main(void) {
	int k;
	cin>>k;

	for(int i = 0; i < k; i++) {
		cin>>N>>M;

		int x, y; // 인접 행렬 좌표
		for(int j = 0; j < M; j++) {
			cin>>x>>y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		} 

		for(int j = 0; j <= N; j++)
			if(visited[j] == 0) {
				visited[j] = 1;
				dfs(j, 1);
			}


		if(bipartite()) cout<<"YES\n";
		else cout<<"NO\n";

		// 인접 행렬, 방문 노드 초기화
		for(int j = 0; j <= N; j++) {
			adj[j].clear();
			visited[j] = 0;
		}
	}
}