# [Algorithm](EN) Basic DFS, BFS concept and problem

Solve basic brute force problem which use dfs and bfs.

## Environment and Prerequisite

• C++
• Basic concept of BFS and DFS

## Problem • Problem : There is a map like picture above. 1 represents house, 0 represents nothing. Chulsoo plans to define connected houses as apartment block and assign same number to each block. Connected houses means that specific house is connected to other houses near up, right, down and left(like on the image). Houses in cross line are not connected. Picture on the right is numbered apartment block of picture on left. Find each apartment blocks number of houses and print those houses in ascending order.

### Apporach

• We can find apartment blocks by scanning all places on the map. While searching all places on map, define apartment block when we meet 1(house) and count number of houses.
• We need to scan all places so it is brute force search.
• In apartment block, we need to spread out from one position to around neighbors. So we can think it as BFS or DFS.

### Solution

1. Check if there is a 1(house), while scanning all places on map.
2. If there is a 1(house), define it as new apartment block and assign ID to it.
3. Find number of houses in apartment block by using BFS or DFS.
4. Add number of houses in apartment block to array.
5. After scanning all places on map, sort array in ascending order and print it.

### Definition

• `Bruete Force or Exhaustive Search` : Solution which search all the possible cases.
• It is accurate but takes long time.
• Ex : Sum from 1 to n, Find specific number in random array

## BFS and DFS

### Concept • DFS(Depth First Search) : Explores as far as possible along each branch before backtracking(move to neighbor).
• BFS(Breadth First Search) : Explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
• See above attached image. The number is traverse order.

### Method

• DFS : Use stack or recursion
• BFS : Use queue

## Solution Codes

### DFS(Recursion)

• DFS solution using recursion
``````// DFS - Recursion
void dfs_recursion(int x, int y) {

// step into function -> it means visited
visited[x][y] = true;
// increase number of houses in group_id apartment block
groups[group_id]++;

// search around current x,y position
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];

// if nx and ny are in map
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// if cur nx,ny is not visited then -> visit
if(map[nx][ny] == 1 && visited[nx][ny] == false){
dfs_recursion(nx, ny);
}
}
}
}
``````

### DFS(Stack)

• DFS solution using stack
``````// DFS - Stack
void dfs_stack(int x, int y) {

stack< pair<int,int> > s; // stack for dfs, (x,y) -> (row, col)
s.push(make_pair(x,y)); // make pair data structure and push to stack

// first visit to x,y -> make x,y position visited
visited[x][y] = true;
// increase number of houses in group_id apartment block
groups[group_id]++;

while(!s.empty()){

// get top element of stack
x = s.top().first;
y = s.top().second;
s.pop();

// search around current x,y position
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];

// if nx and ny are in map
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// if cur nx,ny is not visited then -> visit
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;

// increase number of houses in group_id apartment block
groups[group_id]++;

// also push current x,y and nx,ny
// because it is dfs(search around other positions after processing nx,ny then come back to x,y)
s.push(make_pair(x,y));
s.push(make_pair(nx,ny));
}
}
}
}
}
``````

### BFS(Queue)

• BFS solution using queue
``````// BFS
void bfs(int x, int y){

queue< pair<int,int> > q; // queue for dfs, (x,y) -> (row, col)
q.push(make_pair(x,y)); // make pair data structure and push to queue

// first visit to x,y -> make x,y position visited
visited[x][y] = true;
// increase number of houses in group_id apartment block
groups[group_id]++;

while(!q.empty()){

// get front element of queue
x = q.front().first;
y = q.front().second;
q.pop();

// search around current x,y position
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];

// if nx and ny are in map
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// if cur nx,ny is not visited then -> visit
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;

// increase number of houses in group_id apartment block
groups[group_id]++;

// push current nx,ny to queue
q.push(make_pair(nx,ny));
}
}
}
}
}
``````

### Full Code

``````#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX_SIZE 25

using namespace std;

// up, right, down, left
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int n; // number of rows and columns
int group_id; // apartment block id, it starts from 1
int groups[MAX_SIZE * MAX_SIZE]; // number of houses in each apartment block

int map[MAX_SIZE][MAX_SIZE]; // map
bool visited[MAX_SIZE][MAX_SIZE]; // map for visited or not

// DFS - Recursion
void dfs_recursion(int x, int y) {

// step into function -> it means visited
visited[x][y] = true;
// increase number of houses in group_id apartment block
groups[group_id]++;

// search around current x,y position
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];

// if nx and ny are in map
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// if cur nx,ny is not visited then -> visit
if(map[nx][ny] == 1 && visited[nx][ny] == false){
dfs_recursion(nx, ny);
}
}
}
}

// DFS - Stack
void dfs_stack(int x, int y) {

stack< pair<int,int> > s; // stack for dfs, (x,y) -> (row, col)
s.push(make_pair(x,y)); // make pair data structure and push to stack

// first visit to x,y -> make x,y position visited
visited[x][y] = true;
// increase number of houses in group_id apartment block
groups[group_id]++;

while(!s.empty()){

// get top element of stack
x = s.top().first;
y = s.top().second;
s.pop();

// search around current x,y position
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];

// if nx and ny are in map
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// if cur nx,ny is not visited then -> visit
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;

// increase number of houses in group_id apartment block
groups[group_id]++;

// also push current x,y and nx,ny
// because it is dfs(search around other positions after processing nx,ny then come back to x,y)
s.push(make_pair(x,y));
s.push(make_pair(nx,ny));
}
}
}
}
}

// BFS
void bfs(int x, int y){

queue< pair<int,int> > q; // queue for dfs, (x,y) -> (row, col)
q.push(make_pair(x,y)); // make pair data structure and push to queue

// first visit to x,y -> make x,y position visited
visited[x][y] = true;
// increase number of houses in group_id apartment block
groups[group_id]++;

while(!q.empty()){

// get front element of queue
x = q.front().first;
y = q.front().second;
q.pop();

// search around current x,y position
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];

// if nx and ny are in map
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// if cur nx,ny is not visited then -> visit
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;

// increase number of houses in group_id apartment block
groups[group_id]++;

// push current nx,ny to queue
q.push(make_pair(nx,ny));
}
}
}
}
}

int main (){

scanf("%d", &n);

for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
// get integer one by one -> %1d
scanf("%1d", &map[i][j]);
}

// search all values in map
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// if cur i,j is not visited then -> visit
if(map[i][j]==1 && visited[i][j]==false){

// assign id to current position(apartment block)
group_id++;

// Search
//dfs_recursion(i, j);
//dfs_stack(i, j);
//bfs(i, j);
}
}
}

// sort number of houses in each apartment block in ascending order
// ID starts from 1
// usage : https://twpower.github.io/71-use-sort-and-stable_sort-in-cpp
sort(groups + 1, groups + group_id + 1);

printf("%d\n", group_id);
for (int i = 1; i <= group_id; i++) {
printf("%d\n", groups[i]);
}
}
``````

# [VirtualBox] 명령어로 백그라운드(background)에서 VM 실행하기

VirtualBox 가상머신을 백그라운드에서 실행해보자

## 환경 및 선수조건

• Linux or Mac
• VirtualBox and VM(미리 만들어진)

## VBoxManage 명령어

### VBoxManage 명령어란?

• `VBoxManage` : VBoxManage는 Oracle VirtualBox를 사용할 수 있는 커맨드라인 명령어입니다.
• VirtualBox를 API를 통해 사용할 수 있는 명령어라고 볼 수 있습니다.
• API DOC : https://www.virtualbox.org/manual/ch08.html

#### VM을 백그라운드에서 실행

• 기본
``````VBoxManage startvm [VM NAME] --type headless
``````
• 예제
``````VBoxManage startvm "Ubuntu 14.04" --type headless
``````

#### VM을 현재 상태로 저장

• 기본
``````VBoxManage controlvm [VM NAME] savestate
``````
• 예제
``````VBoxManage controlvm "Ubuntu 14.04" savestate
``````

# [VirtualBox](EN) Run VM in background by using command line interface

Run VirtualBox VM in background by using command line interface

• Linux or Mac

## VBoxManage Command

### What is VBoxManage command?

#### Run VM in background

• Usage
``````VBoxManage startvm [VM NAME] --type headless
``````
• Example
``````VBoxManage startvm "Ubuntu 14.04" --type headless
``````

#### Save VM in current state

• Usage
``````VBoxManage controlvm [VM NAME] savestate
``````
• Usage
``````VBoxManage controlvm "Ubuntu 14.04" savestate
``````

# [Algorithm] 언어별(C, C++, Python, Javascript, Java, Shell Script) 난수(랜덤 값) 생성하기

각 언어에서 난수를 생성하는 방법을 알아보자

## 환경

• C, C++, Python, Javascript, Java, Shell Script

## 난수 생성 코드

### C

• `rand` 함수 이용
• `rand()` : 0과 RAND_MAX 사이에 난수 정수 값을 반환
• `srand``time`함수는 랜덤 생성할 시드 값을 위해 사용
``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main (){

// use time for seed
srand(time(NULL));

// print one number in range 1 ~ 50
printf("%d\n", rand() % 50 + 1);

return 0;
}
``````

### C++

• `rand` 함수 이용
• `rand()` : 0과 RAND_MAX 사이에 난수 정수 값을 반환
• `srand``time`함수는 랜덤 생성할 시드 값을 위해 사용
``````#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main (){

// use time for seed
srand(time(NULL));

// print one number in range 1 ~ 50
cout << rand() % 50 + 1 << endl;

return 0;
}
``````

### Python

• `random`패키지 사용
• `random.random()` : 0이상 1미만의 실수를 반환
• `random.randrange(a,b)` : a이상 b미만의 정수를 반환
``````import random

# value between 0 and 1, 1 is not included
# ex) 0.667165525151183
rand_value = random.random()

# random integer between a and b, b is not included
rand_value = random.randrange(1,50) # 1 ~ 49
``````

### Javascript

• `Math.random()`를 사용
• `Math.random()` : 0이상 1미만의 실수를 반환
``````
// value between 0 and 1, 1 is not included
// ex) 0.8645079349832587
var = Math.random();

// 올림, 내림, 반올림 -> ceil, floor, round
Math.ceil (Math.random()) // 1
Math.floor (Math.random()) // 0
Math.round (Math.random()) // it depends
``````

### Java

• `java.util.Random` 혹은 `java.lang.Math`를 이용
• random.nextInt(n) : 0 ~ n-1 사이의 난수 정수 값을 반환
• Math.random() : 0이상 1미만의 실수를 반환
``````import java.util.Random;

public class Main {
public static void main(String[] args) {
// Random example using java.util.Random
Random random = new Random();
// Number between 100 and 199
System.out.println(random.nextInt(100) + 100);

// Random example using java.
// Number between 100 and 199
System.out.println( (int)(Math.random() * 114124)%100 + 100 );
}
}
``````

### Shell Script

• `\$RANDOM`를 이용
• `\$RANDOM` : 0 ~ 32767 사이의 정수 값을 반환
``````
# Number between 0 and 32767
echo \$RANDOM

# Number between 100 and 199
echo \$((\$RANDOM*12345%100 + 100))

``````

# [Network] ip address 명령어에 대해서 알아보기

ip address 명령어와 해당 내용에 대해서 간략하게 알아보자

## ip 명령어

### ip 명령어란?

• `ip` : 라우팅, 장치(NIC, Bridge …) 그리고 터널링과 같이 네트워크에 관련된 부분들을 수정하고 조회할 떄 사용하는 명령어입니다.
• `ip(in english)` : show or manipulate routing, devices, policy routing and tunnels
• 사용법
``````ip [ OPTIONS ] OBJECT { COMMAND | help }
``````
• `OBJETCT` : `link, address, route, rule, tunnel`와 같은 대상들을 조회 및 수정할 수 있습니다.

• 위의 `ip`명령어에서 `OBJETCT``address`인 명령어로 NIC들에 대해 IP주소를 조회할 수 있으며 나아가 추가 혹은 삭제도 가능한 명령어입니다.

• 아래는 제가 생성한 VM에서 `ip address`의 출력결과 입니다.
``````\$ ip address
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1
inet 127.0.0.1/8 scope host lo
valid_lft forever preferred_lft forever
inet6 ::1/128 scope host
valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state UP group default qlen 1000
inet 10.0.2.15/24 brd 10.0.2.255 scope global eth0
valid_lft forever preferred_lft forever
valid_lft forever preferred_lft forever
``````

#### LOOPBACK

• 자신의 호스트로 보내는 인터페이스를 의미합니다. `localhost`와 같습니다.

• 브로드캐스트 패킷을 처리할 수 있음을 의미하며 해당 기능을 통해 DHCP 서버로부터 IP주소를 받을 수 있습니다.

#### MULTICAST

• 멀티캐스트 패킷을 처리할 수 있음을 의미합니다.

#### UP

• 해당 NIC가 작동중임을 나타냅니다.

#### LOWER_UP

• L1 레이어 즉, 물리계층에서 신호가 UP이라는 의미로 물리계층에서 신호가 들어오고 있음을 의미합니다.

#### mtu

• 해당 프로토콜이 해당 레이어에서 전송할 수 있는 최대의 단위(바이트)로 이더넷의 기본값은 1500으로 설정됩니다.

#### qdisc

• Queuing Disciplines를 의미하며 NIC에 들어오기전에 데이터 패킷들이 Queue에 저장되는데 FIFO형식인 Queue에 넣기전에 패킷에 우선순위를 부여해서 스케쥴링하는 부분으로 현재 eth0의 경우 pfifo_fast라는 방식을 사용한다는 의미입니다.

#### state

• 현재 NIC의 작동상태를 의미합니다.

#### group

• 인터페이스 그룹을 의미합니다. 기본값은 default입니다.

#### qlen

• 전송큐의 크기를 의미합니다.

• L2 레이어 즉, Link Layer의 프로토콜이 Ethernet이라는 의미이며 바로 옆에 나오는 주소는 해당 NIC의 MAC주소이고 brd는 브로드캐스트를 할 때의 주소를 의미합니다.

#### inet

• L3 레이어 즉, Network Layer가 인터넷임을 의미하며 바로 옆에 나오는 주소는 ipv4와 ipv6에 따른 주소를 의미합니다.

#### scope

• 해당 인터페이스가 어느 수준에서 접근가능하며 유효하냐는 의미입니다. Global의 경우 외부 네트워크에서 접근이 가능한 범위이며(클라우드에서 호스팅한 인스턴스에 들어가면 Global로 나와있는 경우가 있습니다.) Link의 경우 현재 인터페이스가 속한 LAN안에서만 접근이 가능하고 유효하며 Host의 경우는 현재 인터페이스가 속해있는 호스트에서만 유효하고 접근이 가능하다

#### valid_lft, preferred_lft

• 자료의 내용을 참고하면 valid_lft(Valid Lifetime)은 해당 주소가 유효한 시간을 의미하며 뒤에 나온 preferred_lft(Preferred Lifetime)보다 크거나 같다고 합니다. preferred_lft은 의미 그대로 해당 주소가 유효했으면 하는 설정값입니다.