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-bfs-example

  • 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]);
    }
}


Reference

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


참고자료

Run VirtualBox VM in background by using command line interface


Environment and Prerequisite

  • Linux or Mac
  • VirtualBox and VM(alreaday amde)


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


Reference

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


환경

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


난수 생성 코드

C

  • rand 함수 이용
  • rand() : 0과 RAND_MAX 사이에 난수 정수 값을 반환
  • srandtime함수는 랜덤 생성할 시드 값을 위해 사용
#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 사이에 난수 정수 값을 반환
  • srandtime함수는 랜덤 생성할 시드 값을 위해 사용
#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))


참고자료

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 address란?

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


ip address 예시

  • 아래는 제가 생성한 VM에서 ip address의 출력결과 입니다.
$ ip address
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    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
    link/ether 08:00:27:45:44:cc brd ff:ff:ff:ff:ff:ff
    inet 10.0.2.15/24 brd 10.0.2.255 scope global eth0
       valid_lft forever preferred_lft forever
    inet6 fe80::a00:27ff:fe45:44cc/64 scope link
       valid_lft forever preferred_lft forever


ip address 항목 설명

LOOPBACK

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

BROADCAST

  • 브로드캐스트 패킷을 처리할 수 있음을 의미하며 해당 기능을 통해 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

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

link/ether

  • 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은 의미 그대로 해당 주소가 유효했으면 하는 설정값입니다.


참고자료