코드노예

먼저 min.io 는 무엇인가? 그리고 어디에 쓰면 좋은가? 에 대해서 살펴보도록 하겠습니다.

https://min.io/

홈페이지에 따르면, min.io는 (aws) S3와 호환되는 고성능의 오브젝트 스토리지 라고 소개하고 있습니다. 즉, 스토리지 서비스를 구축하는데 사용할 수 있는 오픈 소스 솔루션 입니다. S3와 사용법이 거의 유사하게 되어 있어서, S3를 써 보셨던 분들은 매우 쉽게 사용이 가능하며, 스토리지를 처음 써보시는 분들은 약간의 적응이 필요합니다.

서비스를 시작하는 방법은 여러가지가 있지만, 저는 docker를 사용해서 서비스를 시작해 보겠습니다. (docker 설치 필요)

min.io 서비스를 시작하기 위해서는 docker를 사용하면 되는데, min.io 에서는 podman 커맨드를 제시하고 있어서 혼선을 주고 있습니다. podman 을 별도로 설치하기 귀찮아서 docker-compose.yml 파일을 아래와 같이 작성해 보았습니다.

version: '3'
services:
  s3:
    image: minio/minio
    ports:
      - 9000:9000
      - 9001:9001
    environment:
      MINIO_ROOT_USER: admin
      MINIO_ROOT_PASSWORD: changeme
    volumes:
      - ./storage/minio:/data
    command: server /data --console-address ":9001"

서비스 명은 편의상 s3로 하였습니다. 그리고, docker에서 사용할 image 를 지정해 주었고 (minio/minio), 서비스에서 사용될 포트를 매핑해 주었습니다. (9000, 9001)

환경변수로 user, password 를 지정해 주었으며, volume을 지정하여 재시작을 해도 기존에 저장했던 스토리지 정보가 남을 수 있게 해 주었습니다.

시작 커맨드는 버전에 따라 약간씩 상이하다고 하니, 추후에는 변경이 될 수도 있습니다.

커맨드 윈도우에서 아래 명령어를 이용해서 서비스를 시작합니다.

> docker-compose -f docker-compose.yml up -d

도커 컨테이너가 제대로 실행되어 돌아가면, 브라우저를 열어서 http://localhost:9000 으로 접속을 시도합니다.

요청은 http://localhost:9001로 redirect 되며, 아래와 같은 admin 페이지 로그인 창이 뜹니다.

위의 docker-compose.yml 파일에 설정했던, username, password 를 이용해서 로그인을 합니다.

로그인을 하면, 아래와 같은 화면이 나옵니다.

위의 화면에서 우측 상단의 Create Bucket 버튼을 클릭해서 Bucket을 생성해 봅니다.

Bucket Name 에 'test'를 입력하고, Create Bucket 버튼을 클릭하여 bucket을 생성합니다. 제대로 생성되면 아래와 같은 화면이 나오게 됩니다.

생성된 bucket 에 파일을 드래그해서 업로드 해 봅니다. 아래와 같은 화면이 나오면서 파일이 올라간 것이 화면에 표시됩니다. 업로드 버튼을 클릭해서 폴더도 생성할 수 있고, 파일을 업로드 할 수도 있습니다.

업로드 된 파일을 클릭해보면, 화면 우측에 파일을 다운로드, 공유, 삭제하거나 정보를 확인 할 수 있는 창이 나타납니다.

Share 아이템을 클릭하면 아래와 같이 특정 기간 동안 유효한 URL을 생성하여 파일을 공유할 수 있습니다.

이번 시간에는 docker를 이용해서 min.io 서비스를 설치하고, bucket을 생성하고, 간단하게 파일 업로드 및 공유 기능에 대해서 살펴 보았습니다. 다음 시간에는 node.js를 이용해서 프로그래밍으로 bucket 을 관리하고, 파일 업로드 및 다운로드를 하는 예시를 살펴 보겠습니다.

지난 포스트에서는 https 를 적용하기 위해서, 실제 인증기관을 통해서 서명된 인증서를 사용하는 방법에 대해서 적어 보았습니다.

하지만, 테스트 용도의 서버나 개발 서버 등 외부로 노출되지 않는 서버까지 유료 인증서를 사용할 필요는 없습니다. 이런 경우 self signed certificate 을 이용해서 적용할 수 있습니다.

1. 이전과 마찬가지로 private key 파일과 인증 요청서 파일을 생성하는 것입니다. 이번에는 nodes 옵션을 추가해서 암호 설정이 되지 않은 key 파일을 생성하겠습니다.

openssl req -newkey rsa:2048 -nodes -keyout domain.key -out domain.csr

2. 인증서를 생성합니다.

openssl x509 -signkey domain.key -in CSR.csr -req -days 10000 -out domain.crt

days 옵션에 숫자로 날짜를 입력할 수 있습니다. 해당 기간 동안 인증이 유효한 것인데, 테스트 용은 길게 적어 줘도 상관 없습니다.

3. key 파일과 인증서 (crt) 파일을 적당한 경로로 옮겨 둡니다.

4. nginx 설정에 다음 내역을 추가합니다.

server {
    listen 443 ssl;
    server_name your_domain.com;
    
    ssl_certificate '/etc/ssl/certs/domain.crt';
    ssl_certificate_key '/etc/ssl/certs/domain.key';
    
    ...
}

5. nginx 서버를 재시작 합니다.

위의 내용은 아래 사이트에서 참조하여 작성하였습니다.

https://www.baeldung.com/openssl-self-signed-cert#:~:text=A%20self%2Dsigned%20certificate%20is,the%20certificate%20isn't%20trusted

nginx 서버에 ssl을 설정하는 방법입니다.

ssl이란.. Secure Sockets Layer 의 약자로.. 쉽게 이야기해서 Security가 강화된 프로토콜입니다.

요즘 대부분의 웹사이트들은 https를 기본으로 적용하고 있습니다. https 를 사용하는 이유는.. 여러가지가 있겠지만.. 그 중에서도 가장 중요한 것은 보안 문제입니다. http 를 사용하게 되면.. 해당 사이트가 제대로 된 서버로 접속이 된건지.. 피싱 사이트인지 구분이 힘들지만, 제대로 된 https 인증서를 세팅한 사이트라면, 실제 회사의 사이트로 접속했다는 것을 인증서 발급 업체가 검증을 해주기 때문입니다. 그 외에 유저 전송 데이터를 암호화 하는 것도 반드시 필요하기 때문에 https가 권장되고 있습니다.

대부분의 웹서버들에서 ssl 설정을 할 수 있지만.. 오늘은 nginx 서버에 설정해 보겠습니다.

ssl 설정을 하기 위해서는 최종적으로 private key 파일과 인증서 파일이 필요합니다. 

먼저 private key 파일과 인증서 파일을 준비하는 과정입니다.

private key 파일이나 인증서 파일은 여러가지 형태(확장자)로 존재하기 때문에, 가장 기본이 되는 파일로 설명해 보겠습니다.

1. 암호화 된 private key 파일과 인증서 요청 파일을 생성합니다.

아래 명령어를 이용해서 생성합니다.

openssl req -newkey rsa:2048 -keyout PRIVATEKEY.key -out CSR.csr

private key 파일 (PRIVATEKEY.key) 과 인증서 요청 파일 (CSR.csr) 을 생성합니다. 여기서는 rsa 2048bits 로 생성했지만, 더 강화된 보안을 위해서 rsa:4096 등의 옵션을 사용할 수 있습니다.

생성시 private key 파일에 password 를 설정해야하며, 인증 요청을 위한 정보들 (국가, 지역 등등..) 을 입력해야 합니다.

private key 파일과 password 를 잘 보관해 둬야 합니다.

2. 인증서 요청 파일을 인증기관에 보내서 인증서를 발급 받습니다.

원래 인증기관은 인증을 해주는 기관이지만, 여기서는 ssl 인증서를 발급해 주는 회사라고 하겠습니다. GeoTrust 같은 곳이 유명하고, 그 외에도 cloudflare, sectigo(comodo) 등의 인증 기관에서 인증서를 발급 받을 수 있습니다. 인증 기관에 따라 서비스가 크게 차이가 나진 않지만 인증서 발급 가격은 다를 수 있습니다.

인증서는 전체 도메인에 대해서 받을 수도 있고, 특정 호스트 도메인에 대해서도 받을 수 있으며, 인증 기간에 따라서도 비용이 다르니 필요에 따라 발급 받으면 됩니다.

위에서 생성한 인증 요청 파일 (csr 파일)을 보내고, 비용을 내면, 인증서 파일 (pem, crt 등) 을 보내줍니다.

보통 인증기관에서는 요청 도메인에 대한 인증서와 체인 인증서등을 보내줍니다.

요청 도메인에 대한 인증서는 위에서 생성한 csr 에 대한 인증서입니다.

체인 인증서는 csr에 대한 인증서를 인증해준 인증기관들에 대한 정보라고 생각하면 됩니다. 즉, A라는 인증기관이 B를 인증해주고, B에서 csr에 대한 인증서를 발급해 준 것이라면, A-B 인증기관에 대한 인증서가 됩니다.

참고로 인증서는 하나의 파일에 여러 개의 인증 정보가 포함될 수 있습니다.

만약 체인 인증서에 요청한 인증서가 포함되지 않았다면, 아래 명령어로 인증서를 하나로 합칩니다.

(domain.crt 가 요청해서 받은 인증서, bundle.crt 가 인증 기관의 체인 인증서)

cat domain.crt bundle.crt > domain.chained.crt

3. 암호화된 private key 파일을 복호화합니다.

아래 명령을 이용하여 복호화합니다.

openssl rsa -in PRIVATEKEY.key -out domain.key

처음에 설정한 password 를 입력하면 domain.key 라는 복호화된 키 파일이 생성됩니다.

4. 파일을 적당한 위치에 위치시킵니다.

리눅스 서버를 기준으로 하면.. /etc/ssl/certs 같은 폴더에 인증서 파일을 보관합니다.

인증서 (domain.chained.crt) 와 private key (domain.key) 파일을 /etc/ssl/certs 폴더에 위치시킵니다.

파일을 읽기 전용으로 변환합니다. (optional)

chmod 400 domain.key
chomd 400 domain.chained.crt

nginx 설정 파일을 열어 다음과 같이 설정합니다.

# http 요청을 https URL로 redirect 시킨다.
server {
    listen 80;
    server_name your_domain.com;
    return 301 https://your_domain.com$request_uri;
}

server {
    listen 443 ssl;
    server_name your_domain.com;
    
    ssl_certificate      /etc/ssl/certs/domain.chained.crt;
    ssl_certificate_key  /etc/ssl/certs/domain.key;
    
    # 필요에 따라 ssl protocol 이나 cipher 등을 설정할 수 있음
    # ssl_protocols TLSv1.2 TSLv1.3;    
    # ssl_ciphers ...;
    # ssl_prefer_server_ciphers on;
    
    # 나머지 nginx 옵션
    ...
}

설정 후 nginx를 재시작 합니다.

재시작 후에는 아래 명령어로 nginx 설정을 확인해 봅니다.

nginx -t

위와 같이 설정하면 your_domain.com 으로 오는 요청에 대해서, http 요청은 https 로 리다이렉트 되고, https 요청은 브라우저의 루트 인증서와 사이트 인증서를 확인하고 나서, 브라우저에서 안전한 연결인지 알려주게 됩니다.

브라우저에서 자물쇠 표시가 제대로 나오고, 에러 메시지가 없으면 잘 처리 된 것입니다. 

(아래는 네이버 사이트 https 연결 체크)

요약

1. key 파일과 인증서 요청 파일을 생성한다.

2. 인증서 요청 파일을 가지고 인증기관에서 인증서를 받아온다.

3. key 파일 (decrypt 필요), 인증서 파일 (체인 인증서) 을 준비해서 적당한 위치에 둔다.

4. nginx 설정에 key와 인증서 등을 세팅하고 리스타트 한다.

많이 사용되는 파일 확장자를 간략히 정리하면 다음과 같습니다.

• .key : private key. (.p8 혹은 .pkcs8을 쓰기도 함) encrypted 된 파일도 있고, decrypted 된 파일도 있습니다. encrypted 파일의 경우 decrypt 하기 위해서는 암호가 필요합니다.
• .csr : 인증 요청서 파일. (.req 혹은 .p10을 쓰기도 함) 이것을 인증 기관으로 보내서 인증서를 받습니다. (보통은 파일 형태로 보내지 않고, 그 내용만 복사해서 폼에 붙여 넣습니다.)
• .crt : 인증서 파일. (.cer 을 쓰기도 함) 체인 인증서일 수도 있음.
• .der : 바이너리 형태의 인증서. (.cer 을 쓰기도 함)
• .pem : 컨테이너 파일. 컨테이너 라는 것은 안에 무언가 내용을 담을 수 있다는 의미이며, base64로 인코딩된 내용이 들어갑니다. 내용은 key가 될 수도 있고, 인증서가 될 수도 있습니다. (즉, 어떤 내용이 담겨있는지는 생성한 쪽에서 알려줘야 합니다.)
• .p7b 혹은 .p7c : PKCS#7/CMS 메세지. private key 를 제외한 인증서 혹은 체인 인증서를 담기 위해 사용됩니다.
• .pfx 혹은 .p12 : PKCS#12 파일. 키 스토어 컨테이너로 보통은 암호화 된 private key 와 인증서를 같이 담기 위해 사용됩니다.

각 포맷간 변환 참조 (소스: https://myonlineusb.wordpress.com/2011/06/19/what-are-the-differences-between-pem-der-p7bpkcs7-pfxpkcs12-certificates/)

# PEM to DER
openssl x509 -outform der -in certificate.pem -out certificate.der

# PEM to P7B
openssl crl2pkcs7 -nocrl -certfile certificate.cer -out certificate.p7b -certfile CAcert.cer

# PEM to PFX
openssl pkcs12 -export -out certificate.pfx -inkey privateKey.key -in certificate.crt -certfile CAcert.crt

# DER to PEM
openssl x509 -inform der -in certificate.cer -out certificate.pem

# P7B to PEM
openssl pkcs7 -print_certs -in certificate.p7b -out certificate.cer

# P7B to PFX
openssl pkcs7 -print_certs -in certificate.p7b -out certificate.cer
openssl pkcs12 -export -in certificate.cer -inkey privateKey.key -out certificate.pfx -certfile CAcert.cer

# PFX to PEM
openssl pkcs12 -in certificate.pfx -out certificate.cer -nodes

이번에는 request 할 때, 서버로 데이터를 전송하는 것에 대해서 알아보겠습니다.

먼저 데이터를 전송하는 방법에 대해서 정리해 보겠습니다.

클라이언트에서 서버로 http를 이용해서 데이터를 전송하는 방법은 크게 3가지가 있습니다.

1. Query string

2. URI parameter

3. request body

Query string 은 request 뒤에 [key]=[value] 형식으로 값을 붙여서 전달하는 방식입니다.

ex) 

curl "http://localhost:5000?key=value"

두 개 이상 값을 전송할 때는 key, value 셋 사이에 &를 사용합니다.

curl "http://localhost:5000?key1=value1&key2=value2"

URI parameter는 URL에 값을 넣어서 호출하는 방식으로, 서버쪽에서 URL을 parsing 해서 사용합니다.

ex)

category 에 food 라는 값을 전송

curl http://localhost:5000/category/food

category1 에는 food, category2 에는 fruit 전송

curl http://localhost:5000/category1/food/category2/fruit

request body 의 경우는 POST method를 이용해서 데이터를 추가로 전송합니다.

ex)

form 전송

curl -X POST http://localhost:5000 -d 'key1=value1&key2=value2'

json 데이터 전송 (header 정보가 필요합니다.)

curl -X POST http://localhost:5000 -H "Content-Type: application/json" -d '{"key1":"value1", "key2":"value2"}'

각각에 대해서 flask 서버에서 처리하는 방법은 다음과 같습니다.

먼저 Query string 을 처리하는 방법입니다. 

request.args.get(<key>) 를 이용해서 값을 받아 올 수 있습니다.

@app.route("/query")
def query_test():
    return ("<br>".join( map(lambda key: '{}={}'.format(key, request.args.get(key)), request.args) ))

테스트를 위해서는 아래와 같이 path 를 query로 지정합니다. 

curl "http://localhost:5000/query?key=value"

URI parameter 를 처리하는 방법입니다.

route annotation path에 parameter들을 <> 를 이용해서 세팅합니다. 

method에 해당 parameter를 인자로 받아서 처리합니다.

@app.route("/category1/<category1>/category2/<category2>")
def uri_test(category1, category2):
    return "<p>Category1: {} <br>Category2: {}</p>".format(category1, category2)

아래 처럼 호출을 하면,

curl http://localhost:5000/category1/food/category2/fruit

 category1 은 food, category2 는 fruit 이 들어오는 것을 확인할 수 있습니다.

request body로 오는 정보는 request.form, request.json 혹은 request.data 으로 처리할 수 있습니다.

form은 데이터가 query string 과 같이 <key>=<value> 형식으로 오는 경우 처리가 가능합니다.

json은 header에 Content-Type 을 application/json 으로 지정해주고, body가 json 포맷으로 되어 있는 경우 처리가 가능합니다.

마지막으로 data는 클라이언트에서 보내주는 binary 데이터를 그대로 받아올 수 있습니다.

먼저 method 를 POST 로 지정해 줍니다. 

form의 경우는 method를 지정해 주고, 위의 query에서 사용한 request.args 를 request.form 으로 변경해 주기만 하면 됩니다.

참고로 query 혹은 form 에 대해서 방식에 관계없이 처리하는 경우에는 request.value 를 이용할 수 있습니다. query 와 form 모두 같은 키로 데이터를 보낸 경우 query가 우선합니다.

@app.route("/form", methods=['POST'])
def form():
    return ("<br>".join( map(lambda key: '{}={}'.format(key, request.form.get(key)), request.form) ))

json의 경우 request.json 을 이용하면 됩니다.

import json

...

@app.route("/json", methods=['POST'])
def json_test():
    return json.dumps(request.json)

테스트 할 때는 header를 지정해야 합니다.

curl -X POST http://localhost:5000 -H "Content-Type: application/json" -d '{"key1":"value1", "key2":"value2"}'

이번에는 request 에 대해서 알아보겠습니다.

먼저 HTTP 요청 방식은 GET, POST, PUT, PATCH, DELETE 등이 있습니다.

이것은 하나의 convention 으로, 클라이언트에서 요청할 때 method 를 지정하며, 서버쪽에서는 method 에 맞게 response 를 구현해 주면 됩니다.

curl 을 이용해서 테스트를 해 보겠습니다. 

참고로 -X 옵션을 따로 지정하지 않으면 GET method 로 요청을 합니다. 

GET 방식으로 요청

> curl -X GET http://localhost:5000

GET 요청에 대한 리턴

<p>Hello World</p>

POST 방식으로 요청

> curl -X POST http://localhost:5000

같은 url 을 요청했는데, POST 방식에서는 다음과 같이 리턴이 왔습니다.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<title>405 Method Not Allowed</title>
<h1>Method Not Allowed</h1>
<p>The method is not allowed for the requested URL.</p>

내용을 살펴보면 해당 method 를 지원하지 않는다고 합니다.

이슈를 해결하기 위해서 이전에 작성한 app.py 코드를 다음과 같이 수정해 봅니다.

from flask import Flask

app = Flask(__name__)

@app.route("/test")
def path_test():
    return '<p>test</p>'

@app.route("/", methods=['GET', 'POST'])
def hello_world():
    return '<p>Hello World</p>'

"/" 경로에 method 를 추가해 준 것입니다.

변경 후 재 실행 하면 POST 요청에 대한 리턴도 GET 과 같은 것을 확인 할 수 있습니다.

이번에는 method 에 따라 다른 결과를 보내주는 코드를 작성해 보겠습니다.

요청을 구분하기 위해서는 request.method 사용합니다. 

먼저 request 를 import 해주고, 아래처럼 분기하면 요청 method 에 따라 다른 결과가 리턴 됩니다.

from flask import Flask, request

app = Flask(__name__)

@app.route("/test")
def path_test():
    return '<p>test</p>'

@app.route("/", methods=['GET', 'POST'])
def hello_world():
    if request.method == 'GET':
        return '<p>GET: Hello World</p>'
    elif request.method == 'POST':
        return '<p>POST: Hello World</p>'

지난번 포스트에서는 기본적인 서비스를 시작해 보았습니다.

이번 포스팅부터는 윈도우 환경에서 실행되며, 포트는 default인 5000번을 사용한다고 가정하고 진행하겠습니다.

이번에는 경로를 추가해 보겠습니다.

app.py 파일을 열어서 아래와 같이 편집합니다.

from flask import Flask

app = Flask(__name__)

@app.route("/test")
def r_test():
    return '<p>test</p>'
    
@app.route("/")
def hello_world():
    return '<p>Hello World</p>'

flask 앱을 다시 실행하고, 웹브라우저에 다음과 같이 입력합니다.

http://localhost:5000/test

그러면 화면에 test라고 나옵니다.

flask 앱에 test 라는 경로가 추가되었습니다.

따라서 원하는 경로를 추가하려면, @app.route 에 경로를 지정하고, 바로 method 를 구현해 주면됩니다.

여기서 method 이름은 크게 중요하진 않지만, 다른 method 이름과 중복되지 않게 적어 주셔야 합니다.

만약 같은 경로를 중복해서 지정하면 어떻게 될까요?

아래와 같이, 같은 경로(/test)에 여러 개의 method를 구현하면, 제일 처음에 나오는 r_test()가 실행됩니다.

from flask import Flask

app = Flask(__name__)

@app.route("/test")
def r_test():
    return '<p>test</p>'

@app.route("/test")
def r_test2():
    return '<p>test2</p>'

@app.route("/")
def hello_world():
    return '<p>Hello World</p>'

Python Flask를 이용해서 REST 서비스를 구현해 보겠습니다.

먼저 Python 3.x가 설치되어 있다고 가정하고 진행해 보겠습니다.

Python 의 가상환경을 이용할 예정이며, 테스트 환경은 Windows 10 이지만, OS 의 영향이 거의 없을 듯 합니다.

Python 의 가상환경은 가상으로 isolated 된 실행 환경을 생성해 주며, 각 환경 별로 다른 모듈을 설치하여 실행할 수 있게 해줍니다.

프로젝트 실행 위치를 myApp 폴더라고 가정하겠습니다.

명령프롬프트를 사용해서 해당 위치로 이동후에 아래 명령어로 가상환경을 생성합니다.

> python3 -m venv venv

마지막의 venv는 가상환경이 생성되는 경로이기 때문에 원하시는 폴더로 변경해서 지정할 수 있습니다.

가상환경을 실행합니다. (윈도우)

> venv\Scripts\activate

맥OS나 리눅스에서는 다음과 같이 실행합니다.

$ source venv/bin/activate

참고로 가상환경을 종료할 때는 deactivate 명령어를 입력하면 됩니다.

실행후에는 명령프롬프트 앞쪽에 가상환경에 대한 정보가 나타납니다.

(venv) >

Flask 모듈을 설치합니다.

(venv) > pip3 install flask

간단한 Flask 앱을 만들어 보겠습니다.

먼저 app.py 파일을 생성해서 편집기로 열고 다음과 같이 입력합니다.

from flask import Flask

app = Flask(__name__)

@app.route("/")
def hello_world():
    return '<p>Hello World</p>'

그리고 가상환경의 명령프롬프트에서 다음과 같이 입력합니다. (윈도우)

> set FLASK_APP=app
> flask run

맥OS나 리눅스라면 다음과 같이 입력합니다.

$ export FLASK_APP=app
$ flask run

실행시키면 어떤 포트에서 실행 중인지에 대한 정보가 화면에 나타납니다.  참고로 default 는 5000포트인데, 맥에서는 AirPlay Receiver 서비스가 해당 포트를 사용중이기 때문에, 서비스를 중지시키거나 다른 포트를 사용해야 합니다.

Monterey 에서 서비스 중지시키는 방법:

System Preferences > Sharing > AirPlay Receiver 체크 해제

포트 지정은 -p 옵션을 사용합니다.

$ flask run -p 4999

웹 브라우저를 열어 아래 주소를 입력해서 결과를 확인해 봅니다.

http://localhost:5000 

브라우저에 Hello World 라고 나오면 성공입니다.

이번에는 LIS 에 대해서 알아보겠습니다.

LIS는 원소가 증가하는 순서대로 배치 했을 때, 가장 긴 배열의 길이를 구하는 문제입니다.

예를 들어 [1, 5, 2, 3, 10] 이라는 배열이 있다면,

증가 순서대로 배치 했을 때, 가장 길게 나오는 경우는 [1, 2, 3, 10]이 되므로, 이 경우의 답은 4가 됩니다.

기본적인 접근법은, 자신보다 작은 수의 원소를 카운트할 수 있는 버퍼(dp)를 생성하고, 중첩루프를 돌며 자신보다 작은 수의 원소에 대해서 현재 카운트와 작은 수의 원소의 카운트 + 1을 비교해서 큰 값을 취하고, 최종결과에서 최대값을 리턴하면 됩니다.

위의 예시에 대해서 과정을 살펴보면,

먼저 자기 자신은 모두 1로 세팅합니다.

[1, 1, 1, 1, 1]

1에 대해서 나머지 모든 원소들이 1보다 크기 때문에 dp[i] (= 1) 과 dp[0] + 1 (= 2)를  비교해서 더 큰 값인 2를 취합니다.

[1, 2, 2, 2, 2]

5에 대해서 같은 방법을 적용하면, 5보다 큰 10에 대해서만 dp[1] + 1 (= 3) 으로 바뀝니다.

[1, 2, 2, 2, 3]

2에 대해서 같은 방법을 적용하면, 10의 경우 이미 3이었는데, dp[2] + 1 (= 3) 이기 때문에 변화가 없습니다.

[1, 2, 2, 3, 3]

3에 대해서 같은 방법을 적용하면,

[1, 2, 2, 3, 4]

dp 의 최대 값은 4이기 때문에, 가장 긴 증가 순서의 길이는 4가 됨을 알 수 있습니다.

위의 알고리즘을 코드로 구현하면 다음과 같습니다.

def lengthOfLIS(nums):
    arrLen = len(nums)
    dp = [1] * arrLen
    ret = 0
    for i in range(arrLen):
        for j in range(i+1, arrLen):
            if (nums[i] < nums[j]):     
                dp[j] = max(dp[j], dp[i] + 1)
                if (dp[j] > ret):
                    ret = dp[j]
    return ret

이 경우 시간 복잡도는 O(n^2) 이 됩니다.

조금 더 효율적인 방법으로는 배열을 순회하며, 값이 증가하는 경우에는 그대로 값을 추가해주고, 값이 감소하면 그 값을 기존에 찾아둔 배열에서 해당 값보다 큰 수들 중에 가장 작은 값의 위치에 대입해주면서 추가된 개수를 리턴하면 됩니다.

위의 예시에 대해서 과정을 살펴보면,

배열의 첫번째 원소를 추가합니다.

[1]

다음 원소를 체크해 보면, 이전에 추가한 원소(1) 보다 크기 때문에 증가 순서에 추가 합니다.

[1, 5]

다음 원소는 2 인데, 2는 이전에 추가한 원소(5) 보다 작기 때문에, 리스트에 추가하지 않고, 기존 리스트에서 2보다 큰 수들 중에서 가장 작은 값(5)를 2로 대체합니다.

[1,2]

다음 부터 나오는 숫자들 (3, 10) 은 순서대로 증가하기 때문에 하나씩 추가해 주면 됩니다.

[1,2,3]
[1,2,3,10]

최종적으로 총 4번 추가했기 때문에, 길이는 4가 됩니다.

이 알고리즘은 길이를 구하기 위해서 최적화 된 알고리즘 이기 때문에, 배열에 들어가 있는 값은 실제 순서와는 다를 수 있습니다.

예를 들어, [1, 5, 6, 7, 8, 2, 3, 4] 라는 배열로 적용해 보면, 최종 수행 결과는 [1, 2, 3, 4, 8]가 되는데, 실제로 가장 긴 배열은 [1, 5, 6, 7, 8] 이기 때문입니다. 

위의 알고리즘을 코드로 구현하면 다음과 같습니다.

def lengthOfLIS(nums):
    arrLen = len(nums)
    dp = [nums[0]]
    dpLen = 1
    for i in range(1, arrLen):
        if (dp[-1] == nums[i]):
            pass
        elif (dp[-1] == nums[i]):
            dp.append(nums[i])
            dpLen += 1
        else:
            l = 0
            r = dpLen - 1
            while(l < r):
                mid = l + (r - l) // 2
                if (dp[mid] < nums[i]):
                    l = mid + 1
                else:
                    r = mid
            dp[l] = nums[i]
    return dpLen

이 알고리즘의 시간 복잡도는 O(n log n) 이 됩니다.

마지막으로 LIS의 길이가 아닌, 해당 원소들을 찾는 방법에 대해서 살펴보면, 기존 코드에서 dp에 값 대신 해당 원소의 인덱스를 저장하고, 값이 추가될 때, 해당 원소의 바로 앞이 어떤 값인지를 저장하는 버퍼(prevIdx)를 추가해서 처리하면 됩니다.

def lengthOfLISEx(nums):
    arrLen = len(nums)
    prevIdx = [-1] * arrLen
    dp = [0]
    dpLen = 1
    for i in range(1, arrLen):
        if (nums[dp[-1]] == nums[i]):
            pass
        elif (dp[-1] < nums[i]):
            prevIdx[i] = dp[dpLen - 1]
            dp.append(i)
            dpLen += 1
        else:
            l = 0
            r = dpLen - 1
            while(l < r):
                mid = l + (r - l) // 2
                if (nums[dp[mid]] < nums[i]):
                    l = mid + 1
                else:
                    r = mid
            prevIdx[i] = dp[l - 1]
            dp[l] = i

    currIdx = dp[-1]
    ans = [nums[currIdx]]
    while prevIdx[currIdx] != -1:
        ans.append(nums[prevIdx[currIdx]])
        currIdx = prevIdx[currIdx]
    return ans[::-1]