2번째, 프림 알고리즘

개념은 이해가 되는데 코드로 구현한거는 이해가 안됬다.

그래서 수기로 순서대로 정리를...


import sys;

N = 7;

s = 0;

g = [None] * N # size 를 설정하기 위해서


g[0] = [(1,9), (2,10)];

g[1] = [(0,9), (3,10), (4,5), (6,3)];

g[2] = [(0,10),(3,9),(4,7),(5,2)];

g[3] = [(1,10),(2,9),(5,4),(6,8)];

g[4] = [(1,5),(2,7),(6,1)];

g[5] = [(2,2),(3,4),(6,6)]

g[6] = [(1,3), (3,8), (4,1), (5,6)];

visited = [False] * N

D = [sys.maxsize] * N #?????


D[s] = 0

previous = [None] * N;

previous[s] = s


if __name__ == '__main__':

 for k in range(N):

  m = -1

  min_value = sys.maxsize;

  print("k is %d" %k);

  for j in range(N):

   print("j in %d" %j);

   print("outter D[j] is %d" %D[j]);

   if not visited[j] and D[j] < min_value:

    print("D[j] is %d" %D[j]);

    min_value = D[j]

    m = j

  visited[m] = True

  

  for w, wt in list(g[m]):

   print("w : %d, wt : %d" %(w, wt));

   if not visited[w]:

    if wt < D[w]:

     print("if  wt :%d, D[w] : %d" %(wt, D[w]))

     print("previo", previous[w]);

     D[w] = wt

     previous[w] = m

     print("afeter pri", previous[w]);

    

 print("min tree", end = '');

 mst_cost = 0;

 for i in range(1, N):

  print("(%d, %d)" %(i, previous[i]), end='');


이 코드의 핵심은 방문리스트와 이전리스트를 활용하는 것이다.

방문이 되는 것은 최소 가중치로 선정이 됬을때이다.

이전 리스트는 가중치가 무한에서 자기가 갖고 있는 값으로 업데이트 됬을때 된다

이 장에선 여러가지 알고리즘을 배운다

이러한 알고리즘의 핵심은 최단 경로 혹은 최소 가중치로 신장트리를 만드는 것.

네비게이션이나 경로 탐색 등 다양한 분야에서 실제로 사용된다고 한다.


1. kruskal 알고리즘.

최소 신장트리를 만드는 것


if __name__ == '__main__':

 weights = [(0,1,9), (0,2,10), (1,3,10), (1,4,5), (1,6,3), (2,3,9), (2,4,7), (2,5,2), (3,5,4,), (3,6,8),(4,6,1),(5,6,6)]

 weights.sort(key = lambda t:t[2])

 mst = []

 N = 7

 p = []

 check = 0;  

 

 for i in range(N):

  p.append(i);

  

 def find(u):

  print("find", u)

  if u != p[u]:

   print("inner find", u, p[u]);ㅎ

   p[u] =find(p[u]);

  print("find p[u] : %d" %p[u]); 

  return p[u]

  

 def union(u,v):

  root1 = find(u)

  root2 = find(v)

  print("root1 :%d, root:%d" %(root1, root2));

  p[root2] = root1;

  print("p[r2] : %d, r1:%d" %(p[root2],root1))

  

 tree_edges = 0;

 mst_cost = 0;

 while True:

  if tree_edges == N-1:

   break;

  print("check", weights)

  u,v,wt = weights.pop(0);

  print("not if check", u, v, wt)

  if find(u) != find(v):

   print("check", u, v, wt)

   print("ch", p);

   union(u,v)

   mst.append((u,v))

   mst_cost += wt;

   tree_edges += 1

   

  

 print("최소 신장트리 :", end = '');

 print(mst)

 print('최소 신장트리 가중치 :', mst_cost)


코드는 위와 같다.

이 알고리즘의 핵심은 union-find 이다.

가중치로 정렬을 했기 때문에 제일 위부터 아래로 연결을 해주면 되는데

문제는 이 정점들이 싸이클이 되는지 확인하는 것이다.

그렇기에 이 싸이클 여부를 확인하는 것은 해당 정점의 최상 루트가 무엇인지를 파악 해주면 된다.

예를 들어 1-2, 2-3, 3-4, 4-5 이렇게 연결 되어 있는 경우에 5번 노드가 2,3번에 연결이 안되는 이유는 2,3의 최상 루트가 1번이기 때문이다.

재귀적 방식을 통해서 제일 위의 루트를 찾는것, 그리고 그것이 다를때만 연결을 해주는 것이 핵심이다.(이를 위해 p라는 임의의 리스트를 형성)

var express = require('express'), http = require('http'),

    path = require('path');

var router = express.Router();

// 라우터 객체 생성!

var ErrorH =  require('express-error-handler');

// 오류페이지 보내기 위한 핸들러 선언

var cookieParser = require('cookie-parser');

var expressSession = require('express-session');

var app = express();

var errh = ErrorH({

    static :{

        '404' : './public/404.html'

    }

});

app.use(ErrorH.httpError(404));

app.use(errh);

app.use(cookieParser());

app.use(expressSession({

    secret : 'my key',

    resave:true,

    saveUnintialized:true

}));

router.route('/process/product').get(function(req,res){

        console.log('product 호출');

        if(req.session.user){

            res.redirect('/public/product.html');

        }else{

            res.redirect('/public/login2.html');

        }

    });

router.route('/process/showCookie').get(function(req, res){

        console.log('/process/showCookie 호출');

        res.send(req.cookie);

        });

router.route('/process/setUserCookie').get(function(req,res){

    console.log('setuser 호출');

    res.cookie('user', {

        id :'mike',

        name :'sosi',

        authorized:true

    });

    res.redirect('/process/showCookie');

});


router.route('/process/login/').post(function(req,res){

    console.log('process/login check');

    var paramName = req.params.name;

    // 얘는 토큰이라 부른다.

    var paramId = req.body.id||req.query.id;

    var parPass = req.body.pass || req.query.pass;

    console.log('process/login check222');

    if(req.session.user){

        console.log('already login');

        res.redirect('/public/product.html');

    }else{

        console.log('process/login check333');

        req.session.user={

        id : paramId,

        name :'sosi',

        authorized:true

        };

    

    res.writeHead('200', {'Content-Type':'text/html;charset = utf8'});

    res.write('<h1> express server answer');

    res.write('<div><p>Param Name : ' +paramName + '</p></div>');

    res.write('<div><p>Param id :'+paramId + '</p></div>' );

    res.write('<div><p>param pass :' + parPass + '</p></div>');

    res.write(

    "<br><br><a href ='/public/login2.html'>go back</a>");

    res.end();

    }

});

router.route('/process/logout').get(function(req,res){

    console.log('logout');

    if(req.session.user){

        console.log('go logout');

        req.session.destroy(function(err){

            if(err){throw err;}

            console.log('session des');

            res.redirect('/public/login2.html');

        });

    }else{

        console.log('not yet login');

        res.redirect('/public/login2/html');

    }

});


var bodyParser = require('body-parser'), static = require('serve-static');

// static 미들웨어 불러오기


var app = express();

app.set('port', process.env.PORT||3000);


app.use(bodyParser.urlencoded({extended:false}));

// body-parser 활용

// application//www-xxx-xxx 주소를 파싱

// 즉 폴더안에 있는 페이지의 주소를 연결해줌!!

app.use(bodyParser.json());

// bp를 이용한 application/json 파싱

// 내용을 파밍하는듯?

app.use(static(path.join(__dirname, 'public')));

// 폴더명을 연결해줌!!

// public만 해주나?


app.use('/', router); //router을 app 객체에 등록


http.createServer(app).listen(3000, function(){

    console.log('server start');

});



이 부분은 서버 실행 + 로그인 + 세션 유지 파트이다.

기본적으로 특정 페이지 접속시 세션유무를 파악하여

세션이 있으면 페이즈를 응답하고

없으면 로그인 할 수 있도록 유도한다


근데 문제는 session 에러가 계속 뜸

TypeError: Cannot read property 'user' of undefined

분명 세션 사용과 if else를 통해 세션이 없을경우 저장 까지 할 수 있게 해놨는데

실행이 안된다.


내일 더 봐야할듯..

'Node.Js 도전(임시 마감)' 카테고리의 다른 글

Do.it과 함께하는 Node.js 5장  (0) 2018.04.30

+ Recent posts