2017년 9월 19일 화요일

Javascript Solution - Insertion Sort - Part 1

hackkerank Insertion Sort - Part 1 


function insertSortLog(arr){
    var n = arr.length-1
    var unsorted = true
    var tmp = arr[n]
    var log = []
    while(unsorted){
        if(tmp < arr[n-1]) {
            arr[n] = arr[n-1]
            n--
        } else {
            arr[n] = tmp
            unsorted = false
        }
        console.log(arr.join(' '))
    }
}

function processData(input) {
    //Enter your code here
    input = input.split('\n')
    var n = input[0]
    var arr = input[1].split(' ')
    insertSortLog(arr)
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});
작성자: 시간: 댓글 없음:
라벨:

Javascript Solution - Intro to Tutorial Challenges

hackkerank Intro to Tutorial Challenges 


function processData(input) {
    //Enter your code here
    input = input.split('\n')
    var V = input[0]
    var n = input[1]
    var ar = input[2].split(' ')
    console.log(ar.indexOf(V))
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});
작성자: 시간: 댓글 없음:
라벨:

Javascript Solution - Big Sorting Solution

hackkerank Big Sorting Solution 


process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////
function compare(a,b){
    if(a.length > b.length){
        return 1
    }
    else if(a.length < b.length){
        return -1
    }
    var unsolve = true,idx = 0
    var char_a,char_b
    while(unsolve){
        char_a = parseInt(a.charAt(idx))
        char_b = parseInt(b.charAt(idx))
        
        if(isNaN(char_a)){
            return 0
        }
        
        if(char_a > char_b){
            return 1
        }
        else if(char_a < char_b){
            return -1
        }
        else{
            idx++
        }
    }
}


function main() {
    var n = parseInt(readLine());
    var unsorted = [];
    for(var unsorted_i = 0; unsorted_i < n; unsorted_i++){
       unsorted[unsorted_i] = readLine();
    }
    // your code goes here
    var sorted = unsorted.sort(compare)
    console.log(sorted.join('\n'))
}
작성자: 시간: 댓글 없음:
라벨:

2016년 7월 26일 화요일

[android] RecyclerView 에서의 setOnItemClickListener (흉내내기)

[개요]


RecyclerView는 ListView에서의 비효율적인 리스트 아이템 생성과 같은 점을 극복하고자 좀 더 유연하고 좀 더 효율적으로 사용되기 위해 만들어졌다고 합니다.
RecyclerView이 만들기 이전에도 ListView에서 ViewHolder개념을 응용? 도입? 해서 효율적으로 사용하였지만 RecyclerView에선 강제적으로 사용하게 되었다고 합니다.

하지만 Listview에서 setOnItemClickListener 와 같은 기능을 지원하지 않습니다.  addOnItemTouchListener와 같은 기능이 있지만 listview에서와 같이 직접적으로 position에 접근을 할 수 없고 여러 이슈가 있다고 합니다.

[흉내내보자]


RecyclerView에서 onBindViewHolder해줄 때에 각각의 아이템에 OnClickListener를 등록해 주는 것으로 접근했습니다.
코드는 핵심적인 부분만 중략해서 작성했습니다.


public class RecyclerAdapter extends RecyclerView.Adapter{
    private ArrayList strings;

    //아이템 클릭시 실행 함수
    private ItemClick itemClick;
    public interface ItemClick {
        public void onClick(View view,int position);
    }

    //아이템 클릭시 실행 함수 등록 함수
    public void setItemClick(ItemClick itemClick) {
        this.itemClick = itemClick;
    }

    public static class ViewHolder extends RecyclerView.ViewHolder{
        View view;
        public ViewHolder(View view) {
            super(view);
            this.view = view;
        }
    }

    @Override
    public RecyclerAdapter.ViewHolder onCreateViewHolder(ViewGroup parent,
                                                         int viewType) {
        // create a new view
        View v = LayoutInflater.from(parent.getContext())
                .inflate(R.layout.list_items, null);
        ViewHolder vh = new ViewHolder(v);

        return vh;
    }


    //중략 ...................

    @Override
    public void onBindViewHolder(ViewHolder holder, int position) {
        final int Position = position;
        //중략 ...................
        holder.view.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                if(itemClick != null){
                    itemClick.onClick(v, Position);
                }
            }
        });
    }
    //중략 ...................

}
adapter 부분에서 이와 같은 방식으로 작성하였습니다.
이후에 recycler 호출부분에서 아래와 같이 작성한다면, listview에서 setOnItemClickListener 와같이 작동할 수 있습니다.

        mAdapter.setItemClick(new RecyclerAdapter.ItemClick() {
            @Override
            public void onClick(View view, int position) {
                //클릭시 실행될 함수 작성
            }
        });

코드가 길어져 상당히 중략을 하였습니다.

제가 작성한 예제 코드는
안드로이드 스터디 프로젝트 git에 공유하고 있습니다.

작성자: 시간: 댓글 없음:
라벨: , ,

[java] x초전.., x분전.., x시간전.. 표시하기.

오랫동안의 서버 프로그래밍이 아닌 안드로이드 개발을 시작하면서 만든 함수 입니다.




위와 같은 기능을 만들어 보고 싶었습니다.
생각보다 쉬운 코드라서 별다른 설명이 필요 없을 듯 합니다.
안드로이드 개발을 하며 안들었지만 사용된 함수가 SimpleDateFormat 이기 때문에 java 개발을 하실 때 그냥 사용하시면 되겠습니다.

코드는 여기 에서 보셔도 됩니다.

코드


public class CommonUtil {

    public String beforeTime(Date date){

        Calendar c = Calendar.getInstance();

        long now = c.getTimeInMillis();
        long dateM = date.getTime();

        long gap = now - dateM;

        String ret = "";

//        초       분   시
//        1000    60  60
        gap = (long)(gap/1000);
        long hour = gap/3600;
        gap = gap%3600;
        long min = gap/60;
        long sec = gap%60;

        if(hour > 24){
            ret = new SimpleDateFormat("HH:mm").format(date);
        }
        else if(hour > 0){
            ret = hour+"시간 전";
        }
        else if(min > 0){
            ret = min+"분 전";
        }
        else if(sec > 0){
            ret = sec+"초 전";
        }
        else{
            ret = new SimpleDateFormat("HH:mm").format(date);
        }
        return ret;

    }
}


결과값으로는
x초 전
x분 전
x시간 전
이런식으로 나오게 되고
이외에는 시:분으로 나오게 되는데.
https://developer.android.com/reference/java/text/SimpleDateFormat.html
을 참고하셔서 수정하시면될듯합니다.
작성자: 시간: 댓글 없음:
라벨: ,

2016년 3월 7일 월요일

[redis - node] key event 받아보기

redis key event 받아보기

관련페이지 : http://redis.io/topics/notifications

redis keyspace notification은 2.8버전부터 지원하며 버전 확인은
-> info server  를 통해 확인 가능합니다.

레디스에서는 키 이벤트에 대한 것들의 설정을 하게 되면 pub/sub 패턴을 이용하여 메세지(이벤트)를 전달합니다. 키 이벤트가 발생을 하게 되면 redis서버에서는 keyspace,keyevent의 포맷으로 메세지를 전달합니다.

CONFIG SET nitifi-keyspace-events [option]

를 통해 설정하게 됩니다. options은 위 링크에 나와있습니다. 간단하게
keyspace에 관한 설정은 K
keyevent에 관한 설정은 E
그 뒤의 옵션으로 g, $, l, s, h, z, x, e등이 있으며 A를 통하여 앞의 모든것들 설정가능합니다.각각 옵션에 대한것은 위의 본문 링크를 들어가서 확인하시면 됩니다.

예.. 설명이 빈약합니다. ㅠ
keyspace에 대한 설정을 하게 되면 __keyspace@<db>__[key] 라는 채널로 이벤트가 message로 발행이되고
keyevent에 대한 설정을 하게 되면 __keyevent@<db>__[event] 라는 채널로 key가 message로 발행이됩니다.

받아볼 이벤트의 종류는 g, $, l, s, h, z, x, e, A등을 통하여 설정가능합니다.
예로

CONFIG SET notifiy-keyspace-events KEA

라고 설정을 하게 된다면, 모든 이벤트에 대하여 keyspace,keyevent 채널로 발행이 될것입니다.
제가 맨처음 필요로 했었던 expire에 대한 이벤트의 기준으로만 받아보고 싶다면

CONFIG SET notifiy-keyspace-events Ex

이렇게 설정하면 됩니다.
결과로는

__keyevent@<db>__:expired
의 채널로 키값이 message로 얻어지게 될것입니다.


간단히 redis에서의 pub/sub패턴을 소개하자면 publish,subscript, 즉, 발행, 구독!
레디스에서는 pub/sub를 패턴,채널,메세지의 요소로 나눠 이용합니다.
publisher가 메세지를 해당 채널에 메세지를 전달하게 되면,  패턴에 일치하는 subscriber들이 메세지를 받아보게 됩니다.

pub/sub예제이자 redis notification예제입니다. node입니다.

var redis = require("redis")
  , subscriber = redis.createClient()
  , red  = redis.createClient();

red.config("SET","notify-keyspace-events", "Ex");

subscriber.on("pmessage", function (pattern, channel, message) {
    console.log("pattern : "+pattern+" channel: "+channel+" message : "+message);
});
subscriber.psubscribe("__key*__:*");

red.setex("string key", 10,"string val",redis.print);


결과로는
pattern : __key*__:* channel: __keyevent@0__:expired message : string key

Ex로 설정하였기 때문에 해당 키가 expired된다면 해당 key값을 얻을 수 있습니다.

만약 KEA로 설정을 한다면

pattern : __key*__:* channel: __keyspace@0__:string key message : set
pattern : __key*__:* channel: __keyevent@0__:set message : string key
pattern : __key*__:* channel: __keyspace@0__:string key message : expire
pattern : __key*__:* channel: __keyevent@0__:expire message : string key
---------------------------------------
pattern : __key*__:* channel: __keyspace@0__:string key message : expired
pattern : __key*__:* channel: __keyevent@0__:expired message : string key
이렇게 나옵니다. ㅎ
작성자: 시간: 댓글 1개:
라벨: , , , , ,

2016년 1월 25일 월요일

[nodejs - redis] rediss - session 레디스 세션 이용하기

redis를 session서버로 사용하는 방법


session의 값을 server와 분리 시킴으로서 안정적으로 저장하고 여러개의 서버의 세션을 하나의 redis서버로 통합하여 사용 할 수 있습니다. session의 특성상 입출력이 빈번하기 때문에 redis의 성격과도 잘 맞다고 생각됩니다.

우선 환경은
입니다.

레디스 설치 방법은 생략합니다.


//redis session require
var session = require('express-session');
var redis = require('redis');
var redisStore = require('connect-redis')(session);
var client = redis.createClient();

app.use(session(
    {
        secret: 'secret_key',
        store: new redisStore({
            host: "127.0.0.1",
            port: 6379,
            client: client,
            prefix : "session:",
            db : 0
        }),
        saveUninitialized: false, // don't create session until something stored,
        resave: true // don't save session if unmodified
    }
));

//....아래쪽...

//redis session input output
var router = express.Router();
router.get('/session/set/:value', function(req, res) {
    req.session.redSession = req.params.value;
    res.send('session written in Redis successfully');
});

app.get('/session/get/', function(req, res) {
    if(req.session.redSession)
        res.send('the session value stored in Redis is: ' + req.session.redSess);
    else
        res.send("no session value stored in Redis ");
});
를 app.js에 작성하면 설정이 끝나게 됩니다.

new redisStore 부분에 자신의  reids설정을 작성하고 db의 파라미터를 통하여 session store로 사용할 db index를 설정합니다.

prefix를 통하여 키값의 앞에 붙일 값들을 정합니다. redis는 : <- 를 통하여 키값들을 grouping하게 됩니다. 즉, 위와 같이 해놓게 된다면 session에 해당하는 key값들은
아래 결과의 사진을 보게 됬을때 정리가 깔금하게 됩니다.

session의 상용방법은
http://mythinkg.blogspot.kr/2015_01_01_archive.html
를 참고해주시면 됩니다.
단순히 redis에 값을 저장하는 것이기 때문에 사용방법은 express-session과 같고 결과는 아래와 같이 나오는 걸 확인하여 session값이 저장됨을 볼 수있습니다.




작성자: 시간: 댓글 없음:
라벨: , , , ,

2015년 11월 16일 월요일

안드로이드 http통신 retrofit 2.0

retrofit은 http통신모듈로서 android에서 많이 사용한다고 합니다.

  • 파싱 & value object로의 변환이 편하고
  • template 방식으로의 사용
  • 동기 & 비동기 지원

의 장점을 뽑을 수 있을 것 같습니다.
spring framework를 공부하면서 동시에 개발하고 있는데 사용방식이 많이 유사함이 느껴집니다.

2.0을 기준 입니다.

저의 환경으로는  json으로 서버와 값을 주고 받게 됩니다.

기본적인 튜토리얼은 http://square.github.io/retrofit/ 를 참고했습니다.

먼저 라이브러리 추가. (GRADLE)


compile 'com.squareup.retrofit:retrofit:2.0.0-beta2'
//json파싱을 위한 주입
compile 'com.squareup.retrofit:converter-gson:2.0.0-beta2'
//xml파싱을 위한 주입
compile 'com.squareup.retrofit:adapter-rxjava:2.0.0-beta1'

value object 작성

public class test {
    private String ret;

    public String getRet() {
        return ret;
    }

    public void setRet(String ret) {
        this.ret = ret;
    }
}

Service작성


public interface TestService {
    @FormUrlEncoded
    @POST("/test")
    public Call<test> retroTest(@Field("param") String aa);
}

어노테이션을 몇개 정리.
@POST("상세주소")를 이용하여 상세 주소를 설정합니다.
@GET/PUT/DELETE등도 사용가능합니다.
@HEARs를 이용해서 헤더 설정도 가능하고

@FormUrlEncoded을 사용하여 x-www-form-urlencoded를 설정하고
@Multipart를 이용한 파일전송 등도 설정 가능합니다.

동기/비동기 방식이 1.9버전에서는 선언하는 방식이 서로 달랐는데 2.0버전에서는 두가지의 차이가 없습니다. 사용에 따라서 동기/비동기가 나눠지는데 아래 설명하겠습니다.


Service생성 및 반환

public class repo {
    public TestService getService(){
        Retrofit retrofit = new Retrofit.Builder()
                .baseUrl("http://192.168.25.24:8080")
                .addConverterFactory(GsonConverterFactory.create())
//              .addConverterFactory(SimpleXmlConverterFactory.create())
                .build();
        TestService service =  retrofit.create(TestService.class);
        return service;
    }
}

baseUrl을 설정하고, 저는 json만을 사용하기 때문에 GsonConverterFactory만 설정하였고 xml을 사용하시려면 SimpleXmlConverterFactory까지 설정 하시면 됩니다.

getService()를 이용하여 TestService에 대한 설정,생성,반환을 받습니다.

동기방식 사용

String result = null;
TestService service = new repo().getService();
Call<test> c = service.retroTest("aa");
try {
    result = c.execute().body().getRet();
} catch (IOException e) {
    e.printStackTrace();
}
위 방식은 동기방식 입니다. Call<test>를 받은 이후 실행(execute) -> 결과(body)를 하게 되면 위의 결과는 test객체에 담겨져 오게 됩니다.

비동기방식 사용

final String[] result = {null};
TestService service = new repo().getService();
Call<test> c = service.retroTest("aa");
c.enqueue(new Callback() {

    @Override
    public void onResponse(Response response, Retrofit retrofit) {
        result[0] = response.body().getRet();
    }

    @Override
    public void onFailure(Throwable t) {
        result[0] = "false";
    }
});
위 방식은 비동기방식 입니다. Call<test>를 받은 이후 enqueue를 통해 구현합니다.
onResponse를 통하여 결과값을 받을 때 처리, 즉 callback방식으로의 처리를 하게 됩니다.

위의 방법으로 안드로이드(또는 다른 java플렛폼)에서 사용을 간단하게 http통신을 하게 됩니다.
작성자: 시간: 댓글 2개:
라벨: , , ,

2015년 11월 9일 월요일

[spring] - mongo 에러처리

mongodb의 특성상 처리에 대한 결과를 신경 쓰지 않는다.

즉, 삽입에서의 성공, 실패에 대한 처리가 불가능가능하지 않다.

 결과를 리턴받는 것은 필요한 기능이고 당연 기능을 제공한다. 하지만 spring에서든 node에서든 이러한 성격에 따라 결과를 신경쓰지 않는 것을 따기 때문에 default 설정으로 그냥 넘기게 된다.

xml 설정의 mongoTemplate의 설정 부분을 바꾸면 된다.
<bean id="mongoTemplate" class="org.springframework.data.mongodb.core.MongoTemplate">
    <constructor-arg ref="mongo" />
    <constructor-arg value="oman" />
    <property name="writeResultChecking" value="EXCEPTION"/>
</bean>


value로 설정 할 수 있는 값은 3가지다.
none, exception, log



  • none
    • default 설정 값으로 아무런 행동도 하지 않는다. error를 던지지도 않고 로그로도 남기지 않는다.
  • log
    • 문제가 생길 경우 로그로 남긴다.
    • ....failed: E11000 duplicate key error index:........
  • exception
    • 예외처리가 되어 핸들링 할 수 있게 된다.
    • org.springframework.dao.DataIntegrityViolationException:.......

작성자: 시간: 댓글 없음:
라벨: , ,

2015년 10월 24일 토요일

mysql transction isolation level (트렌젝션 격리 수준)



repeatable read
  • mysql에서 default로 설정되어 있는 트랜젝션 격리수준이다. 
  • 한 데이터에 대하여 데이터 트랜젝션이 수행중일 경우 읽기에 대한 접근을 할 수 있다.
  • 한 데이터에 대해 여러 트랜젝션이 동시에 진행중일 때 모든 트렌젝션이 끝날때까지 이전의 데이터를 읽을 수 있다.
    • 이점은 read commit 과 다른 점이다.
read uncommitted
  • 커밋 되지 않은 데이터 상태에서 읽을 경우 추후에 롤백이 되더라도 처리 된 부분까지의 결과를 읽을 수 있습니다. 즉, 트랜젝션 중간이라도 데이터 읽기에 대한 접근이 가능합니다.
  • dirty read라고 부르기도 한다.
read commit
  • 트랜젝션 중의 경우 커밋이 되어 있지 않다면 이전의 데이터를 읽는다는 점에서는 repeatable read와 비슷하다.
  • 여러 트랜젝션이 수행중일 경우 해당 세션에서 진행중인 트랜젝션의 범위 내에서만 적용된다.
 SERIALIZABLE
  • 가장 높은 level의 트랜젝션
  • 데이터에 대하여 트랜젝션이 수행중인 경우 읽기 쓰기 수정 삭제 모든게 불가능하다.
작성자: 시간: 댓글 없음:

2015년 10월 12일 월요일

barcode 표기법 : code 128에 대하여

원문 : https://en.wikipedia.org/wiki/Code_128


code 128에 대하여..

사진 출처는 언제나 위키피디아

code128은 아주 높은 정보를 집약해 놓을 수 있는 1차원 바코드 표기법이다.
즉, 적은 양의 표기로 많은 양의 정보를 보여줄 수 있다. (어디까지나 1차원 중에서..)
스마트폰의 스대가 오면서 2차원 바코드 스캐너, 즉 qr코드등의 스캔이 용이 해지면서 qr로 더욱 많은 정보를 전달하지만, 1차원 바코드가 비교적 빠르고 이미 많은 시스탬화 되어 있는 상황과 시중에 (특히 중고로 구매사용하는 상점들)은 1차원 바코드 스캐너를 이용하고 있다.  

흔히 바코드라 말하는 상품 분류코드는 ean 13으로 13자리표기로 물품을 분류관리 하고 있고 code128은 좀 다른 방식이다.

code 128의 심볼

총 108개의 문자를 표현 할 수 있다. 이중에 start symbol(3개)과 stop symbol(2개)를 제외하면 총 105개의 문자를 표현 할수 있다.
각 심볼을 구성하는 요소는 3개의 bar와 3개의 white space로 이루어져 있다.

Bar와 White Space

하나의 문자(심벌)에는 3개의 bar와 white space를 가지고 있으며 각각의 요소는 다른 두깨를 가지고 있으며 이에는 몇가지 규칙이 있다.

  • 이 두가지(bar,space)는 각각 1~4의 두깨를 가질수 있다.  
  • 하나의 symbol에서 Bar들의 두깨의 합은 짝수의 넓이를 가지고 
  • Space의 넓이들의 합은 홀수를 가져야 한다.
  • 하나의 심벌에서 모든 넓이의 값은 11의 넓이이다.(stop symbol일 경우 13)
바코드를 2진표기할때 이것을 이용한다.
예를 들어 0을 표기할때 11011001100로 표기하는데, 
순서대로 (단위: 두깨) 
  • 검은바(2) 흰공백(1) 검은바(2) 흰공백(2) 검은바(2) 흰공백(2)
가 되며 
  • 검은 바의 넓이의 합은 6(짝수)가 되며 흰공백의 넓이의 합은 5(홀수)가 된다.
  • 총 넓이의 합은 11이 된다.

Start Symbol

code128은 3가지의 code set을 사용한다. 각각 128a,128b,128c로 부른다.
이를 정의 하기 위한 symbol을 앞에 위치하게 된다. 위의 그림에서 2개의 2번영역 중 앞에 위치하게 된다.

Stop Symbol

stop심볼은 특수한 심볼이다. 다른 symbol들과는 달리 4개의 bar, 3개의 white space로 이루어져 있다. 1100011101011(2331112)로 적으며 위의 그림에서 2개의 2번영역중 뒤에 위치하게 된다. stop symbol은 아주 특수한 심벌로서 중요한 역활을 한다.
  • 바코드을 거꾸로 읽었을 경우를 인지 할 수 있다.
바로 읽을경우 2331112로 끝을 알리고 거꾸로 읽었을 경우 즉, 2111332일 경우 바코드를 반대로 읽었음을 인지하고 바로 할 수 있다.

Check digit

code 128에도 체크섬과 같은 역활을 하는 부분이 있다.
start symbol *1,과 각각의 2진비트값 * 위치 를 103으로 나눈 값을 적어 둔다.
마치 주민등록번호 유효성 검사와 같다.
위의 위치에서 4번에 위치하게 된다.

Quiet zone

바코드의 앞,뒤에 존재하게 되며, 최소한의 크기는 바코드의 내용문자의 *10의 크기를 가져야 한다. 위의 그림에서 1번에 위치하게 된다.

FUNCTION4

를 사용하면 더욱 많은 문자(특수한 문자)를 사용 할 수 있다고 한다.
작성자: 시간: 댓글 없음:
라벨: , ,

2015년 6월 28일 일요일

몬티홀 문제 코딩 구현

확률에 관한 공부를 조금만 깊게 하면 한번쯤은 만나는 문제인듯 합니다.
몬티홀 게임, 몬티홀 딜레마 라고 불리는 이 문제의 법칙 및 순서는 아래와 같습니다.
  1. 각각의 3개의 문 뒤에는 염소 2마리, 자동차 1대 중 하나가 있다.
  2. 참가자는 하나의 문을 선택한다.
  3. 사회자는 선택되지 않은 문 중에 염소가 있는 문 하나를 공개한다.
  4. 참가자는 처음 선택한 문과 나머지 하나의 문 중에서 선택을 바꿀 기회를 얻는다.
  • 이러한 상황일 경우 바꾸는 것이 좋을 것인가? 그대로 선택하는 것이 좋을 것인가?


이 문제는 (적어도 저에게) 딜레마라는 문제 답게 이해하기 힘들었습니다.

이 문제는 사실 아주 쉬운 문제입니다.
  • 처음 고른 상품이 차 일 경우(1/3 확률) 사회자가 제외시킨 문을 제외하면 나머지는 무조건 염소
  • 처음 고른 상품이 염소 일 경우(2/3 확률) 사회자가 제외 시킨 문을 제외하면 나머지는 무조건 차

라는 결과가 나옵니다.

이 문제를 알려주셨던 선생님의 표현을 빌려 쓰자면, 사회자가 선택한 문의 확률이 흡수 되었다고 할 수 있습니다.


var i = 0;
var arr = ['goat','goat','goat'];
var success = 0;
var fail = 0;
for(i = 0;i<100000;i++,arr=['goat','goat','goat']){
	//자동차 랜덤 위치
	var car = Math.floor(Math.random()*3);
	arr[car] = 'car';
	
	//랜덤하게 선택
	var choice = Math.floor(Math.random()*3);
	
	
	//염소위치 알려줌
	do{	
		rm_index = Math.floor(Math.random()*3);
	}while(rm_index == car || rm_index == choice);


	//바꾼후 진행
	choice = 3-(rm_index+choice);
	
	if(arr[choice] == 'car'){
		success++;
	}
	else{
		fail++;
	}	
}

console.log("case : change")
console.log("success " + success);
console.log("fail " + fail);
결과는
success 33322
fail 66678
success 66660
fail 33340
작성자: 시간: 댓글 없음:
라벨: , , ,

2015년 5월 2일 토요일

트랜젝션 4가지 속성 ACID!


  • 분명 공부할때 에시드 에시드 에시드 하면서 외웠지만 벙떄림..

  • 원자성(Atomicity)
    • 트랜젝션과 관련된 작업은 하나의 단위이다.
    • 은행에서 이체의 예
      • 1)a의 출금, 2)b의 입금   2가지의 작업
      • 에러의 시점
        • 1)전 : a의 출금이 되지 않는다. b의 입금이 되지 않는다.
        • 1)후, 2)전 : a의 출금이 되었다. b의 입금이 되지 않는다.
        • 2)후 : a의 출금이 되었다. b의 입금이 되었다.
      • 위의 경우 두번째의 경우 중간 단계까지 실행되고 실패하는 일은 없어야한다.
      • 이러한 일을 방지하기 위해 원자성을 보장해야한다. 중간단계에서 실패하는 경우는 없어야한다.
      • 모든 작업은 하나의 단위로 하여 모든 경우 에러, 성공의 결과가 같아야한다.
  • 일관성(Consistency)
    • 트랜잭션 처리 후 모든 데이터베이스의 상태는 이전의 상태와 같아야 한다.
    • 즉. 결과가 데이터베이스의 무결성 제약 등을 위반하거나 모든 상태에 영향을 주어서는 안 된다.
  • 고립성(Isolation)
    • 트랜잭션의 연산은 다른 트랜잭션, 다른 연산작업이 끼어들지 못하게 보장해야한다.
  • 지속성(Durability)
    • 트랜잭션의 연산이 성공적으로 이루어지고 나면 그 결과는 유지되어야 한다.
작성자: 시간: 댓글 없음:
라벨:

2015년 4월 20일 월요일

[data structure javascript] binary tree


  • 실행환경 : nodejs
전체 코드는 길어서 github로 대체합니다.
데모는 여기
  • javascript를 이용한 binary tree구현
    • node를 구현, left와 right 자식엘리먼트의 주소와 엘리먼트를 저장할 data로 구성
    • tree에는 root를 가르키며, 이후 subtree을 가르키며 트리를 구성
      • javascript에서는 object(객체)에 대해서는 call by reference로 작동된다.
  • binary tree의 특징
    • 탐색시간이 log n(밑2) 이다.
    • 한 node의 subtree는 2개 이하이다.
      • 구현에서는 정렬을 위해, 
        • 왼쪽 노드는 부모노드 보다 작은 값을,
        • 오른쪽 노드는 부모 노드보다 큰 값을 넣는다.
  • 위와 같은 방식을 사용할 경우 문제,
    • 트리의 균형이 보장되지 않는다.
  • 해결방법
    • avl, red black 트리 등이 있다.
  • 삽입,
    • case 1. root가 비어있을 경우
      • root에 값을 넣는다.
    • case 2. root(node)에 값이 있을 경우
      • 1-1) 값을 비교하여 작을 경우 왼쪽 노드를 따라 간다.
      • 1-2) 값을 비교하여 클 경우 오른쪽 노드를 따라간다.
      • 2-1) 해당 위치가 비어 있지 않다면 case 2를 반복한다.
      • 2-2) 해당 위치가 비어 있다면 값을 넣어준다.
        • 부모노드의 해당 위치에 노드를 연결한다.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
tree.prototype.add = function(element,node){
 //루트 부터 시작
 var node = node||this.root;

 //루트가 null, 즉 트리가 비어있을 경우
 if(this.root == null){
  this.root = new NODE(element);
 }

 //루트가 비어있지 않을 경우
 else{
  if(element<node.data){
   if(node.left == null){
    node.left = new NODE(element);
   }
   else{
    this.add(element,node.left);
   }
  }
  else if(element>=node.data){
   if(node.right == null){
    node.right = new NODE(element);
   }
   else{
    this.add(element,node.right);

   }
  }
 }

 console.log("-------------------------------------------------------------");
 console.log("insert ",element);
 console.log("-------------------------------------------------------------");
 this.print();
}

  • 탐색
    • 1. 찾으려는 값과 root(node)와 값을 비교한다.
    • 2-1) 작을 경우 왼쪽 node를 따라간다.
    • 2-2) 클 경우 오른쪽 node를 따라간다.
    • 3. 같은 값이 나올때까지 1-2를 반복한다. 가르키는 노드가 비어있다면 null를 비교한다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
tree.prototype.search = function(element, node){
 var node = node||this.root;

 target = null;
 if(node.data == element){
  target = node;
 }
 else if(element < node.data){
  target = this.search(element,node.left);
 }
 else{
  target = this.search(element,node.right);
 }

 return target;

}

  • 삭제
    • 해당 노드를 찾는다. 이때 부모 노드도 기억한다.
      • stack을 이용하여 찾으려는 노드의 모든 경로를 기억한다.
      • 부모노드는 stack의 top에 해당하는 노드의 바로 아래에 위치해 있을 것이다.
    • case 1, subtree가 없을 경우
      • 부모노드로부터 해당 노드를 삭제한다.
    • case 2, subtree가 1개 이상일 경우 후보를 찾는다.
      • 해당 노드 자리에 후보노드를 대체한다.
------------

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
tree.prototype.search2 = function(stack,element,node){
 var node = node||this.root;
 stack.push(node);

 if(node.data == element){
 }
 else if(element < node.data){
  this.search2(stack,element,node.left);
 }
 else{
  this.search2(stack,element,node.right);
 }
}


tree.prototype.del = function(element,node){
 node = node||this.root;
 // console.log(target);
 console.log("-------------------------------------------------------------");
 console.log("del "+element);
 console.log("-------------------------------------------------------------");

 target = null;
 parent = null;
 selected_node = null;
    

 var S = new stack();
    this.search2(S,element);
    // S.print();
    target = S.pop();
    parent == null;
    if(!S.isEmpty()){
     parent = S.pop();
    }

 this.renewDH(target);

 left_parent = target;
 left_node = target.left;
 if(left_node){
  while(left_node.right){
   left_node = left_node.right;
  }
 }

 right_parent = target;
 right_node = target.right;
 if(right_node){
  while(right_node.left){
   right_parent = right_node;
   right_node = right_node.left;

  }
 }

 left_depth = left_node==null?0:left_node.depth;
 right_depth = right_node==null?0:right_node.depth;



 if(target.height == 1){
  if(parent == null){
   this.root = null;
  }
  else if(parent.left == target){
   parent.left = null;
  }
  else{
   parent.right = null;
  } 
 }
 else if(left_depth>right_depth){
  selected_node = left_node;
  selected_parent = left_parent;
  if(left_depth == 1){
   selected_node.right = target.right;
   if(parent == null){
    this.root = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
  else if(left_depth >= 2){
   selected_parent.right = selected_node.left;
   selected_node.left = target.left;
   selected_node.right = target.right;
   if(parent == null){
    this.root  = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
 }

 else if(left_depth<=right_depth){
  selected_node = right_node;
  selected_parent = right_parent;
  if(right_depth == 1){
   selected_node.left = target.left;
   if(parent == null){
    this.root = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
  else if(right_depth >= 2){
   selected_parent.left = selected_node.right;
   selected_node.left = target.left;
   selected_node.right = target.right;
   if(parent == null){
    this.root  = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
 }

    this.print();

}

  • 후보노드
          • 이것은 만드는 사람이 정하기 나름!
    • 왼쪽 방향
      • 해당노드의 left node를 시작으로 right node가 null일 경우 까지 계속 따라 내려간다.
    • 오른쪽 방향
      • 해당노드의 right node를 시작으로 left node가 null일 경우 까지 계속 따라 내려간다.
    • 두 노드 중에 depth가 큰 노드를 후보노드로 선정한다.

  • 구현에 있어서의 특징,
    • javascript의 특성상 closure의 특징 때문에 height를 구하는 점에 있어서 문제가 생긴다.  (node_left, node_right의 값이 recursive하며 계속하여 달라진다.)
      • 이를 해결하기 위해 stack를 사용함.
    • 출력에 있어서 깊이 우선 탐색을 하여 높은 노드부터 순차적으로 출력하도록 하였다. 부모노드 부터 순차적으로 기록하기 위해 queue를 사용하였다.




코드는 길어서 github로 대체합니다.
아래 github또는 블로그 내에 다른 linked list, stack, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure
작성자: 시간: 댓글 없음:
라벨: , , , , ,

2015년 4월 19일 일요일

[data structure javascript] Linked List


  • 실행환경 : nodejs

  • javascript를 이용한 linked list구현
    • node를 구현, 단순 linked list 이기 때문에 다음 느드를 가르키는 next와, 엘리먼트를 저장할 data로 구성
    • node를 출력하면 다음 노드, 다음 노드의 다음노드, 다음 노드의 다음 노드의 다음 노드..... 쭈욱 출력이 되지만, 실제로는 객체 값이 저장되는 것이 아니라 주소를 가르키고 있다.
      • javascript에서는 object(객체)에 대해서는 call by reference로 작동된다.
  • linked_list의 특징
    • 노드로 구성
    • 노드에는 값과 다음 값에 대한 주소를 가지고 있다.
  • 장정
    • 크기에 제한을 가지고 있지 않다.
    • 중간 삽입, 삭제가 array에 비하여 쉽다.
    • 삽입, 삭제에 대한 비용이 적다. O(1)
    • 때문에 c,c++ 등에서 자료구조를 구현할때 linked list를 주로 활용한다.
  • 단점
    • 탐색에 있어서 단방향이다.
    • 탐색에 대하여 비용이 크다. O(n)
    • 때문에 삽입,삭제 에 있어서 이전 노드의 주소(객체)의 정보를 가지고 있어야 한다.
    • 이중 연결 리스트가 방안이 될 수 있다.
  • linked list용어
    • node
      • 하나의 객체로, 값과 다음 값으로 이루어 져 있다.
  • 자매품
    • 환영 연결 리스트
    • 이중 연결 리스트
  • 삽입 방법
    • 삽입 할 노드의 앞의 노드를 찾는다. (이전노드)
    • 이전 노드의 next의 주소를 삽입할 노드의 next로 넣는다.
    • 이전 노드의 next의 주소를 삽입할 노드의 주소를 넣는다.

  • 삭제 방법
    • 삽입 반대로.





  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
var linkedList = function(){
 this.length = 0;
 this.headNode = new node(null);
}


var node = function(element){
 this.data = element;
 this.next = null;
}

linkedList.prototype.add = function(element,position){
 
 //position이 null일 경우 마지막위치로
 var position = position==undefined?this.length+1:position;
 
 //입력값으로 node 생성

 var newNode = new node(element);

 var preNode = this.headNode;
 for(i = 1;i<position;i++){
  preNode = preNode.next;
 }
 newNode.next = preNode==null?null:preNode.next;
 preNode.next = newNode;

 this.length++;

 // console.log("-------------------------------------------");
 // console.log("add",element);
 // console.log("position",position);
 // console.log("-------------------------------------------");
 // this.print();
}

linkedList.prototype.remove = function(position){

 var ret = null;
 var position = position==undefined?0:position;
 if(this.isEmpty()){
  console.log("list is Empty");
 }
 else if(position<this.length){
  var preNode = this.headNode;

  for(i = 0;i<position;i++){
   preNode = preNode.next;
  }
  ret = preNode.next.data;
  preNode.next = preNode.next.next;
  
  this.length--;
 }
 else{
  console.log("index error");
 }

 // console.log("-------------------------------------------");
 // console.log("position",position);
 // console.log("remove",ret);
 // console.log("-------------------------------------------");
 // this.print();
 return ret;
}


linkedList.prototype.peek = function(position){

 var ret = null;
 var position = position==undefined?0:position;
 if(this.isEmpty()){
  console.log("list is Empty");
 }
 else if(position<this.length){
  var preNode = this.headNode;

  for(i = 0;i<position;i++){
   preNode = preNode.next;
  }
  ret = preNode.next.data;

 }
 else{
  console.log("index error");
 }

 return ret;
}

linkedList.prototype.print = function(position){
 var str = "linkedList : ";
 var node = this.headNode.next;
 while(node != null){
  str += node.data;
  str += " -> ";
  node = node.next;
 };
 console.log(str);
}


linkedList.prototype.isEmpty = function(){
 var ret = false;
 if(!this.length){
  ret = true;
 }

 return ret;
}

// list = new linkedList();

// list.add(1);

// list.add(2);

// list.add(3);

// list.add(3,1);

// list.add(1);

// list.remove();
// list.remove(3);

아래 github또는 블로그 내에 다른 tree, stack, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure
작성자: 시간: 댓글 없음:
라벨: , , , , ,

[data structure javascript] Stack

  • 실행환경 : nodejs
  • javascript를 이용한 stack 구현
    • 배열의 구조,api를 활용
    • javascript의 약한 언어의 특징 때문에 쉬운 구현이 가능
      • 때문에 크기에 제한을 두지 않는다.(메모리 크기까지 가능)
      • javascript의 array 메소드에 push, pop을 활용하여 간단한 구현을 하였습니다.
  • stack의 특징
    • last in first  out, first in last out 특징
    • 인터럽트, tree의 전위 순회 등에 쓰인다.
      • (제 tree의 구현에 사용했습니다.)
  • stack용어
    • push(,= put)
      • 삽입, stack의 맨 위에 해당 엘리먼트를 삽입한다.
    • pop(,= get)
      • 삭제, stack의 맨 위에 해당하는 엘리먼트를 리턴, 삭제한다.
    • top
      • 맨 위의 값, push한 값, pop이 될 값이 된다.
    • buttom
      • 맨 아래, top == buttom이라면 stack이 비었음을 의미한다.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
var stack = function(){
 this.datas = [];
}


stack.prototype.isEmpty = function(){
  return this.datas.length==0?true:false;
}
stack.prototype.length = function(){
 return this.datas.length;
}
stack.prototype.push = function(element){

 this.datas.push(element);
 // console.log("-------------------------------------------------------------");
 // console.log("push ",element);
 // console.log("-------------------------------------------------------------");
 // this.print();

}
stack.prototype.pop = function(){
 element = this.peek();
 this.datas.pop();
 // console.log("-------------------------------------------------------------");
 // console.log("pop!");
 // console.log("return",element);
 // console.log("-------------------------------------------------------------");
 // this.print();
 return element;
}
stack.prototype.peek = function(){
 element = this.datas[this.datas.length-1]==undefined?null:this.datas[this.datas.length-1];
 return element;
}
stack.prototype.toArray = function(){
 return this.datas;
}
stack.prototype.print = function(){
 var tmp = this.datas;
 for(i=tmp.length-1;0<=i;i--){
  console.log("│ "+this.datas[i]+" │");
 }
 console.log("└---┘");
}

stack.prototype.delAll = function(){
 this.datas = [];
}

// S = new stack();

// S.push(3);
// S.push(5);
// S.push(1);
// S.push(6);

// S.pop();

// S.pop();

// S.push(9);
// S.push(8);

module.exports = stack;


아래 github또는 블로그 내에 다른 tree, linked list, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure
작성자: 시간: 댓글 없음:
라벨: , , , , ,
피드 구독하기: 글 (Atom)