Ubuntu 16.04 상에서 세팅하는 과정이다.

DB 및 AWS를 운영하는 메인 서버 한 대와, 하위 서버 여러 대로 이루어진 구성이다.
일반적으로는 워커(Worker)를 담당할 채점기 컴퓨터를 따로 두는 편이다. 각각의 채점기 컴퓨터에서는 워커 서비스를 세 개 정도(코어 갯수 - 1) 켜서 사용한다.

또, 참가자(contestant)가 굉장히 많은 경우, 참가자에게 홈페이지를 그려주는 contest web server(CWS) 서버 역시 분리할 필요가 생기기도 한다.
그 경우에도 마찬가지로 CWS를 담당하는 컴퓨터를 따로 둔다.

또, 랭킹을 표시하는 ranking web server(RWS)를 따로, 그리고 여러 개 둘 필요가 생기기도 한다. 채점 및 점수 매기기가 완료될 때마다 모든 RWS 쪽으로 채점 결과를 전송하게 된다.

이외의 서비스, 즉 Postgres DB 서버를 운영하고, 관리자용 admin web server(AWS)를 운영하고, 채점 및 점수 매기는 과정(evaluation service, scoring service)을 총괄하고, 로그를 남기고, 프린팅 등을 처리하는 모든 과정은 하나의 컴퓨터에서 처리할 만 하다.


1.

모든 컴퓨터에서, 필요한 패키지를 설치한다.

sudo apt-get install build-essential openjdk-8-jre openjdk-8-jdk fpc \
    postgresql postgresql-client gettext python2.7 \
    iso-codes shared-mime-info stl-manual cgroup-lite libcap-dev

sudo apt-get install python-dev libpq-dev libcups2-dev libyaml-dev \
libffi-dev python-pip


2.

모든 컴퓨터에서, CMS를 가져오고 prerequisites의 설치를 진행한다.

myungwoo/cms를 가져온다고 하면

<메인 서버>

git clone --single-branch -b koi-cms --recursive https://github.com/myungwoo/cms
cd cms
sudo ./prerequisites.py install

그리고 여전히 메인 서버에서, 모든 하위 서버들의 IP에 대해서 scp로 CMS 폴더를 통째로 보내준다. (git clone보다 빠르기 때문에)

scp ../cms $ip:~/cms -r

이제 각각의 하위 서버에서도 설치를 실행해준다.

<하위 서버>

cd cms
sudo ./prerequisites.py install


3.

모든 서버에서, 파이썬 virtual env를 만들고 CMS의 install을 진행한다.

virtualenv -p python2 ~/venv
source ~/venv/bin/activate
pip install -r requirements.txt
python setup.py install


4.

메인 서버에서, postgres DB를 세팅한다.

<메인 서버>

sudo su - postgres
createuser --username=postgres --pwprompt cmsuser

위의 커맨드에서, DB 접속 비밀번호를 입력한다.

<메인 서버>

createdb --username=postgres --owner=cmsuser cmsdb
psql --username=postgres --dbname=cmsdb --command='ALTER SCHEMA public OWNER TO cmsuser'
psql --username=postgres --dbname=cmsdb --command='GRANT SELECT ON pg_largeobject TO cmsuser'
cmsInitDB

또, Worker나 CWS 등이 이 Postgres에 접속할 수 있어야 하기 때문에, postgres 설정을 바꿔주어야 한다.

<메인 서버>

sudo vim /etc/postgresql/9.5/main/postgresql.conf

59번줄?에, listen_addresses = '127.0.0.1,192.168.0.x'와 같은 부분을, 하위 서버들의 IP 주소로 채운다.
또 HBA 관련 설정을 채워야 한다.

sudo vim /etc/postgresql/9.5/main/pg_hba.conf

모든 하위 서버에 대해서, host cmsdb cmsuser <하위 서버의 IP 주소>/32 md5 와 같은 식으로 한 줄씩 추가해준다.


5.

모든 서버에서, 설정 파일을 수정한다. 이 역시 메인 서버에서 수정하고 그를 scp로 deploy 하는게 편하다.

<메인 서버>

cp config/cms.conf.sample config/cms.conf
vim cms.conf

세팅해야 할 것

5-1. 20-32번줄의 각 서비스의 IP 주소를 설정한다.
Worker(, 그리고 CWS도 분리한다면 CWS)를 제외한 모든 서비스의 IP 주소는 메인 서버의 IP 주소로 설정한다.
포트는 대부분 그대로 쓰되, 한 컴퓨터에서 워커를 여러 대 켜는 경우 각 워커의 포트는 다르게 설정한다.

5-2. DB 접속 스트링 (45번줄)
"database": "postgresql+psycopg2://cmsuser:your_password_here@localhost/cmsdb 라고 되어 있는데,
"database": "postgresql+psycopg2://cmsuser:<4번에서 설정한 비밀번호>@<메인 서버의 IP주소>/cmsdb 가 되도록 바꾼다.

5-3. 81번줄 secret_key
랜덤한 16 bytes hexademical 스트링(즉, 32글자)으로 바꿔 주어야 한다.
다음 커맨드의 결과를 붙여넣자:
python -c "import random;print('%032x'%random.randrange(1<<128))"

5-#. 145번줄 rankings
RWS를 쓸 경우에만 설정한다.
"rankings": ["http://usern4me:passw0rd@localhost:8890/"]
RWS를 호스팅할 서버 주소와 포트를 넣고, 랭킹 서비스에서만 쓸 ID와 비밀번호로 채운다.
이 아이디와 비밀번호는, 대회 서버가 랭킹 서버에게 채점 결과를 전송하는 과정에서의 보안을 담당한다.
여기서, 만약 RWS 앞에 nginx를 놓을 계획이라고 하더라도, 여기에는 백엔드 역할의 서버의 주소와 포트를 넣어야 한다.

5-#. cms.ranking.conf

RWS를 쓸 경우에만 설정한다.

위에서 설정한 랭킹 서비스 전용 아이디와 비밀번호를 채워 넣는다.



수정을 마쳤으면 scp로 각 유저의 ~/cms/config/ 안에 복사해주고,

※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
※ cms.conf 등을 수정하고 나면, 꼭 다음 커맨드를 써야 반영된다!!!
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※

sudo ./prerequisites.py install


6.
관리자 계정을 만들고, AWS를 켜서 로그인한다.

관리자 계정에 로그인 할 수 있으면 절대 안 된다는 생각으로, 아이디와 비밀번호를 꼭 정성들여서 만들도록 하자.

<메인 컴퓨터>

cmsAddAdmin -p <패스워드> <아이디>
cmsAdminWebServer 0

AWS에서 컨테스트를 만들어주어야 한다. 그래야 cmsResourceService를 켤 수 있다.


7.
모든 컴퓨터에서 cmsResourceService를 켠다.
Resource Service만 켜면, 그 아이가 각자의 컴퓨터에서 켜야 하는 서비스를 모두 켜 줄 것이다.

cmsResourceService -a <컨테스트 번호>

이제 모든 setup이 끝났다.



번외 1.

nginx 프론트엔드를 세우려면, 먼저 nginx를 설치한다.
그리고 /etc/nginx/sites-enabled/default 의 내용을 싹 지우고, 채워준다.

HTTP 서버만 세우는 건 간단하다.
nginx 설정을 아래와 같이 해준다.

upstream cws {
    ip_hash;
    keepalive 500;
    server :<포트(보통 8888)>;
    server :<포트(보통 8888)>;
# ...
}
upstream aws {
    keepalive 5;
    server :<포트(보통 8889)>;
}
# rws를 안 쓰면 아래 줄은 필요 없다.
upstream rws {
    keepalive 500;
    server :<포트(보통 8890)>;
    server :<포트(보통 8890)>;
# ...
}
server {
    listen 80 default_server;
    server_name <서버 주소>; # cms.asdfzxcv.com, ioi, 혹은 192.168.0.200 등
    location ^~ /aws/ {
        proxy_pass http://aws/;
        include proxy_params;

        proxy_redirect http://$host/ /aws/;
        proxy_redirect https://$host/ /aws/;
        proxy_http_version 1.1;
        proxy_set_header Connection "";
        client_max_body_size 100M;
    }
# rws를 안 쓰면 아래 줄은 필요 없다.
location ^~ /rws/ { proxy_pass http://rws/; include proxy_params; proxy_redirect http://$host/ /rws/; proxy_redirect https://$host/ /rws/; proxy_http_version 1.1; proxy_set_header Connection ""; proxy_buffering off; } location / { proxy_pass http://cws/; include proxy_params; proxy_http_version 1.1; proxy_set_header Connection ""; client_max_body_size 50M; } }


그리고 cms.conf 에서 num_proxies 를 찾아서 1로 만들어주어야 하고,

그 다음에는 또다시 sudo ./prerequisites.py install 을 돌려주어야 한다!!!!

꼭 까먹지 말자.



그리고 방화벽을 세운다.

sudo ufw allow 80
sudo ufw allow 5432
sudo ufw enable

HTTPS를 사용하고 싶다면, 80번을 443번으로 넘겨주는 server{}를 하나 만들고, self-signed certificate를 지정해준 후,
모든 참가자(contestant) 컴퓨터에 해당 CA를 신뢰할 수 있는 인증서로 배포해야 한다.


번외 2. 각종 커맨드 목록

cmsAddAdmin [-p PASSWORD] username
cmsAddParticipation [-c CONTEST_ID] [-i IP] [-d DELAY_TIME] [-e EXTRA_TIME] [-t TEAM] [--hidden] [--unrestricted] [-p PLAINTEXT_PASSWORD | -H HASHED_PASSWORD] [--bcrypt] uesrname
cmsAddUser [-t TIMEZONE] [-l LANGUAGES: comma-separated] [-p PLAINTEXT_PASSWORD | -H HASHED_PASSWORD] [--bcrypt] first_name last_name username
cmsRemoveContest [-c CONTEST_ID]
cmsRemoveParticipation [-c CONTEST_ID] username
cmsRemoveSubmissions [-c CONTEST_ID] [-u USERNAME] [-t TASK_NAME] [-s SUBMISSION_ID]
cmsRemoveTask task_name
cmsRemoveUser username


번외 3. 컴퓨터 환경 세팅

# 유저 추가하기

useradd=저수준이라고 까임
adduser 를 쓰자!

adduser [--home DIR] [--shell SHELL] [--no-create-home] user


# IP 칠 필요 없게 만들기

/etc/hosts에 IP주소와 대명사를 순서대로  한 줄에 띄어쓰기로 구분해서 써주면 된다.
127.0.0.1 대신 localhost를 쓸 수 있는 것도 이 파일 덕분이라고 생각하면 된다.


# 브라우저 홈 페이지 설정

Firefox 홈 페이지 설정 (모든 Firefox를 종료시킨 후에 하자!)

/usr/lib/firefox/mozilla.cfg 에 다음 내용: (첫 줄에 //가 꼭 필요하단다)

//
defaultPref("browser.startup.homepage", "data:text/plain,browser.startup.homepage=http://ioi")
pref("browser.startup.homepage", "http://ioi")

/usr/lib/firefox/defaults/pref/local-settings.js 에 다음 내용:

pref("general.config.obscure_value", 0);
pref("general.config.filename", "mozilla.cfg");

obscure value를 설정하지 않거나 디폴트 값 13으로 두면, mozilla.cfg를 ROT13 해서 읽으려고 하기 때문에 꼭 써주어야 한다.


Chrome 홈 페이지 설정

/opt/google/chrome/master_preferences 에 다음 내용:

{
"homepage": "http://ioi",
"homepage_is_newtabpage": false,
"browser": {
"show_home_button": true
},
"session": {
"restore_on_startup": 4,
"startup_urls": [
"http://ioi"
]
},
"bookmark_bar": {
"show_on_all_tabs": true
},
"sync_promo": {
"show_on_first_run_allowed": false
},
"distribution": {
"import_bookmarks": false,
"import_history": false,
"import_home_page": false,
"import_search_engine": false,
"ping_delay": 60,
"suppress_first_run_bubble": true,
"do_not_create_desktop_shortcut": true,
"do_not_create_quick_launch_shortcut": true,
"do_not_launch_chrome": true,
"do_not_register_for_update_launch": true,
"make_chrome_default": false,
"make_chrome_default_for_user": false,
"suppress_first_run_default_browser_prompt": true,
"system_level": true,
"verbose_logging": true
},
"first_run_tabs": [
"http://ioi"
]
}


얏호

'알고리즘 문제풀기 > 기타' 카테고리의 다른 글

CMS 세팅 (워커 등 분리)  (0) 2018.08.02
Code::Blocks에서의 편한 설정  (0) 2016.01.13

<남남서와 찌끄레기들> 팀으로 참가해, 12문제 중 10문제를 풀고 전체 4등의 결과를 얻었다. 팀 연습을 안 해봤어서 걱정했는데 좋은 결과가 나와서 다행이었다.

대회 준비에 부족한 부분이 있긴 했지만 내가 준비해도 저런 문제가 안 생겼을 거라고는 장담 못 할 것 같다... 주최 분들이 정말 수고하신게 보였다.

내가 푼 문제는 E, K, I였다. 각각 내 풀이를 써본다.


E

배열을 one-based로 사용해 min-heap을 만든다. ($i$번째 노드의 부모가 $\lfloor i/2 \rfloor$가 되는 식으로)
이 때, $1$부터 $N$까지의 수를 어떤 특정 순서로 힙에 삽입해서,
모든 작업이 끝났을 때 $p$번째 위치에 $k$가 적혀 있도록 하는 방법을 아무거나 하나 출력하는 문제이다.

처음에는 방법의 수를 세는 것으로 잘못 읽고는 엄청 어려운 문제라고 생각하고 넘겼는데,
사람들이 많이 풀길래... 현수에게 설명해주면서 보니까 방법을 아무거나 하나 출력하는 문제였고, 그러면 어렵지 않아 보였다.
초반 스퍼트가 끝나가는 타이밍이기도 했고, 급한 마음에 두 번 실수를 거친 끝에 맞았다.


$p$번째 위치 밑($p$번째 위치의 subtree)에는 모두 $k$보다 큰 수가 있어야 하며,
$p$번째 위치 위($p$번째 위치의 조상들)에는 모두 $k$보다 작은 수가 있어야 한다.
양쪽 다 갯수가 맞으면(그만큼 채울 수 있다면) 그런 숫자들로 적당히 채우면 된다.

E 코드 (열기)


K

자연수 $n$과 $m$, 그리고 자연수 수열 $A_i$가 주어졌을 때, 다음 식을 만족하는 자연수 수열 $B_i$를 구하는 문제이다.

$$1+\frac{2^m-1}{n}=\frac{(A_1+B_1)(A_2+B_2)\dots (A_m+B_m)}{B_1 B_2 \dots B_m}$$

너무 하드한 수학문제 같은 인상이라, 처음에는 별로 안 잡으려고 했다.
11분만에 풀어 퍼스트 솔브를 가져간 더민당 팀도 수학을 잘 하는 분이 계시다고 들어서 그런가보다 했었다.
그런데 생각보다 푸는 팀들이 나오고, 내가 맡던 문제들을 다 팀원들한테 준 상태였기 때문에, 이 문제에 대해서 좀 더 고민을 했었다.


먼저 신경쓰인 건, 우변이 $m$개의 값으로 되어 있는데, 좌변에 $2^m-1$이 있는 것이다.
우변을 정리하면 $\left(1+A_i/B_i\right)$들의 곱이기 때문에, 이 항이 하나하나 붙어나가면서 좌변의 값도 만들어나갈 수 있지 않을까 싶었다.

$$\begin{cases}\displaystyle 1+\frac{2^1-1}{n}=\left(1+\frac{A_1}{B_1}\right)? \\ \displaystyle 1+\frac{2^2-1}{n}=\left(1+\frac{A_1}{B_1}\right)\left(1+\frac{A_2}{B_2}\right)? \\ \vdots \\ \displaystyle 1+\frac{2^m-1}{n}=\left(1+\frac{A_1}{B_1}\right)\left(1+\frac{A_2}{B_2}\right)\left(1+\frac{A_3}{B_3}\right) \cdots \left(1+\frac{A_m}{B_m}\right)?\end{cases}$$

그럼 원하는 대로 되기 위해서는 이렇게 되어야 할 것이다...

$$\frac{\displaystyle 1+\frac{2^i-1}{n}}{\displaystyle 1+\frac{2^{i-1}-1}{n}} = 1+\frac{A_i}{B_i}?$$

그런데 이게 좀처럼 예쁘게 풀리지 않았다. $A_i=2^k$ 꼴일 때만 적당한 $B_i$가 존재하게 된다. 그런데 예제를 보면 그렇지 않더라도 멀쩡히 풀고 있었다.

그래서 새로운 시도를 해 봤다. 좌변을 약간 다르게 바꿔보니까...

$$\frac{\displaystyle 1+\frac{2^i-1}{n}}{\displaystyle 1+\frac{2^{i-1}-1}{n/2}} = 1+\frac{A_i}{B_i}$$

만약 이런 식으로 된다면... $n$을 점차 키워나가며 (만들어나가며) 풀 수 있어 보인다.

$$ \frac{n+2^i-1}{n+2^i-2}=1+\frac{A_i}{B_i} \\ \therefore B_i = (n+2^i-2)A_i $$

식이 엄청 간단하게 나왔다. $B_i = (n+2^i-2)A_i $라면 문제의 조건도 만족한다.

그런데.. $n$이 항상 짝수인 것도 아니고. 홀수면 어떻게 되지?
예제 입력 2를 보았다. $n=10$, $m=3$이며,

$$1+\frac{2^1-1}{3} = \left(1+\frac{1}{3}\right) \\ 1+\frac{2^2-1}{5} = \left(1+\frac{1}{3}\right)\left(1+\frac{1}{5}\right) \\ 1+\frac{2^3-1}{10} = \left(1+\frac{1}{3}\right)\left(1+\frac{1}{5}\right)\left(1+\frac{1}{16}\right)$$

좌변에서 $n$이 5에서 10으로 갈 때는 $n+2^3-2=16$이므로 $\left(1+\frac{1}{16}\right)$을 곱해주는 부분이 우리 생각과 꼭 들어맞는 부분인데, 3에서 5로 가는 부분이... 뭔가 신기하다. 뭐지??

뭔가 그럴듯하게 계산을 해보니

$$\frac{\displaystyle 1+\frac{2^m-1}{2n-1}}{\displaystyle 1+\frac{2^{m-1}-1}{n}} = \frac{n}{2n-1} \frac{\displaystyle 2n-1+2^m-1}{\displaystyle n+2^{m-1}-1} = \frac{n}{2n-1} \frac{\displaystyle 2\left(n+2^{m-1}-1 \right)}{n+2^{m-1}-1}=\frac{2n}{2n-1}=1+\frac{1}{2n-1}$$

!!!!!
이렇게 간단하게 정리되는 것이다.
따라서 $n$이 홀수가 될 때는 $B_i = nA_i$를 잡으면 된다.

즉... $n$이 짝수일 때는 $(n/2) \rightarrow n$으로 온 것으로 생각해 $B_i$를 하나 잡아주면, 항이 하나 줄면서 $n$이 절반이 되고,
$n$이 홀수일 때는 $(n+1)/2 \rightarrow n$으로 온 것으로 생각해 $B_i$를 하나 잡아주면, 항이 하나 줄면서 $n$이 거의 절반이 되므로
대충 해결할 수 있...어 보이고,

$m \leq 50$이므로, $m$이 충분히 크다면야 $n$이 무조건 1로 가겠지만, $m$이 너무 작으면 $n$이 1로 가기 전에 쓸 수 있는 $1+\frac{A_i}{B_i}$ 항이 하나 줄지 않나? 싶을 수 있는데,
$m=1$일 때는 그 때의 $n$에 대해서 $B_i=nA_i$를 잡아주면 무조건 $1+\frac{1}{n}=1+\frac{2^1-1}{n}$이 되므로 그 때만 이렇게 처리해주면 된다.

K 코드 (열기)


I

어떤 규칙에 맞게 $N\times N$ 격자를 0 혹은 1로 채운다. 그 조건은...
$a_{ij} + a_{(i+1)j} + a_{i(j+1)} + a_{(i+1)(j+1)} \equiv c_{ij}\text{ mod 2}$ 를 만족해야 한다. $(1\leq i,j \leq N-1)$
즉 모든 2×2 격자에 대해서, 그 격자의 합 mod 2가 되어야 할 값이 정해져 있는 것이다.

여기에, 특정 위치는 반드시 1이라거나, 특정 위치는 반드시 0이라거나 하는 조건들이 여러 개 들어온다. 그것도 들어왔다가 사라졌다가 한다.
이 때 각 시점마다, 지금 들어와있는 조건을 만족하면서 격자를 채우는 방법이 있는가?를 답하는 문제이다.


일단 저 규칙에 대해 생각해보자.
$i=1\textrm{ or }j=1$인 격자들, 즉 ┌ 모양 테두리 부분의 격자들의 값이 정해지면 안쪽 모든 칸들의 값은 저절로 정해질 것이다.
주어진 규칙에 맞게 채워나가면 되니까.
mod 2의 규칙 때문에, 양변에 항을 더하면
$a_{(i+1)(j+1)} \equiv a_{ij} + a_{(i+1)j} + a_{i(j+1)} + c_{ij}\text{ mod 2}$ 로도 쓸 수 있다.
이 식으로 아직 모르는 값을 채워나갈 수 있는 것이다.

반대로 저 격자들의 값은 "자유 변수"의 느낌이다. 안쪽의 "종속 변수"의 값을 결정하는....
예를 들어 $a_{22} = a_{11} + a_{12} + a_{21} + c_{11}$ 이다.
$a_{33} = a_{11} + a_{31} + a_{13} + c_{22}$ 이다.

뭔가 많이 계산을 해보다 보면, 이런 규칙을 알 수 있다.

$$\large a_{ij} = a_{11} + a_{1j} + a_{i1} + \sum _{x<i \\ y<j} c_{xy} \quad \textrm{ for }i,\: j \geq 2$$

각각의 숫자가 어느 위치의 값들에 합해지는지를 보면 규칙을 증명할 수가 있다.
무슨 말이냐면, 예를 들어 $a_{15}$의 값("자유 변수")이 어느 칸들에 더해지는지 생각해보자.
자기 왼쪽 위의 세 칸을 합해 가져오는 규칙 때문에, $a_{25}$에 더해질 것이고,
그걸 가져온 $a_{35}$에도 더해질 것이고, ... 이렇게 $a_{i5}$에는 모두 더해지지만,
$a_{26}$의 경우에는 $a_{15}$와 $a_{25}$를 둘 다 가져오기 때문에 더해지지 않는다. 즉 $a_{15}$가 더해지는 칸들을 1로 나타내면 이런 모양이다.

$$\begin{array}{lr} \cdots & 0 & 1 & 0 & 0 & \cdots \\ \cdots & 0 & 1 & 0 & 0 & \cdots \\ \cdots & 0 & 1 & 0 & 0 & \cdots \\ \quad & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}$$

이런 식으로 각각의 변수들에 대해서 생각하면 위의 규칙 식을 증명할 수 있다.



그러면 우리가 각 시점에 풀어야 할 문제는, 다음과 같은 식이 여러 개 있을 때 모두 만족하도록 "자유 변수"를 정하는 방법이 있는지의 여부이다.

$$\begin{cases}\displaystyle a_{11} + a_{1j} + a_{i1} + \sum _{x<i \\ y<j} c_{xy} \equiv p \\ \displaystyle a_{i1}=p \\ \displaystyle a_{1j}=p \\ \displaystyle a_{11}=p \end{cases}$$

너무 복잡해 보이는데, 일단 첫 번째 식에서 $\sum _{x<i \\ y<j} c_{xy}$ 부분은 다른 조건이랑도 상관 없고, 처음에 입력받은 테이블에서 계산을 마치기만 하면 그 뒤로는 그냥 상수이기 때문에, 그냥 양변에 미리 더해주고 처음부터 $p$에 포함되는 것으로 생각해도 된다. 다시 정리하면

$$\begin{cases}\displaystyle a_{11} + a_{1j} + a_{i1} \equiv p \\ \displaystyle a_{i1}=p \\ \displaystyle a_{1j}=p \\ \displaystyle a_{11}=p \end{cases}$$

각 행 첫 값인 자유 변수를 $A_i$, 각 열 첫 값인 자유 변수를 $B_j$, (1, 1)의 값을 $f$라고 썼을 때

$$\begin{cases}\displaystyle A_i + B_j + f \equiv p \\ \displaystyle A_i=p \\ \displaystyle B_j=p \\ \displaystyle f=p \end{cases}$$

이 문제를 풀려고 보니, 또 $f$가 방해이다.
$f=0$일 때와 $f=1$일 때 중 어느 한 쪽이라도 조건을 만족하게 값을 채울 수 있다면 그 시점의 답은 1일 것이므로,
그냥 같은 알고리즘을 두 번 수행하기로 하고 $f$에 대한 생각을 지울 수 있다.
혹시 $f$를 강제하는 마지막 조건이 들어온다면, 지금 고려하는 $f$와 다르다면 그 시간에는 무조건 불가능하다고 보면 된다.

이제 다음 문제를 풀면 된다.

$$\begin{cases}\displaystyle A_i + B_j \equiv p \\ \displaystyle A_i=p \\ \displaystyle B_j=p \end{cases}$$

$p$의 값에 따라서 이렇게도 쓸 수 있다.

$$\begin{cases}\displaystyle A_i \equiv B_j \\ \displaystyle A_i \not \equiv B_j \\ \displaystyle A_i=p \\ \displaystyle B_j=p \end{cases}$$


이제, 알고스팟의 EDITORWARS 문제(링크)로 유명한 알고리즘을 생각할 수 있다.
union & find(disjoint set 뭐시기라고도 부른다) 알고리즘에서 한 가지 정보를 더 추가하는데, "자신과 같은 집합이 되어서는 안 되는 아이"이다.
그리고 "A와 B는 같은 집합이다" 연산 외에, "A와 B는 다른 집합이다"라는 연산을 추가하는 것이다.
그럼 놀랍게도 각각의 연산에서 "그것은 모순입니다"가 나올 수도 있게 된다.

그 알고리즘을 쓰면, 위와 같은 조건이 여러 개 있을 때 $A_i$ 및 $B_j$들을 집합 관계로 묶어보고,
거기서 모순이 없다면 조건을 만족하는 채우기가 존재한다는 것으로 볼 수 있으므로 해결 가능하다.
$A_i = p$ 꼴의 조건은... 사실 그 절대적인 값은 혼자만 있을 때는 의미가 없고, $A_i=p$였는데 $B_j=p$라면 $A_i$와 $B_j$가 같은 집합으로 묶여야 한다는 것이 중요하다. 모든 값을 뒤집어도 앞의 두 조건의 참거짓은 변하지 않기 때문에, 서로 같은지 여부, 그 관계만이 중요하다. 때문에 "항상 1"을 나타내는 원소를 하나 더 추가해, 여기에 "같다" 혹은 "다르다" 연산을 적용해서 모순을 따지면 된다.


그런데.. 문제는 여기서 끝나지 않는다. 시간에 따라 들어오고 나가는 조건이 있기 때문이다.
이러고 보니 완전히 풀 수 없는 문제처럼 보였는데, 여기서 조금 더 생각을 발전시키면 할 수 있다.

일단, union & find에서 union을 했던 순서의 역순으로 되돌릴 수 있다는 아이디어가 필요하다.
parent 배열이 매번 갱신되는데, 덮어씌우는 것이 아니라 vector에 push_back을 하는 것이다.
그럼 현재값은 back()이고, 되돌릴 때는 pop_back()을 하면 된다.

두 번째 아이디어는...
시간축 방향으로 세그먼트 트리를 만들어보자.
그럼 각각의 쿼리가 $\log T$개의 노드에 들어갈 것이다.

그리고... 이 세그먼트 트리를 DFS해보자.
각각의 노드에 있는 쿼리를 모두 처리해보고, 모순이 있는지 확인하고...
DFS에서 돌아갈 때는 union & find 결과를 모두 되돌려보자.


이제 문제가 풀렸다.

I 코드 (열기)

시간축 방향으로 세그트리를 만들어서, 작업을 되돌리면서 처리하는 아이디어는 처음 생각해봤고, 그것도 대회 중이었기 때문에, 구현에서 실수를 굉장히 많이 했다.

offline dynamic connectivity로 알려져 있는 아이디어라고 한다. 알려진 아이디어를 스스로 생각해냈다는 점이 많이 뿌듯했다.


'알고리즘 문제풀기 > 대회 참가기' 카테고리의 다른 글

UCPC 2018 후기  (0) 2018.07.30
NYPC 1회 후기  (1) 2016.10.29
Codeforces(618): Wunder Fund Round 2016 후기  (2) 2016.01.30
Codeforces(500): Good Bye 2014 후기  (0) 2014.12.31

$N$개의 숫자가 늘어서 있다.
이중 몇 번째부터 몇 번째까지의 숫자들의 합을 물어보는 질문이 여러 번 주어진다.

이것이 구간의 합 구하기(range sum query) 문제의 가장 기본적인 내용이다.
우리의 목적은 아무 구간이나 잡았을 때 그 합을 빠르게 계산하는 것이다.
그 계산이 빨라야 제한 시간 내에 충분히 여러 번 물어볼 수 있기 때문이다.


단순히 고정된 값들에 대해서 구간의 합을 계산하는 거라면, prefix sum 기법을 먼저 떠올릴 수 있다.

2013/07/29 - [알고리즘 문제풀기/# 기타 주제] - Prefix sum

prefix sum 기법은 고정된 값들에 대해서, $O(N)$ 시간이 드는 전처리(=자료 준비)를 한 번 거치면,
이후 모든 구간에 대한 질문을 $O(1)$에 즉각 처리할 수 있다.



그런데 각 요소가 도중에 변할 수 있다면...?
여기부터는 완전히 새로운 발상이 필요하게 되는데, 그 이유를 알아보자.

prefix sum 기법에서는 첫 번째부터 $i$번째까지의 값의 합을 한 번 구해 놓고, 그 값을 계속 사용하게 되는데,
도중에 만약 $i$번째 위치의 값에 갱신이 필요하다면,
prefix sum 배열에서는 $i$번째, $(i+1)$번째, $(i+2)$번째, ... 이 위치들의 값을 변화시켜 주어야 한다.
$i$번째 위치의 값 가지고 있는 것은 $i$번째 이후의 prefix sum 값들이기 때문이다.

그러면 앞쪽 요소에 갱신이 무지막지하게 많이 들어오면 매번 배열 전체를 돌면서 prefix sum을 갱신해 주어야 한다.
배열의 크기가 $N$일 때, 처음에 $O(N)$의 시간을 소요해서 prefix sum 배열을 만들면
이후 구간의 합 질문을 $O(1)$에 처리할 수 있는게 prefix sum의 장점이었는데,
값 수정을 처리하기 위해서는 최악의 경우 배열 전체를 다 돌아야 하기 때문에 $O(N)$이라고 말할 수 있다.

구간의 합 질문과 특정 위치의 값 수정이 막 섞여서 들어온다면 결국 하나의 질문을 $O(N)$에 처리하게 되는 셈이다.
...그러면 차라리 구간의 합을 구할 때, 해당 구간을 일일이 돌면서 직접 손수 합을 계산하는 것과 차이가 없다.
그것 역시 구간 길이에 비례하는 시간이 들기에 $O(N)$이기 때문이다.

여기서 우리는 "구간의 합 질문과 특정 위치의 값 수정이 막 섞여서 들어올 때"의, 최악의 시간복잡도를 어떻게든 줄이는 것이 목적이다.



위에서 일어난 트레이드오프 trade-off를 고민해보자.

어떤 구간의 합을 미리 계산해서 정리해 놓으면, 궁금한 구간이 있을때 미리 계산한 자료를 이용해 빠르게 답을 구할 수 있다.
이걸 아예 안 한다면, 질문이 들어올 때 질문 구간의 원소 하나하나를 돌면서 합해야 한다.
약간만 한다면..? 예를 들어 인접한 원소 두 개씩의 합 까지만 미리 계산해 놓는다면, 약 (구간의 길이)/2 개의 값을 합하면 된다.
미리 계산해놓은 것이 많으면 많을 수록, 질문에 대답하기 위해 합쳐야 하는 갯수는 줄어드는 것이다.

하지만 그렇게 계산해놓은 구간들이 너무 많고, 별로 좋지 않은 모양을 하고 있으면 갱신할 때 오래 걸릴 수 있다.
핵심은, 한 원소를 갱신을 할 때는 그 원소를 포함하고 있는 모든 구간(prefix sum에서는 $i$번째 이후의 모든 합들)을 갱신해주어야 하고,
그게 너무 많으면 그만큼 오래 걸리는 것이다.

이 두 가지 문제를 정리해보면, 우리에게 필요한 것은 다음과 같다.
1) 임의의 구간에 대한 질문이 들어오더라도, 미리 계산해놓은 자료 몇 개의 합으로 표현할 수 있어야 한다. 그 갯수는 충분히 작아야 한다.
2) 임의의 위치에 대한 수정이 들어오더라도, 미리 계산해놓은 자료 몇 개만 바꿔야 한다. 그 갯수는 충분히 작아야 한다.
이 두 가지 조건을 만족하는 여러 자료구조가 있다.



1. Fenwick tree

2. segment tree

이것들은 별도로 글을 써서 올려야겠다.


3. 버킷 (속어로는 "루트질")

위에서 말했듯이,

인접한 원소 두 개씩의 합 까지만 미리 계산해 놓는다면, 약 (구간의 길이)/2 개의 값을 합하면 된다.
인접한 원소 네 개씩의 합 까지만 미리 계산해 놓는다면, 약 (구간의 길이)/4 개의 값을 합하면 된다.
....
뭐지? 인접하게 여러 개를 묶으면 다 되는 건가?

아니다. 예를 들어 10,000개의 값이 있고, 인접한 1,000개의 합을 미리 계산해 놓았다고 하면,
적당히 큰 구간이 들어왔을 때 많아야 열 개의 값(질문으로 들어온 구간에 완전히 포함되는 덩어리)을 합하면 될 것처럼 보이지만,
거기에 포함되지 않은 양쪽 가장자리도 있기 때문에 최악의 경우에는 999×2 번의 덧셈이 더 필요하다.

$t$개씩 한 덩어리로 묶어서 미리 합을 계산해 놓는다고 했을 때 시간을 계산해보자.
(여기서 각각의 덩어리들이 안 겹치게 잡았다고 하자. 즉 $1$번째부터 $t$번째까지, $(t+1)$번째부터 $2t$번째까지, ... 이런 식이다.)

구간에 포함되는 덩어리가 $\left \lfloor{N/t}\right \rfloor$개, 양쪽에 남는 원소가 최대 $2(t-1)$개이므로
매 질문에 대해서$O(\max \{N/t, t\})$에 대답할 수 있다.
특정 위치의 갱신은 그 값과 그것을 포함하는 덩어리 두 개의 값만 바꿔주면 되므로 $O(1)$이다.

이때 $t=\sqrt N$으로 잡으면, 매 질문에 대해서 $O(\sqrt{N})$에 대답할 수 있는 훌륭한 자료구조가 완성되었다.
물론 $t=2\sqrt N$이나, $t=0.125 \sqrt N$으로 잡아도 시간복잡도는 동일하기는 하나, 실제로 구현해서 랜덤 데이터를 넣어보면 당연히 소요 시간은 달라진다. 그런 걸 생각하기 어렵기도 하고, 데이터를 모르는 상태에서는 할 수 있는 합리적 추측이 없기 때문에 그냥 $t=\sqrt N$로 많이 쓴다.


이렇게 $\sqrt N$에 비례하게 묶어 미리 저장해둔 덩어리, 혹은 이 기법을 버킷(bucket)이라고 부른다.
버킷을 사용한 풀이는, 추가적인 자료구조나 기타 기법들의 유무에 따라 $O(N \sqrt N)$이나 $O(N \sqrt N \log N)$ 정도의 시간 복잡도를 가지게 되는 것이 일반적이다.

$\sqrt N$이 좀 크지 않냐고 할 수 있는데, 문제를 푸는 데에 있어서 $O(N\sqrt N)$은 $N \leq 100,000$이라면 1초 안에 충분히 돌아가고도 남을 만큼 빠른 방법이다. 경험적으로는 $O(N \log ^2 N)$와 비슷한 시간이 걸린다. $O(N \sqrt N \log N)$ 역시 대부분의 경우에 큰 지장이 없이 문제를 풀 수 있다. 다만 $O(N \sqrt N \log ^2 N)$ 처럼 로그가 한 번 더 붙게 되면, 충분히 빠른 $O(N^2)$과 비슷한 수준이 된다.


어려운 풀이를 요구하는 문제에서, 쉽게 생각 가능한 풀이에 버킷 혹은 $\sqrt N$에 비례하는 무언가를 사용해 시간을 약간 더 빠르게 하면 놀랍게도 생각보다 빨리 작동해 정답을 받는 경우가 종종 있다. 때문에 약간의 비하적인 의미를 담아 이들 기법을 묶어서 '루트질'이라고 부르는 일이 많다.

또한 구현이 생각보다 어려울 수 있어서, 개인적으로는 초보자에게는 별로 추천하지 않는다. 아닌가? 사실 그렇게 어렵지만도 않긴 한데...

'알고리즘 문제풀기 > # 자료구조' 카테고리의 다른 글

구간의 합 구하기  (0) 2018.07.27
Treap  (0) 2015.07.08
Binary Indexed Tree와 구간의 사용방법  (0) 2013.09.06
Fenwick tree  (0) 2013.09.02

+ Recent posts

티스토리 툴바