아인스트라세의 SW 블로그

워게임 사이트란?

유입 로그를 보니, 게임 사이트로 검색해서 들어오는 분들이 많아서 워게임 사이트가 무엇인지 간략하게 설명을 하고 지나가도록 하겠습니다.

워게임은 일반적인 오락 종류인 게임이 아닌, 해킹 연습 문제를 풀 수있는 그러한 플랫폼이라고 생각하시면 됩니다.

따라서 지금 소개하려는 워게임 사이트인 root-me.org라는 사이트도, 기본적인 해킹 기술들을 연습할 수 있는 사이트라고 보시면 됩니다. 

해킹에 입문하고자 하는 학생 및 일반인 등이라면 이 글을 관심을 갖고 읽어보시면 좋을 듯 합니다.

root-me.org

최근 루비야님 블로그를 보다가 보니, 웹 해킹 테크트리라는 글을 보게 되었다.

https://blog.rubiya.kr/index.php/2019/07/26/webhacking-techtree/

그 글에서 root-me.org라는 워게임 사이트에서 Web-Server 카테고리의 문제들을 추천하는 내용을 보고 해당 사이트에 한번 접속해 보았다.

생각보다 사이트는 깔끔한 디자인을 하고 있었다.

그런데 언어가 영어가 아닌 것 같으니, 우측 상단에 국기 같은 부분에 마우스를 올려서 영국 국기를 클릭해서 영어로 언어를 변경해주자.

현재는 불어로 되어 있는 것 같다. 가장 좌측의 영국 국기를 눌러서 영어로 바꾸자.

메인화면에 있는 회원가입 폼에 값을 입력해서 회원가입을 하면 된다. naver 이메일을 쓰니 이유는 모르겠지만, 인증 메일이 오지 않아서 gmail 계정을 입력했다.

Account Type은 하단에 나와있긴한데, 무료계정인 Visitor access로 일단 한번 가입해보도록 하였다.

로그인 한 뒤 화면인데, 좌측 메뉴에서 Challenge - Web - Server를 눌러보자.

61개의 챌린지가 있다고 하는데, 해당 워게임 사이트에 온 김에 가장 쉬운 문제 하나만 풀고 글을 마무리 해보려고 한다.

HTML - Source Code 문제로 들어가보자.

5점짜리 문제이고, Validations가 48%로 꽤나 높다. 아마 문제를 풀려고 시도한 사람 수 대비 푼 사람 수에 해당하는 값이지 싶다.

Start the challenge를 눌러보자.

------------------ 솔루션은 공유하면 안된다고 해서 문제 풀이 부분은 내용을 제거하였다. ----------------------------

패스워드를 구한 뒤 입력하면 저렇게 점수를 얻을 수 있다.

문제가 해결되었다 ㅎㅎ

나중에 시간 나면 다른 문제들도 다 풀어봐야 겠다.

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

한국정보올림피아드 2007년도 초등부 3번문제이자 백준 2539번 문제 "모자이크"문제 풀이입니다.

2007년도때 초등부 문제는 3문제만 나왔네요. 마지막 문제 3번 문제입니다.

문제 분석

2차원 행렬칸에 구멍이 난 녀석이 있고, 정사각형 색종이로 이들을 모두 가려야 합니다.

정사각형 색종이의 개수는 정해져 있고, 겹쳐서 덮어도 됩니다. 정사각형 색종이의 최소 크기를 구하는 문제입니다.

뭔가 나름 어려운 문제 일 수도 있는데, 한 가지 조건 덕에 난이도가 꽤 낮아진 감이 있습니다.

바로 "모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다." 라는 조건이죠. 밑 변에 맞추어서 붙여야 한다는 조건이 있습니다.

행과 열 개수는 100만 미만이라고 하니, 이들을 모두 2차원 배열로 잡기는 조금 무리가 있어 보입니다.

알고리즘 구상

일단 모든 색종이는 도화지의 밑변에 맞추어 붙어야 한다는 조건 때문에, 구멍이 난녀석의 y좌표가 가장 높은 녀석을 커버할 수 있어야 합니다.

따라서 색종이의 크기 최소값은, 가장 큰 y좌표 값 보다는 같거나 커야 합니다.

그리고 모든 점을 덮을 최소 색종이 크기를 알아내야하는데, 이는 파라메트릭 서치로 풀 수 있습니다.

문제를 다음과 같이 환원합니다.

//(f(x)//) => 색종이 크기가 x일 때 주어진 개수의 색종이로 모든 점을 덮을 수 있는가?

만약 크기가 x일때 모두 덮을 수 있다면, 당연히 x+1의 크기로도 덮을 수 있겠지요.

만약 y크기로 덮을 수 없다면, y-1의 크기로도 덮을 수 없습니다.

이러한 성질을 이용하여 파라메트릭 서치(바이너리 서치)로 풀 수 있습니다.

//(f(x)//)는 그리디하게 구할 수 있습니다.

구멍의 x좌표들만 모아놓은 상태에서, 처음 만나는 점을 색종이의 가장 왼쪽 변에 맞게 놓는다고 치고,

지금 놓여진 색종이의 오른쪽 변을 넘어가면 새로운 색종이를 덮는 식으로, 총 색종이가 몇 장 필요한지 알아내서

주어진 색종이 개수로 덮을 수 있는지를 확인하면 됩니다.

따라서 //(f(x)//)는 //(O(N)//)만에 구할 수 있고, 여기서 //(N//)는 잘못 칠해진 색종이 칸의 개수이므로 1000이 됩니다.

계산량은 총 //(1000 * lg1000000//)이므로, 쉽게 구할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
vector<int> arr;
int need(int width) {
	// 색종이 폭이 width일때, 다 덮기 위해 필요한 종이의 수
	int prev = -1;
	int ret = 0;
	for (int pos : arr) {
		if (prev == -1) {
			//처음 종이를 놓는 경우, [prev, prev+width) 까지 커버 가능
			prev = pos;
			ret++;
		}
		else if (prev + width <= pos) {
			prev = pos;
			ret++;
		}
	}
	return ret;
}
int main() {
	int row, col, num_paper, num_hole;
	int max_height = 0;
	cin >> row >> col >> num_paper >> num_hole;
	for (int i = 0; i < num_hole; i++) {
		int x, y; //행, 열
		cin >> x >> y;
		max_height = max(max_height, x);
		arr.push_back(y);
	}
	sort(arr.begin(), arr.end());
	int l = max_height;
	int r = 1000000; //range = [l, r]
	while (l < r) {
		int m = (l + r) / 2;
		if (need(m) <= num_paper) {
			//가능한 경우
			r = m;
		}
		else {
			l = m + 1;
		}
	}
	cout << l << endl;
	return 0;
}

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

한국정보올림피아드 초등부 2007년도 전국본선 1번문제이자 백준 1713번 문제 "후보 추천하기" 문제 풀이입니다.

문제 개요

정올 초등부 1번문제 치고는 solved.ac 티어가 골드5 로 높은 편입니다.

문제 내용을 보면, 약간 특이한 룰을 따라서 코딩을 해야 합니다. 시뮬레이션 종류의 문제로 볼 수 있습니다.

LRU Cache 구현하는 것 같은 느낌이고, 사진 틀에 학생 사진을 넣고 빼는 것을 잘 시뮬레이션 해야 합니다.

특히나 중요한 부분은 사진 틀이 꽉 찼을 때 어떤 녀석을 빼느냐에 관한 문제인 것 같은데, 사진 틀의 개수가 최대 20개 밖에 되지 않으니, 뺄 녀석을 그때 그때 모든 사진 틀을 다 순회하면서 체크하면 될 것 같습니다.

총 추천회수는 1000이니, 최악의 경우 계산량은 //(1000*20//)으로 2만 정도가 됩니다.

시간복잡도는 크게 문제가 되지는 않을 것 같습니다.

사진 틀에서 삭제되는 경우, 추천 수가 0이 되는 것은 사진틀에서 뺀 경우 추천 수를 트래킹 하지 않으면 되므로 구현을 더 간단하게 해 줍니다.

구현전략

사진틀에서 가장 추천 수가 적거나, 추천수가 같다면 더 오래된 녀석을 빼야 한다." 이 조건을 쉽게 하도록 구현을 해야하는데, pair<int, int>를 사용하면 편할 듯 합니다.

C++ STL에 있는 pair은 비교 연산자가 기본적으로 first끼리 비교하고, first가 같다면 second끼리 비교하는 탬플릿 구조체입니다.

template class<T1, T2>
class pair {
	T1 first;
    T2 second;
    bool operator<(const class pair& rhs) const {
    	if (first != rhs.first) {
        	return first < rhs.first;
        }
        return second < rhs.second;
    };
    bool operator>(const class pair& rhs) const {
    	if (first != rhs.first) {
        	return first > rhs.first;
        }
        return second > rhs.second;
    }
};

대략 위와 같은 형태라고 보시면 됩니다.

따라서 first에 투표 수, second에 추가한 시기를 넣으면, pair값이 최소인녀석을 제거하면 되는 형식입니다.

코드

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
map<int, pii> slot; //pii.first = vote , pii.second = age

int main() {
	int n, k;
	int cnt = 0;
	cin >> n >> k;
	for (int i = 1; i <= k; i++) {
		int tmp;
		cin >> tmp;
		(void)0;
		if (slot.find(tmp) == slot.end()) {
			//기존에 없는 경우
			if (slot.size() < n) {
				slot[tmp].first = 1;
				slot[tmp].second = i;
			}
			else {
				//기존거 지우고
				int victim = slot.begin()->first;
				pii value = slot.begin()->second;
				for (auto a : slot) {
					if (a.second < value) {
						value = a.second;
						victim = a.first;
					}
				}
				slot.erase(victim);
				slot[tmp].first = 1;
				slot[tmp].second = i;
			}
		}
		else {
			//있는 경우 투표만 추가시킨다.
			slot[tmp].first = slot[tmp].first + 1;
		}
	}
	for (auto it : slot) {
		printf("%d ", it.first);
	}
	return 0;
}