윈도우 환경에선 아래의 주소에서 .zip 또는 .msi 파일을 다운받아 설치 가능하다. 참고로 64비트만 지원한다고 한다.

https://github.com/MicrosoftArchive/redis/releases

 

MicrosoftArchive/redis

Redis is an in-memory database that persists on disk. The data model is key-value, but many different kind of values are supported: Strings, Lists, Sets, Sorted Sets, Hashes - MicrosoftArchive/redis

github.com

.msi 로 설치할 경우 

C:\Program Files\Redis 이 경로에 설치가 되며

redis-sever.exe 로 서버 실행이 가능하며 , redis-cli.exe로 클라이언트 실행이 가능하다.

.msi 로 설치 하면 바로 redis 서버가 실행이 되므로 본인이 확인하고 싶다면

관리자 권한 cmd로 들어가

net stop redis 명령어를 입력해 redis를 멈춘 뒤 redis-server.exe로 다 시실행하면 된다.

 

아주 간단한 명령어만 살펴본다.

>SET keyname "hello"
OK
>GET keyname
"hello"

set 을 통해 key와 value를 입력할 수 있고

get 을 통해 key의 value를 조회할 수 있다.

 

>TTL keyname
(integer) -1

TTL을 통해 key의 만료시간을 알 수 있다.

-1은 기한이 없는 것을 말하고 밀리초 단위로 반환한다.

 

>DEL keyname
(integer) 1

DEL 명령어를 통해 key를 삭제할 수 있고 삭제한 키의 개수를 반환한다.

 

>SET keyname "hello"
OK
>SET keyname2 "hello2"
> keys *
1) "keyname"
2) "keyname2"

keys pattern

*는 모든 키들 검색

keys 명렁어를 통해 모든 key들 또는 검색한 key들을 알 수 있으나, key가 많아지면 성능이 저하될 수 있으므로 현재 배포 중인 서비스에서는 사용하지 않는다.

(scan이라는 명령어를 사용함)

 

 

https://www.acmicpc.net/problem/12865

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.

www.acmicpc.net

 

Knapsack 알고리즘을 사용하면 풀리는 문제이다.

최근에 알고리즘 문제 풀이에 취미가 생겨 문제를 열심히 푸는 중인데, Knapsack 알고리즘을 봐도 이해가 안되어

나름 내 방식대로 이해하고 풀다 보니 Knapsack알고리즘과 똑같이 나왔다 ㄷㄷ.

 

주어진 개수 = n

주어진 무게 = weight

주어진 무게의 가치 = value

Knapsack 알고리즘은 전체 무게가 weight(주어진 무게)를 넘지 않도록 n 번째까지 항목 중에서 얻어진 최고 이익을

저장하여 Dynamic Programing으로 푸는 방식이다.

처음에 이게 무슨말인지 이해가 안되어 이해를 포기하고 그냥 내 생각대로 해보니 Knapsack알고리즘이 나왔는 데,

이 글 또한 그러한 사람들을 위해 작성 또는 내가 다시보려고 작성한 글이다.

 

문제에 나와있는 무게와 가치

6 13

4 8

3 6

5 12

말고

아래의 가치로 계산해보고 n(주어진 개수)=5 , WEIGHT(주어진 무게의 값)=15 라고 하자

weight value
1 1
2 2
3 3
4 4
5 5

 

5*15 로 2차원 배열을 잡는다. 실제로 생성할 땐 dp[n+1][value+1] 로 생성하자 dp[0][0~15]을 써야하기 때문.

또한. 값을 [1][1] 부터 집어넣자.

 

첫 번째 항목인

weight=1과 value=1을 먼저 계산한다.

 

weight=1과 주어진 무게의값 WEIGHT(15)까지 계산을 한다

계산은 각 열의 무게와 weight=1을 빼서 0보다 클경우 value를 집어 넣고

만약 작을 경우 그 이전의 값(바로 위의 행)을 집어넣는다. 그 이전의 값이란 것은 두번째 또는 세번째 항목부터 이해가 될 것이다.

 

현재 weight=1이고 첫 번째 열의 무게는 1이다 1-1>=0 이므로 1을 넣는다.

현재 weight=1이고 두 번째 열의 무게는 2이다 2-1>=0 이므로 1을 넣는다.

이런식으로 첫 번째 항목을 채운다

 

만약 첫 번째 항목의 weight=5라면 첫 번째 열에서는 1-5 >=0 이 아니므로 0을 넣는 데, 사실 0이라기보단 그 이전의 값(바로 위의 행)인 dp[0][1]값을 넣는 것이다. 두번째 또는 세번째 항목부터 이해가 될 것이다.

(행은 아이템 순번, 열은 무게)

두 번째 항목은 weight=2이고 value=2이다

 

현재 weight=2이고 첫 번째 열의 무게는 1이다 1-2>=0 이 아니다. 따라서 이 전의 값(바로 위의 행)을 넣어야한다.

이전의 값(바로 위의 행)은 dp[1][1]값인데 이는 즉, dp[n-1][j] 정도로 볼 수 있다.

 

현재 weight=2이고 두 번째 열의 무게는 2이다 2-2=>0 이므로 첫 번째 항목처럼 2를 넣는다라고 생각할 수 있지만

아니라 이전(바로 위의 행)의 값과 값을 비교해야한다.

이전(바로 위의 행)의 값은 1이고 현재 나의 값은 2이다 2가 더 크므로 2를넣는다.

 

현재 weight=2이고 세 번째 열의 무게는 3이다 3-2>=0 이고 3-2=1이다. 이제 남은 1의 값을 활용해야 한다.

이전(바로 위의 행)의 열을 사용한다. 

3-2=1 이기 때문에 이전 값(바로 위의 행)의 열은 1,1 -> dp[1][1]이다

현재 weight는 2이며, value=2이고 현재 열은 세 번째 열이다. 2, 3 -> dp[2][3]

현재 열은 이전 값(바로 위의 행)의 1번열의 값 + 현재 값 -> dp[2][3] = dp[1][1]+value -> dp[2][3]=1+2=3

dp[2][3]=3이란 것을 알 수 있다.

현재 weight=2일 때 세 번째 열의 무게가 3이라는 것을 알게 되었으면 이제 또 이전의 값(바로 위의 행)과 비교를 해야한다. 바로 위의행 dp[1][3]=1 이고 현재 dp[2][3]은 3이라는 것을 알고 3이 더크므로 3을 완전히 집어 넣는다.

 

이로써 규칙은

1. 먼저 그 열의 무게와 현재 항목의 무게를 빼고 무게가 0보다 큰지 확인한다. 

2. 0보다 작다면 이전의 값(바로 위의 행)값을 넣는다.

3. 0보다 크다면 현재 열의 무게와 현재 항목의 무게를 뺀 값을 더 한다.

더하는데 빼서 나온 값은 그 이전의 값(바로 위의 행에서 뺀 값의 열번째) 와 현재 항목의 가치를 더한다.

4. 값을 더했다면 이전의 값(바로 위의 행)의 값과 비교를 해 더 큰 값을 완전히 집어 넣는다.

 

이렇게 해서 두번째도 쭉 집어넣는다.

 

세 번째 항목은 weight=3이고 value=3이다

 

현재 weight=3이고 첫 번째 열의 무게는 1이다 1-3>=0 이 아니다. 따라서 이 전의 값(바로 위의 행)을 넣어야한다.

이전의 값(바로 위의 행)은 dp[2][1]값이다. 따라서 1을 넣는다

 

현재 weight=3이고 두 번째 열의 무게는 2이다 2-3>=0 이 아니다. 따라서 이 전의 값(바로 위의 행)을 넣어야한다.

이전의 값(바로 위의 행)은 dp[2][2]값이다. 따라서 2을 넣는다

 

현재 weight=3이고 세 번째 열의 무게는 3이다 3-3>=0 이다. 따라서 규칙대로 행동한다.

규칙의 3번인 0보다 크기 때문에 현재 열의 무게와 현재 항목의 무게를 뺀값을 더하는 데 3-3=0이다.

그리고 이 0의 값은 그 이전의 값( 바로 위의 행에서 뺀값의 열번째)는 dp[2][0]인데 이는 0이다.(dp[n+1][value+1] 로 잡았고 값을 [1][1]부터 잡았기때문에 0번쨰는 0으로 초기화 해준다.)

어쨋든 dp[2][0] + 현재 항목의 가치 -> dp[2][0]+3 -> 0+3 =3

그리고 규칙의 4번으로 와서 3과 그 이전의 값(바로 위의 행) dp[2][3]의 값과 비교해서 큰 값을 넣어준다. 둘이 값이 3으로 같기 때문에 3을 넣어준다.

 

현재 weight=4이고 네 번째 열의 무게는 4이다 4-3>=0 이다. 따라서 규칙대로 행동한다

규칙의 3번인 0보다 크기 때문에 현재 열의 무게와 현재 항목의 무게를 뺀값을 더하는 데 4-3=1이다.

그리고 이 1의 값은 그 이전의 값( 바로 위의 행에서 뺀값의 열번째)는 dp[2][1]인데 이는 1이다.

어쨋든 dp[2][1] + 현재 항목의 가치 -> dp[2][1]+3 -> 1+3 =4

그리고 규칙의 4번으로 와서 4와 그 이전의 값(바로 위의 행) dp[2][4]의 값과 비교해서 큰 값을 넣어준다. 

dp[2][4]=3이고 현재는 4이기 때문에 4가 더크므로 4를 넣어준다.

 

이런식으로 하다보면 아래의 값들이 나온다

 

 

이게 Knapsack알고리즘인데 이를 알고리즘적으로 풀이하면

dp[i][j] = Math.max(dp[i - 1][j], value[i] + dp[i - 1][j - weight[i]]);

이렇게 된다.

 

BOJ 12865 평범한 배낭 문제의 최종 소스는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		String T;

		T = br.readLine();
		st = new StringTokenizer(T);

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int weight[] = new int[N + 1];
		int value[] = new int[K + 1];
		int dp[][] = new int[N + 1][K + 1];
		for (int i = 1; i < N + 1; i++) {
			T = br.readLine();
			st = new StringTokenizer(T);
			weight[i] = Integer.parseInt(st.nextToken());
			value[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= K; j++) {
				if (j - weight[i] >= 0) {
					dp[i][j] = Math.max(dp[i - 1][j], value[i] + dp[i - 1][j - weight[i]]);

				} else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		System.out.println(dp[N][K]);
	}
}


Node.js에서 google oauth 인증하는 방법이다. 

이전에는 passport를 사용하지 않는 방법을 이용하여 JWT와 함께 쿠키로 로그인 인증처리를 했다면,

이번엔 세션을 이용하여 passport를 이용하는 방법이다.


기본적으로 https://console.cloud.google.com 에서 프로젝트를 생성했다는 가정하에 작성한다.


1. passport를 이용하지 않은 google oauth 인증 후 jwt 사용

2019/01/07 - [Develop/Node.js] - [Node.js] google oauth 인증 (구글 로그인)




1. 적당한 프로젝트를 생성 후 아래와 같은 명령어를 입력한다.


npm init
npm install express --save
npm install express-session --save
npm install session-file-store --save
npm install passport --save
npm install passport-google-oauth


express 를 사용할 것이기 때문에 express를 설치한다. 그리고 passport는 기본적으로 session을 이용하기 때문에 express-session도 설치하고

session 저장소를 파일로 처리할 것이기 때문에 session-file-store 를 설치한다.

그리고 사용할 passport와 passport의 전략중 하나인 passport-google-oauth를 설치한다.


※아래엔 express-session에서 파일로 세션을 저장하는 것 말고 데이터베이스 등을 사용하는 방법을 확인 할 수 있다.

https://www.npmjs.com/package/express-session

2. express를 설정하고 다음 session을 설정한다.


먼저 server.js 파일을 생성하고 아래와 같이 작성한다.


https://www.npmjs.com/package/express-session 에 접속해서 기본적인express-session을 사용하기 위해

아래 주석 //1의 미들웨어를 설정한다.

주석 //2번은 localhost:3000으로 접속할 때 나오는 기본 화면이다.

주석 //3은 express를 통해  3000포트를 이용하여 서버를오픈한다.

var express = require('express');
var session = require('express-session')
var FileStore = require('session-file-store')(session)
var app = express();

app.use(session({                // 1
    secret: 'keyboardcat',
    resave: false, 
    saveUninitialized: true,
    store: new FileStore()
}))

app.get('/', function (req, res, next) {    //2
    console.log('홈')
    
})


app.listen(3000, function () {            //3
    console.log('Example app listening on port 3000!');
});


3.  Google Cloud Platform 에서 Json 파일을 다운받고, config 폴더를 만든 뒤 다운받은 json 파일을 config폴더에 넣는다.


사진 맨 오른쪽 하단에 빨간줄로 표시한 아이콘을 클릭하여 json파일을 다운받는다.


다운받은 json 파일엔 기본적으로 아래와같이 나와있다.



이 파일을 아래 처럼 넣는다. 이유는 그냥 가져다 쓰는 것보다 저렇게 가져오는 것이 조금이나마 안전하기 때문.



4. passport를 설정한다.


4-1. passport 전략 중 하나인 우리가 사용할 passport-google-oauth를 사용한다.


server.js에 추가한다.

//1 아래와 같이 passport를 가져오고

//2 passport를 초기화시킨다.

//3 session을 이용하기 때문에 추가한다.

//4 실질적으로 로그인할 수 있는 경로와 scope이다. scope에서는 email이나 기타 정보를 가져 올 수도 있다.

//5 메인페이지에 4번에서 설명한 실질적으로 로그인하는 경로를 설정한다.

var passport = require('passport'),
      GoogleStrategy = require('passport-google-oauth').OAuth2Strategy;    //1

app.use(passport.initialize());    //2
app.use(passport.session());        //3

app.get('/auth/google',            //4
  passport.authenticate('google', { 
      scope: 'https://www.googleapis.com/auth/plus.login' }))

app.get('/', function (req, res, next)   {    //5
  
    var html = `
    login with google`
    res.send(html)
})


위와 같이 설정하고 'node server.js' 명령어를 통해 실행해서 접속하면 아래와 같은 화면이 뜬다.



4-2. 구글 로그인을 해서 정보를 얻어올 로직과 세션에 담을 로직을 구현한다.


//1 은 로그인했을 시 얻어오는 정보가아니라 그냥 임의로 넣었다 사실 이렇게 하는 것은 아니고 바로 아래에서 다시 설명할 예정

//2 로그인 성공하고 로그인 성공했을 때 가져오는 user.id를 세션에 설정한다.

//3 로그인이 성공했으면 페이지를 항상 새로 불러올 때마다 불러오는 것이다. 

그리고 세션에서 serialize에서 설정한 user id를 불러온 후 user 정보를 보여주는 것이다.

//4 아까 json파일에서 client_id와 secret, redirect uri를 불러온다.

//5 로그인이 성공했을 경우 scope를 설정한대로 구글측에서 profile 정보를 가져온다.


//5를 통해 로그인이 성공하면 scope에서 설정한 대로 profile에서 정보를 가져오는데 

성공적으로 가져왔으면 이를 done을 통해 정보를 설정하면

serializeUser로 가서 설정하고

설정된 값이 deserializeUser에서 불러온다.


다시말하자면 원래 var loginData를 설정하는 것이아니라

//5에서 일단 로그인 인증 처리를 한다 -> 데이터베이스에 넣거나, 데이터베이스에 있는 값을 가져와 회원이 맞는지 비교를 한다든지

이런 기본적인 로그인 처리를 설정하고. 이것이 통과된다면 done을 통해 정보를 return하면

//2의 serializeUser가 호출되는데 여기서 user.id ( 꼭 id가아니라 email이면 user.email도 가능) 을 session에 설정한다.

//3 그럼 페이지가 항상 호출될 때마다 deserializeUser가 호출 되는데 deserializeUser의 id를 통해

데이터베이스에 접속해서 이 아이디가 로그인이 된 상태라든지 이런 것들을 확인할 수 있다.

(너무 이상하게 설명한 것 같은데 이해가 되지않는다면 댓글에 적어주시면 감사하겠습니다.)


var config = require('./config/google.json')


var loginData = {        //1 id : 'test', pw : '1' } passport.serializeUser(function(user, done) {    //2 console.log('serialize', user); done(null, user.id); }); passport.deserializeUser(function(id, done) {    //3 console.log('deserialize', id); done(null, loginData) }); passport.use(new GoogleStrategy({                //4 clientID: config.web.client_id, clientSecret: config.web.client_secret, callbackURL: config.web.redirect_uris[0] }, function(accessToken, refreshToken, profile, done) {    //5 return done(null, loginData) } ));


4-3. 로그인이 정상 처리 되어 callback될 주소를 설정한다.


//1 Json파일의 redircet_uri를 설정한다 기본적으로 /auth/google/callback 이다.

//2 로그인이 정상 처리 된다면 //3의 redirect('/') 홈으로 가고 

실패하면 /bye로 보냈다. 이것은 다시 로그인 하는 곳으로 보낼 수 있고 처리하는 것은 개발자 마음이다.

//4 이것을 설정하지 않으면 세션이 스토어에 저장하는 데 오래걸릴 경우 리다이렉트를 시킬 수 있기 때문에 이를 방지하여

세션이 스토어에 저장이 완료되면 리다이렉트를 시키는 코드이다.

//5 로그인 실패시 보내는 주소이다.

//6 위에서 설정한 app.use(passport.session()) 미들웨어를 통해 req에서 user를 호출 할 수 있다. 

이것을 통해 deserilize가 호출 되는 것을 확인할 수 있다.


app.get('/auth/google/callback',     //1
passport.authenticate('google', {     //2
    failureRedirect: '/bye' 
    }),
    function(req, res) {                //3
        req.session.save(function(){     //4                              
          res.redirect('/');
        })
    });


app.get('/bye', function (req, res, next) {    //5
    res.send('login failed')
})

app.get('/', function (req, res, next) {
    console.log(req.user)        //6
    var html = `
    login with google`
    res.send(html)
})


5. 결과



node server.js 명령어를 통해 실행 후

login with google을 클릭하여 로그인을 하게되면

로그인이 성공하면 serialize를 호출하고 

페이지를 새로고침할 때마다 deserialize가 호출 되는 것을 볼 수 있다.



6. 전체 코드



var express = require('express');
var session = require('express-session')
var FileStore = require('session-file-store')(session)
var config = require('./config/google.json');
var app = express();

app.use(session({
    secret: 'keyboardcat',
    resave: false, 
    saveUninitialized: true,
    store: new FileStore()
}))

var loginData = {
    id : 'test',
    pw : '1'
}
var passport = require('passport'),
      GoogleStrategy = require('passport-google-oauth').OAuth2Strategy;

app.use(passport.initialize());
app.use(passport.session());

passport.serializeUser(function(user, done) {
    console.log('serialize', user);
    done(null, user.id);
  });
  
passport.deserializeUser(function(id, done) {
    console.log('deserialize', id);
    done(null, loginData)
  });


passport.use(new GoogleStrategy({
    clientID: config.web.client_id,
    clientSecret: config.web.client_secret,
    callbackURL: config.web.redirect_uris[0]
  },
  function(accessToken, refreshToken, profile, done) {
        return done(null, loginData)
    }
));

app.get('/auth/google',
  passport.authenticate('google', { 
      scope: 'https://www.googleapis.com/auth/plus.login' }))


app.get('/auth/google/callback', 
passport.authenticate('google', { 
    failureRedirect: '/bye' 
    }),
    function(req, res) {
        req.session.save(function(){    
                                       
            res.redirect('/');
        })
    });

app.get('/', function (req, res, next) {
    console.log(req.user)
    var html = `
    login with google`
    res.send(html)
})

app.get('/bye', function (req, res, next) {
    res.send('login failed')
})

app.listen(3000, function () {
    console.log('Example app listening on port 3000!');
});



참고 : 

https://www.npmjs.com/package/express-session 


+ Recent posts