Hack your life

[Javascript] 마니또 알고리즘(리스트 셔플 List shuffle)

가끔 오프라인으로 종이뽑기로 하면 본인을 뽑는 경우도 있는데 마니또는 본인 말고 다른 사람을 뽑는 알고리즘입니다.

O(n^2)이라 좋은 알고리즘은 아닌거 같은데 다른 방법을 생각해내지 못했습니다.

 A, B, C, D, E 5명이 서로 다른 사람을 뽑게 하려면 A부터 순서대로 1~5번까지의 숫자를 뽑는데 1번을 제외한 숫자를 뽑도록 했습니다.

우선 랜덤한 숫자를 먼저 뽑는데 0부터 4의 숫자가 랜덤하게 추출됩니다.(while문 조건중 i == temp 를 빼면 리스트 셔플이 될 것입니다.)

while(i == temp || result.includes(temp))

이 조건은 자기 자신을 뽑지 않고 이미 뽑힌 사람은 뽑지 않는 조건이고, 자기 자신이거나 result에 숫자가 있을 경우엔 True가 되므로 False가 될 때까지 반복 추출을 합니다.

이 코드에선 추출 결과를 저장하기 위해 DB에 Insert 하도록 했습니다.

다른 아이디어가 있으시면 댓글로 남겨주세요!ㅎㅎ

[Nginx] 포트 리다이렉트, Proxy_pass 설정하기

Nginx 설치하기

Nginx를 이용하면 ip:port와 같이 특정 포트로의 연결을 리다이렉트 해줄 수 있다.

우선 nginx의 설치와 명령어는 아래와 같다.

 설치
$ sudo apt-get install nginx

버전 확인
$ nginx -v

 시작
$ sudo service nginx start

재시작
$ sudo service nginx restart

중지
$ sudo service nginx stop

상태
$ sudo service nginx status

설정 reload
$ sudo service nginx reload

서버의 포트는 열려있다고 가정하겠다.

AWS를 사용하는 경우 인바운드 규칙으로 넣어줄 수 있다. 3001번 포트를 열었는데 nginx 설정을 마치면 지워도 된다.

Nginx 설정 파일 수정하기

경로를 확인하는 방법과 설정파일을 수정하는 명령어이다.

$ sudo find / -name nginx.conf

$ sudo vi /etc/nginx/nginx.conf

그리고 아래의 코드를 http{ } 안에 써주기만 하면 된다. 인터넷에 예제로 나온 conf 파일과 형식이 달라 처음에 조금 시행착오를 겪었지만 http{ 안에만 넣어주니 됐다. 

server { # simple reverse-proxy
                listen       80;
                server_name  domain.com;


                # pass requests for dynamic content to rails/turbogears/zope, et al
                location / {
                        proxy_pass      http://127.0.0.1:3001;
                }
        }

[AWS ec2] Node.js 설치하기

AWS linux ec2에서 node.js를 설치하는 방법은 아래와 같다.

1. SSH를 이용하여 Linux 인스턴스에 접속한다.

2. nvm 설치

curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.32.0/install.sh | bash

3. activate nvm

. ~/.nvm/nvm.sh

4. node js 설치(원하는 버전으로)

nvm install 4.4.5

nvm install stable(안정 버전-추천)

5. 설치확인

node -e "console.log('Running Node.js ' + process.version)"

[경영과학] 확률적 모형(Stochastic Model)

확률적 모형(Stochastic Model)

 확률적 모형은 미래에 대한 정보가 불확실하여 수학적 모형 내에 확률이나 확률분포가 포함되어 있느 모형을 말하며, 최적해보다는 근사해난 실행가능한 해를 찾는 데 초점을 맞춘다. 대표적인 예로는 재고모형, 대기행렬, 게임이론, 마코프분석, 시뮬레이션 모형 등이 있다. 확률적 모형은 확정적 모형에 비해 매우 복잡하여 해석적 방법을 적용하기에는 극히 제한적이며 이 모형을 분석하기 위해서는 시뮬레이션이 좋은 수단이 된다.

1) 의사결정이론(Decision Theory)

 의사결정이론(Decision Theory)은 미래의 불확실한 상황하에서 합리적인 의사결정을 하기 위해서 확률이론을 적용하여 해를 구하는 기법이다.

2) 게임이론(Game Theory)

  게임이론(Game Theory)은 게임에 참여하는 경쟁자와 경쟁자의 전략, 전략 선택에 따른 성과를 대상으로 하며 각 전략에 따른 게임이득의 최대화와 게임손실의 최소화를 위한 기법을 다룬다.

3) 재고관리모형(Inventory Model)

  재고모형(Inventory Model)은 주문비용과 재고비용의 총합을 최소화하는 의사결정문제를 다룬다. 이 접근방법은 구입주문비, 재고유지비, 재고부족비를 최소화핳는 주문정책 및 재고정책을 결정하는 데 적용된다. 이때 모형 내에 상수 매개변수가 주어지면 확정적 모형으로, 확률적 매개변수가 주어지면 확률적 모형으로 구분된다.

4) 마코프 분석(Markov Analysis)

  마코프 분석(Markov Analysis)은 다양한 의사결정 시스템을 확률이론에 입각하여 모형화하고 과거의 변화를 토대로 동적 성격을 파악하여 미래의 변화를 연속적으로 예측한다. 이 기법이 가장 잘 이용되는 분야는 마케팅에서의 상표결정문제이며 마코프 분석은 주식동향 예측분야에서도 많이 이용되고 있다.

5) 대기행렬모형(Queueing Model)

  대기행렬모형(Queueing Model)은 제한된 서비스시설의 대기행렬에서 서비스비용과 대기비용을 최소화할 수 있도록 서비스 수준을 결정하기 위한 방법을 다룬다. 대기행렬모형이 적용되는 예로는 개찰구, 고속도로 요금소, 은행창구, 대형마트 내 계산대, 터미널 등이 있다.

6) 시뮬레이션(Simulation)

  시뮬레이션은 실제 시스템의 속성, 형태 및 운영특성 등을 연구하고 이해하기 위한 모의실험 또는 모형의 동적 실험을 하는 기술적 의사결정방법이다. 의사결정문제의 최적해를 얻기 위하여 시행착오적 방법과 확률이론을 사용한다.

참고 : 최적 의사결정을 위한 경영과학, 권수태 외 5인, 청람

[경영과학] 확정적 모형(Deterministic Model)

확정적 모형(Deterministic Model)

확정적 모형은 미래에 대한 정보가 확실하여 수학적 모형 내에 확률이나 확률분포가 포함되어 있지 않은 모형을 말하며, 비교적 쉽게 최적해를 구할 수 있다. 대표적인 예로는 선형계획법, 수송계획법, 네트워크모형, 목표계획법, 정수계획법, 동적계획법 등이 있다. 확정적 모형의 대부분은 해석적 방법을 이용하여 최적해를 구할 수 있다.

1) 선형계획법(Linear Programming: LP)

 사용 가능한 자원의 양이 제약된 상황하에서 총이익을 최대화하거나 총비용을 최소화하기 위한 자원의 최적 할당을 다룬다. 선형계획법의 해를 구하는 방법으로는 그래프를 이용한 도해법(Graphical Method) 및 선형대수학에 기반한 심플렉스법(Simplex Method)이 있다. 선형계획법은 경영과학 기법에서 가장 대표적인 기법이다.

2) 수송모형과 할당모형

  선형계획법의 특수형태를 갖는 알고리즘인 수송계획법과 할당법은 선형의 특수한 문제를 다룰 때 유용한 기법이다. 공급지에서 수요지로 제품의 물량을 최소비용으로 이동시킬 수 있는 최적 대안선택문제와 기계에 작업자 배치, 부서에 신입사원 배치 등에 관한 최적 할당 문제에 직면했을 때 수송모형과 할당모형이 적용된다.

3) 네트워크모형

  네트워크모형은 공간적, 지리적 위치나 시간적 상태를 나타내는 마디(node)와 이것을 연결하는 호(arc)에 의해 표현되는 네트워크문제를 다루는 모형으로 최소걸침나무문제(Spanning Tree Problem), 최단경로문제(Shortest Path Problem), 최대흐름문제(Maximal Flow Problem), 최소비용 네트워크흐름문제(Minimum Cost Network Flow Problem) 등이 예이다. 의사결정자가 대규모 프로젝트에 포함된 제품생산 순서와 계획기간 단축문제를 처리하는 데 이용되기도 하며, 예로는 PERT/CPM(Program Evaluation and Review Technique/Critical Path Method) 기법이 있다.

4) 목표계획법

  단일 목적함수만 고려하는 선형계획법과 달리, 목표계획법(Goal Programming)은 상충되는 다수의 목적을 동시에 고려하여 해를 구하기 위해 개발된 접근 방법이다. 목적함수의 편차변수를 최소화하고, 목적함수에는 우선순위의 목표에 가중치가 부여되고 제약조건에는 목적제약조건과 시스템 제약조건이 도입되어 도해법과 심플렉스법에 의해 최적해를 유도할 수 있다.

5) 정수계획법

  정수계획법(Integer Programming)은 의사결정문제에서 정수해를 필요로하는 선형계획모형의 해를 구하기 위해 적용되며 선형계획법의 해가 정수단위로 나올 수 있도록 정수제약조건을 도입하여 정수해를 유도한다. 분단탐색법(Branch and Bound Method)은 순수 또는 혼합 정수계획문제나 할당문제를 효과적으로 해결하기 위해서 개발된 하나의 순차적 반복계산방식이다.

6) 동적계획법

  동적계획법(Dynamic Programming)은 최적화문제에 대한 순환적 접근방법으로서 일련의 의사결정이 계획적으로 요구되는 상황에서 상화관련성을 지니는 상태변수(State Variable)를 매개로 최적화문제를 여러 단계(stage)로 분할하여 순차적으로 해를 구해 가는 다단계 의사결정 또는 문제해결을 위해 사용되는 수리적 기법이다.

7) 비선형계획법

  현실세계의 실제적인 의사결정문제들은 선형함수만으로 모형화하는 것이 불가능할 수 있으며 비선형 관계에 있는 것도 많다. 산출량과 투입량 간에는 수확체증 또는 수확체감의 법칙이 작용하는 경우에 비선형계획법(Nonlinear Programming)을 적용한다.

참고 : 최적 의사결정을 위한 경영과학, 권수태 외 5인, 청람

[엑셀 데이터 분석] 이항분포(binomial distribution) BINOMDIST

어떤 실험의 결과가 (성공, 실패) 또는 (합격, 불합격)과 같이 두 가지 결과 중 하나로 나타나는 경우의 시행을 베르누이 시행(Bernoulli trial)이라고 하고 두 값 중 하나의 값을 취할 수 있는 확률 변수를 베르누이 확률변수라고 한다.

• 베르누이 시행 :

1. 각 시행의 결과는 성공(S) 또는 실패(F) 중의 하나로 나타난다.
2. 매 시행에서의 성공확률을 p=P(S)로 나타낸다면 실패확률 q=1-p이다. 따라서 p+q=1이 된다.
3. 각 시행은 독립이다.  즉, 한 시행에서의 성공 여부가 다음 시행의 성공확률에 영향을 미치지 않는다.

엑셀에서 이항분포의 확률계산은 BINOMDIST 함수를 이용한다.

• BINOMDIST(number_s, trials, probability_s, cumulative) :

    - number_s : 성공 횟수

    - trials : 독립 시행횟수

    - probability_s : 각 시행에서 성공확률

    - cumulative : 함수형태를 결정하는 논리 값 1이면 누적확률질량함수 값을 계산하고, 0 이면 확률질량함수 값을 계산한다.

예제 1

4개의 동전을 던질 때 나타나는 앞면의 수를 확률변수 X라 하면 X~B(4, 0.5)가 되고 나타난 앞면의 수가 x일 때의 확률은 다음과 같다.

엑셀 수식은 "=BINOMDIST(x, 4, 0.5, 0)" 를 입력하면 된다.

예제 2

어느 생산 공정의 불량률이 5%일 때, 이 공정에서 임의로 10개를 추출하였을 때 이 중에서 불량품이 3개 이상 포함될 확률은?

전체 확률 1에서 불량품이 2개 이하일 확률을 빼면 된다. 2개 이하일 확률은 누적확률질량함수(논리 값 1)을 사용해서 구할 수 있다.

= 1 - BINOMDIST(2, 10, 0.5, 1)

참조: 엑셀데이터분석, 한국방송통신대학교 출판문화원, 조신섭 외 3명 공저

[엑셀 데이터 분석] 포아송분포 POISSON

포아송분포는 사무실에 한 시간 동안 전화가 걸려 오는 횟수, 고속도로 상에서 하루 동안 발생하는 교통사고의 수와 같이 특정한 사건이 일어날 확률이 아주 작은 경우에 사용하는 확률 모델이다. 단위 시간 당 희귀 현상의 평균 발생 횟수가 m일 때 어떤 특정한 단위 동안 발생한 현상의 수를 확률 변수 X로 정의한다. 그러면 확률변수 X는 0, 1, 2, ...의 값을 취하고, 모수가 m인 포아송분포(poisson distribution)을 따른다. 

모수가 m인 포아송분포의 확률질량함수는 다음과 같다.

모수 m을 갖는 포아송분포의 평균과 분산은 다음과 같다.

엑셀에서 포아송분포의 확률계산은 POISSON 함수를 이용하는데, 구체적인 사용법은 다음과 같다.

• POISSON(x, mean, cumulative) :

참조: 엑셀데이터분석, 한국방송통신대학교 출판문화원, 조신섭 외 3명 공저

[확률분포] 확률변수, 확률질량함수, 확률밀도함수

확률변수는 크게 이산형 확률변수와 연속형 확률변수로 나눌 수 있다.

이산형은 책의 페이지당 오자의 수, 제품 한 상자에서 나온 불량품의 개수, 주사위를 5번 던질 때 짝수가 나오는 횟수 등과 같이 확률 변수가 취할 수 있는 값이 정수와 같이 유한하거나 셀 수 있는 값을 취하는 경우의 확률 변수이다.

연속형 확률변수는 사람의 키, 제품의 무게와 같이 정확한 값보다는 어떤 구간의 값을 취하는 형태에서 사용한다. 100명의 키를 조사해서 분포로 나타낼 때, 175.34는 몇 명 180.18은 몇 명 이렇게 나타내지 않고 170~175cm 몇 명(n/S)와 같이 구간으로 나타낸다. 여기서 표본 공간에서 조건을 만족하는 원소의 개수를 구하면 확률이다.

동전던지기를 4번 해서 뒷면이 나올 확률은 아래와 같다.

위의 표에서 p(x) = P{X, x}는 확률변수 X가 취할 수 있는 값에 대해 확률을 대응시킨 관계를 나타내며 확률 분포 또는 분포함수라고 한다.

이산형 확률변수의 분포함수는 이산점의 확률을 나타내므로 도수 분포 그래프로 나타내진다. 그리고 분포함수 p(x)를 확률질량함수라고 부른다. 

연속형 확률변수의 확률분포는 확률변수 X가 어떤 구간에 속할 확률을 나타내므로 면적이 확률이 된다. 연속형 분포함수는 흔히 f(x)로 나타내고 확률밀도함수라고 부른다. 확률변수 X가 구간 (a, b)에 속할 확률 P(a< x <=b)는 곡선의 구간 (a, b) 면적이 된다. 

특정 조건을 만족하는 이벤트의 확률을 구할 때, 이산형 확률은 더하고, 연속형 확률은 적분한다. 

참조: 엑셀데이터분석, 한국방송통신대학교 출판문화원, 조신섭 외 3명 공저

[선형대수] 너무 쉬운 고유값(eigenvalue)과 고유벡터(eigenvector)

고유값과 고유벡터의 의미는 나중에 설명하기로 하고 아래의 행렬 곱을 보자.

계산 결과 값에 어떤 값을 곱해서 원래의 111행렬을 만들 수 없다.

이번엔 1 1 0 행렬을 곱해보자.

이 경우엔 결과 값에 1/3을 곱해서 1 1 0을 만들 수 있다.

여기서  

에서 3이 고유값이고 이 고유벡터이다.

정의

n x n 행렬 A가 있을 때 아래의 식을 만족하는 는 고유값, X는 고유벡터이다.

이식을 방정식 형태로 쓰면 

 이 된다. 고유벡터는 영이 아닌 벡터로 정의 되어있으므로 x의 계수행렬이 특이행렬이어야 한다.

 는 A의 특성방정식(characteristic equation)이라고 부른다.

이 방정식을 풀면 고유값과 고유벡터를 구할 수 있다.

예제1

의 특성다항식은 아래와 같다.

그리고 행렬식 계산을 통해 구한 특성방정식은 아래와 같다.

방정식을 풀면 해는 2 또는 -1이다.

즉, A의 고유값은 2와 -1이다.

람다 2를 위의 식에 다시 대입하면,

이고

이 되어 의 관계를 얻는다. 이 방정식 계의 해는 r을 스칼라로 놓고 

로 나타낼 수 있다. 즉 에 대응하는 고유벡터는  의 형태인 영이 아닌 벡터가 된다.

마찬가지로 을 대입하면 형태의 고유벡터를 구할 수 있다. (s는 스칼라)

마코프체인(Markov chain)

마코프체인은 과거의 상태와 현재 상태가 주어질 때, 미래 상태의 조건부 분포는 과거 상태에는 독립이고 오직 현재 상태에만 종속한다.

예를 들어보자,

1. 날씨 예측

 내일 비가 올 가능성은 오직 오늘 비가 오는지 안 오는지에만 종속하고 과거의 날씨에는 종속하지 않는다고 가정한다. 또한, 오늘 비가 올 때 내일 비가 올 확률은 a이고 오늘 비가 오지 않을 때 내일 비가 올 확률은 b라고 가정하자.

비가 올 때는 상태를 0이라고 하고 비가 오지 않을 때는 상태를 1이라고 하면, 이 과정은 다음의 전이확률을 갖는 2-상태 마코프체인이 된다.

2. 확률 과정을 마코프체인으로 변환하기

오늘 비가 올지의 여부가 과거 날씨 중 최근 이틀의 날씨에만 영향을 받는다고 가정하자. 

1. 지난 이틀 동안 비가 왔으면 내일도 비가 올 확률은 0.7이다.

2. 어제는 비가 오지 않고 오늘 비가 왔다면 내일 비가 올 확률은 0.5이다.

3. 어제는 비가 왔지만 오늘은 오지 않았다면 내일 비가 올 확률은 0.4이다.

4. 지난 이틀 간 비가 오지 않았다면 내일 비가 올 확률은 0.2이다. 

상태 0 : 오늘과 어제 모두 비가 옴

상태 1 : 오늘 비가 오고 어제는 안 옴

상태 2 : 어제 비가 오고 오늘은 안 옴

상태 3 : 어제와 오늘 모두 비가 안 옴

위 상태는 다음과 같은 전이확률 행렬을 갖는 4-상태 마코프체인을 나타낼 것이다.

3. 랜덤보행 모형

상태공간이 정수로 주어진 마코프체인이 어떤 상수 0<p<1에 대해 다음 관계를 만족하면 랜덤보행(random walk)라고 말한다.

이 마코프체인이 랜덤보행이라고 불리는 이유는, 직선 위를 걷고 있는 사람이 각 시점마다 확률 p로 오른쪽으로 한걸음 가든 1-p의 확률로 왼쪽으로 한걸음 가는 것에 대한 모형으로 볼 수 있기 때문이다. (무한도전에서 위에서 공 떨어뜨리면 중간에 막대에 맞고 아래로 내려가는 복불복 게임이랑 비슷한 것 같다. 사진은 못 찾음 ㅎㅎ)

4. 인구이동 모델

2007년에 미국의 도시에 살고 있는 사람의 수는 8천2백만이고 주변 교외에 살고 있는 사람의 수는 1억6천3백만으로 추정된다. 이 정보를 행렬 로 나타내자. 

2007년 인구 흐름은 도시에 그대로 머물 확률은 0.96이었고 교외로 이사 갈 확률은 0.04였다. 거꾸로 교외에서 도시로 이주할 확률은 0.01이었고 교외에 남아 있을 확률은 0.99였다. 이 확률을 원소로 하여 확률행렬 P를 다음과 같이 쓸 수 있다.

       도시 교외(에서)  (로)

2008년도의 인구는 행렬 곱으로 얻을 수 있다.

행렬 P로 표현된 인구흐름이 매년 변하지 않는다고 가정하면, n년 후의 인구 분포는,

로 나타낼 수 있다. 즉, 

 이고 은 n-단계 전이행렬로 불린다.

사실 인구 인구이동의 확률행렬 P는 매년 같다고 하기 어려운 점이 있다. 그래서 인구 이동 보다는 유전 법칙이 마코프체인을 적용하기에 적절하다고 생각한다.