먼저 debugger를 사용하기 위해서는 각 프로그래밍 언어에 맞는 debugger를 설치해 줘야 합니다. Node.js의 경우에는, 개발에 필요한 debugger가 내장되어 있기 때문에 별도의 설치가 필요 없지만, python 이나 java, C/C++ 등을 debug하기 위해서는 debugger를 설치해 주어야 합니다.
Debugger를 설치하고 vscode의 왼쪽 아이콘 중에 debug 아이콘을 클릭해 줍니다.
처음 실행시에는 debugger 설정 파일인 launch.json 파일이 없기 때문에, "create a launch.json file" 링크를 클릭해서 launch.json 파일을 생성합니다.
링크를 클릭하면 화면 가운데 상단에 아래와 같은 팝업이 나오게 되는데, Python Debugger를 선택합니다.
그리고 프로젝트에 맞는 템플릿을 선택합니다.
그러면 아래와 같은 launch.json 파일이 .vscode 폴더 안에 생성이 됩니다.
파일을 편집해서 아래와 같이 설정하였습니다.
아래 설정은 debug 실행시 Django App이 실행될 때, 아이피 주소는 0.0.0.0, 포트는 8000으로 바인딩을 해 주었고, debugger에 Django Shell 을 추가하여, 필요한 경우 django shell 실행을 할 수 있는 설정입니다.
{
// Use IntelliSense to learn about possible attributes.
// Hover to view descriptions of existing attributes.
// For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
"version": "0.2.0",
"configurations": [
{
"name": "Python Debugger: Django",
"type": "debugpy",
"request": "launch",
"program": "${workspaceFolder}\\manage.py",
"args": [
"runserver", "0.0.0.0:8000"
],
"django": true,
"autoStartBrowser": false
},
{
"name": "Python Debugger: Django Shell",
"type": "debugpy",
"request": "launch",
"program": "${workspaceFolder}\\manage.py",
"args": [
"shell"
],
"django": true,
"autoStartBrowser": false
}
]
}
debugger를 실행할 때는 debug 탭에서 실행할 debug 프로그램을 선택한 후에, 초록색 실행 (플레이) 아이콘을 눌러주면 됩니다. 참고로 위에 launch.json 에 설정했던 "configurations"."name" 이 선택 가능한 프로그램 이름으로 화면에 나오게 됩니다.
실행 후에는 필요한 위치에 break point 를 설정할 수 있으며, break point 가 설정되면, runtime 상황에서 해당 위치에서 실행이 중단되어, break point 시점에서 메모리에 올라가 있는 변수들의 실제 값을 확인해 볼 수 있습니다.
아래 화면에서 처럼 실행이 중단된 시점에서는, 왼쪽 상단의 VARIABLES 탭에서는 tree를 확장하여 각 변수들의 중단된 지점에서의 값을 확인해 볼 수 있으며, 왼쪽 아래에 있는 WATCH 탭에서는 변수명을 입력하거나 function, method 등을 호출해서 결과 값을 출력해서 볼 수 있습니다.
debugger가 실행되면 화면 어딘가에 나타나는 (보통 상단에 나타남) 아래와 같은 debug toolbar를 이용해서 컨트롤을 할 수 있습니다.
각각의 아이콘은 순서대로 다음의 동작을 수행합니다.
Continue (F5) / Pause (F6)
Continue: 다음 break point로 넘김 Pause: break point 시점에서 값을 확인
Step Over (F10)
현재 break point 위치에서 다음 줄로 break point 이동
Step Into (F11)
현재 break point의 위치가 method 혹은 subroutine 이라면 해당 method 혹은 subroution 의 첫째 줄로 break point 이동, 그렇지 않으면 다음 줄로 break point 이동
Step Out (Shift + F11)
현재 break point 기준으로 현재 method 혹은 subroutine 을 벗어나서 해당 method 혹은 subroutine이 호출되었던 곳으로 break point 이동
from django.urls import include, path
from . import views
urlpatterns = [
path("test/", views.test, name="name-test")
]
<app>/views.py
from django.urls import reverse
from django.http import HttpResponse
def test(reqeust):
return HttpResponse("Hello World!")
# using the named URL
# will return "index/"
reverse("name-test")
# passing a callable object
# will return "index/"
reverse(test)
@ url namespace - case 1
<app>/urls.py
from django.urls import include, path
from . import views
app_name = "poll"
urlpatterns = [
path("test/", views.test, name="name-test")
]
<app>/views.py
from django.urls import reverse
from django.http import HttpResponse
def test(reqeust):
return HttpResponse("Hello World!")
# using the named URL with app_name
# will return "index/"
reverse("poll:name-test")
include에 module 혹은 module name으로 매핑하는 경우에는 namespace는 <app>/urls.py 에 있는 app_name 이 우선 적용된다. 즉, <app>/urls.py 에 app_name 이 있으면 <app_name>:<path_name> 형식
ex) reverse("poll:name-test")
만약 <app>/urls.py 에 app_name이 없다면 <app_namespace>:<path_name> 이 된다.
ex) reverse("url_name_space:name-test")
@ url namespace - case 3
<config>/urls.py
from django.urls import include, path
from poll.urls import urlpatterns as poll_urlpatterns
urlpatterns = [
path("poll/", include((poll_urlpatterns, "url_name_space"))
]
include에 urlpattern 을 매핑하는 경우에는 <app>/urls.py 전체가 로딩되지 않고, <app>/urls.py/urlpatterns만 읽어서 등록하기 때문에, namespace는 <config>/urls.py 에 있는 app_namespace (여기서는 "url_name_space") 가 적용이 된다. <app_namespace>:<path_name> 형식
ex) reverse("url_name_space:name-test")
@ url in Django Template
Template 에서는 url 키워드를 이용해서 reverse와 같은 결과를 받아올 수 있다.
이번 포스트에서는 RSA 알고리즘에 대해서 알아보고, openssl 을 이용해서 RSA 키를 생성해보고, 몇몇 프로그래밍 언어에서 RSA 를 이용해서 encrypt / decrypt 하는 방법에 대해서 소개해 보겠습니다.
RSA 알고리즘
RSA 알고리즘은 비대칭키 알고리즘으로 두 개의 서로 다른 키를 사용해서 암호화와 복호화를 하는 방식입니다. 알고리즘을 개발했던 개발자들(Ron Rivest, Adi Shamir, Leonard Adleman)의 이름 이니셜을 따서 명명하였습니다. 자세한 알고리즘의 원리는 위키를 참고해 주세요.
이번에는 .net8.0 라이브러리 (System.Security.Cryptography)를 이용해서 데이터를 encrypt 하는 코드 샘플입니다. 참고로 .net5.0 이후는 같은 코드로 동작하지만 .netframework에서는 작동하지 않습니다.
encrypt는 public key를 사용하게 됩니다. 미리 public key를 준비해 둡니다. 저는 위에서 설명한 openssl로 생성한 pem 파일을 열어서 PUB_KEY라는 이름으로 문자열 형태의 리소스를 등록해 두었습니다.
using System.Security.Cryptography;
...
byte[] rsaEncrypt(byte[] encodeData)
{
byte[] ret = null;
// rsa 객체 생성
using (var rsa = RSA.Create())
{
// resource에서 pem 형식의 public 키를 가지고 옵니다.
var pubKeyStr = Properties.Resources.ResourceManager.GetString("PUB_KEY");
// public 키를 import 합니다.
rsa.ImportFromPem(pubKeyStr);
// 데이터를 encrypt 합니다.
ret = rsa.Encrypt(encodeData, RSAEncryptionPadding.OaepSHA256);
}
return ret;
}
RSA decrypt (with .net 8.0)
이번에는 .net8.0 라이브러리 (System.Security.Cryptography)를 이용해서 데이터를 decrypt 하는 코드 샘플입니다. 참고로 .net5.0 이후는 같은 코드로 동작하지만 .netframework에서는 작동하지 않습니다.
decrypt는 private key를 사용하게 됩니다. 미리 private key를 준비해 둡니다. 저는 위에서 설명한 openssl로 생성한 pem 파일을 열어서 PRI_KEY라는 이름으로 문자열 형태의 리소스를 등록해 두었습니다.
using System.Security.Cryptography;
...
byte[] rsaDecrypt(byte[] encodedData)
{
byte[] ret = null;
// rsa 객체 생성
using (var rsa = RSA.Create())
{
// resource에 저장된 private 키를 가지고 옵니다.
var priKeyStr = Properties.Resources.ResourceManager.GetString("PRI_KEY");
// private 키를 import 합니다.
rsa.ImportFromPem(priKeyStr);
// decryhpt 합니다.
ret = rsa.Decrypt(encodedData, RSAEncryptionPadding.OaepSHA256);
}
return ret;
}
RSA 코드 테스트
아래 코드를 이용하면, encrypt / decrypt 결과를 테스트 할 수 있습니다.
public void test()
{
string str = "Hello";
// encrypt string data - string을 byte[] 형태로 변경해서 전달
byte[] buf = rsaEncrypt(Encoding.UTF8.GetBytes(str));
// buf를 base64 string 형태로 출력
Debug.WriteLine(Convert.ToBase64String(buf));
// decrypt encrypted data
buf = rsaDecrypt(buf);
// buf를 string 형태로 출력
Debug.WriteLine(Encoding.UTF8.GetString(buf));
}
from django.contrib.auth import get_user_model
user = get_user_model().objects.get(username='<username>')
groups = user.groups.all()
cf. django.contrib.auth.models.User 를 이용해도 상관 없음
@ Group에 속한 User 리스트 가져오기
from django.contrib.auth.models import Group
group = Group.objects.get(name='<group_name>')
users = group.user_set.all()
@ User Group Check
from django.contrib.auth import get_user_model
user = get_user_model().objects.get(username='<username>')
# 유저가 특정 그룹에 속해 있는지 체크
user.groups.filter(name='<groupname>').exists()
# 유저가 그룹 리스트에 속해 있는지 체크
user.groups.filter(name__in=['<groupname1>', '<groupname2>']).exists()
# 유저 instance 없이 체크
get_user_model().objects.filter(username='<username>', groups__name='<groupname>').exists()
@ User Permission Check
# 유저가 가진 개별 permission 체크
user.user_permissions.filter(codename='<permission_code>').exists()
# 유저가 속한 그룹의 permission 체크
user.groups.filter(permission__codename='<permission_code>').exists()
Django 프로젝트를 배포하는 방법은 서비스 규모나 환경에 따라서 여러가지가 있겠지만..
여기서는 단일 서버에 docker를 이용하여 서비스를 운영한다고 가정을 하고 배포하는 상황을 준비하였습니다.
서비스 구성
기본적으로 source code는 git을 통해서 관리가 되고 있고, 서버에 docker는 이미 설치되어 있다고 가정하겠습니다. 실제 상황에서는 CI/CD 툴을 이용해서 관리하겠지만, 여기서는 Django 프로젝트를 배포하는 것에만 포커스 하도록 하겠습니다.
대략적인 서비스 구성은 아래 그림과 같습니다.
실제 서비스라면 database도 준비가 되어야겠지만.. 여기서는 docker에서 nginx와 python만 container를 띄울 예정입니다. 여기서 storage는 static 파일들이 들어갈 위치인데요, Django의 경우 운영환경에서는 django app은 wsgi (혹은 asgi) 형태로 서비스를 제공하며, static 파일들은 웹서버가 직접 처리해 주는 형태로 서비스를 하기 때문에, storage를 별도로 지정해 두었습니다.
외부에서 해당 서버에 요청이 오면, 먼저 nginx가 요청을 받아서 처리를 하게 되는데, static 파일 등은 nginx 가 알아서 처리해주고, 그 외에 django app이 처리해야할 부분만 reverse proxy 형태로 전달해 주게 됩니다.
Django 서비스 배포 절차
Django 서비스를 배포할 때는 다음과 같은 과정들이 필요합니다.
1. python 가상환경 준비 (처음 한번만 필요)
2. 소스 코드 업데이트
3. 의존 모듈 설치
4. static 파일 collect
5. model migration
6. django app service launch
다음에는 각각의 작업을 command로 살펴보겠습니다.
Django 서비스 배포 - 디렉터리 설정
위에서 언급하진 않았지만, 여기서는 아래와 같이 디렉터리를 설정해 보았습니다.
기본적으로 /opt/docker 폴더에서 각각의 서비스 컨테이너에 대한 폴더를 생성합니다. (nginx, python)
각 서비스 컨테이너 별로 루트에 docker-compose.yaml 파일들을 위치시키게 됩니다.
nginx 에 대해서는 설정파일들은 conf 폴더에 넣을 예정이고, static 파일들은 static 폴더에 넣어 두면 됩니다.
python 도 역시 설정파일들을 conf 폴더에 넣고, 그 외에 필요한 script들은 scripts 폴더에 보관합니다.
그 외에 python 에는 app 폴더를 생성할 예정인데요, app 폴더는 git clone 후에 rename 해서 생성할 예정입니다.
Django 서비스 배포 - 가상환경 준비
가상환경은 application 별로 독립된 python 환경을 구성하기 위해서 준비하는 과정인데, docker image를 빌드하는 경우에는 따로 독립된 환경을 사용하지 않아도 되지만, 여기서는 범용 python 이미지를 사용할 예정이기 때문에, local storage에 가상 환경을 생성해서 사용할 예정입니다. command는 다음과 같은데, 가상환경은 python docker container 안에서 실행할 예정입니다.
> python -m venv .venv
Django 서비스 배포 - 소스 코드 업데이트
소스코드 업데이트는 git pull (혹은 clone) 명령어로 처리가 가능합니다. 물론 먼저 서버에 git이 설치가 되어 있어야 합니다.
처음 소스를 받아올 때는 clone 명령어를 사용합니다.
> git clone <repository url>
추후에 업데이트 하는 경우에는 pull 명령어를 이용하면 됩니다.
> git pull
Django 서비스 배포 - 의존 모듈 설치
python에서 필요로 하는 모듈을 설치합니다. 로컬 개발환경에서는 간단히 pip 명령어로 처리가 되지만.. 여기서는 가상환경을 이용하기 때문에 아래와 같이 명령어를 입력합니다. 역시 python docker container 안에서 실행되어야 합니다.
모델을 migration 합니다. 실제로는 database 테이블을 생성 또는 변경 하는 과정입니다. 역시 python docker container 안에서 실행되어야 합니다.
> ./.venv/bin/python manage.py migrate
Django 서비스 배포 - django app service launch
django app 서비스를 실행합니다. 앞에서 잠시 언급한데로 wsgi 혹은 asgi 를 이용할 예정이기 때문에, 로컬 개발환경에서와는 조금 다른 명령어를 사용합니다. 역시 python docker container 안에서 실행되어야 합니다. 그리고 host를 지정하지 않으면 127.0.0.1 로 지정이 되는데, 컨테이너 외부에서 접속을 하기 위해서는 0.0.0.0 으로 바인드를 해줘야 합니다. port는 nginx에서 매핑할 예정이기 때문에 크게 중요하지 않아서 default 포트인 8000으로 지정해 주었습니다.
django app 이 asgi 형태로 실행되고 있어서, static 파일들 (css, image 등) 이 화면에 표현되지 않습니다.
테스트는 잘 실행이 되었지만, docker compose 실행이 제대로 되지 않는다면, 아마도 asgi 파일의 위치 문제일 가능성이 큽니다. run.sh 파일을 편집에서 해당 프로젝트에서 asgi 파일이 있는 경로를 지정해 주면 됩니다.
static 파일 문제를 해결하기 위해서 nginx를 셋업하도록 하겠습니다.
nginx 셋업
nginx도 docker로 이용할 예정이기 때문에 별다른 설치는 필요하지 않습니다.
nginx에서는 static 파일에 대한 요청을 처리하고, 나머지 요청은 django app으로 보내 줍니다. 실제로는 ssl 처리 등의 복잡한 기능이 필요하지만, 여기서는 아래와 같이 간단한 설정 파일을 준비합니다. 여기서 proxy_pass에 사용한 172.17.0.1 은 docker의 기본 host 주소 입니다. 원래는 docker network 을 이용해야 하지만, 간단한 예시이기 때문에, docker 기본 host 아이피를 적어주었습니다.
/opt/docker/nginx/conf/app.conf
server { listen 80; listen [::]:80; server_name localhost;
에러 내용은.. 허용되지 않는 host 라는 건데요.. 해결하기 위해서는 django app의 소스코드를 수정해야 합니다.
/opt/docker/python/app/config/settings.py 파일을 열어서 28번째 줄을 다음과 같이 변경합니다.
실제 운영환경에서는 이런 식의 소스 코드 변경을 막기위해서 이러한 설정 값은 모두 환경변수에서 읽어서 처리하게 해야 합니다.
그리고 python (django app) 의 docker 를 새로 띄우면, 아래와 같이 잘 나오게 됩니다.
눈치 빠르신 분은 이미 알아채셨겠지만.. 접속 주소가 localhost:8000 에서 localhost 로 변경이 되었습니다. nginx 가 연결을 해주기 때문에 이제는 localhost 로 접속하면 됩니다. 기존의 8000 포트는 iptables 혹은 firewall 등을 이용해서 외부에서 접근하는 것을 막아 두는 것이 좋습니다.
한글 위키 페이지도 있으나.. 내용이 조금 부실한 편이라 영문 위키 페이지를 링크로 달았습니다.
Recursion 을 이용한 풀이
위의 정의대로 Python을 이용해서 구현해 보면, 대략 다음과 같은 코드로 구현이 가능합니다.
def fibo(n):
if n < 1:
return 0
elif n < 3:
return 1
return fibo(n-1) + fibo(n-2)
fibo(19)를 출력해보면, 4181이 나오는 것을 확인할 수 있습니다.
Memoization 을 이용한 성능 개선
Recursion 을 이용하여 구현한 코드는 중복된 계산이 많아서 퍼포먼스에 문제가 있습니다.
fibo(5) 를 구하기 위해서 fibo(4) + fibo(3) 이 호출되고,
fibo(4) 를 구하기 위해서 다시 fibo(3) + fibo(2) 가 호출되고..
같은 계산을 여러 번 중복하는 것을 기록해 두어 성능을 개선해 보겠습니다. 아래 코드는 memoization 을 이용하여 성능을 개선한 코드입니다.
mCache = {}
mCache[1] = 1
mCache[2] = 1
def fibo_memo(n):
if n in mCache:
return mCache[n]
elif n < 1:
return 0
ret = fibo_memo(n-1) + fibo_memo(n-2)
mCache[n] = ret
return ret
한 번 계산을 했던 값은 mCache에 값을 기록해 두어, 중복 계산을 피해서 퍼포먼스를 향상시켰습니다.
Dynamic Programming 을 이용한 풀이
이번에는 테이블을 생성해서 값을 채워가는 방식으로 피보나치 값을 계산해 보겠습니다.
def fibo_dp(n):
if n < 1:
return 0
buf = [0] * (n+1)
buf[1] = 1
for i in range(2, n+1):
buf[i] = buf[i-1] + buf[i-2]
return buf[n]
피보나치 수열의 정의대로 순차적으로 계산해서 마지막 값을 돌려줍니다.
Dynamic Programming 개선
위에서 살펴본 Dynamic Programming에서는 테이블을 이용하였기 때문에, n+1 만큼의 메모리를 할당해서 값을 구하였습니다. 하지만 실제로는 이전의 계산 결과는 더 이상 쓰이지 않기 때문에, 이전값, 현재값을 가지고 있는 것으로 충분합니다. 위의 코드는 아래와 같이 개선이 가능합니다.
def fibo_dp2(n):
if n < 1:
return 0
prev = 0
current = 1
for i in range(1, n):
prev, current = current, prev + current
return current
Matrix를 이용한 풀이
마지막으로 matrix를 이용하여 피보나치 값을 구해 보도록 하겠습니다.
피보나치 수열은 행렬을 이용하면 다음과 같이 정의가 가능합니다.
위의 행렬을 두 개 붙여서 확장하면, 다음과 같은 식을 얻을 수 있습니다.
F0 ~ F2에 값을 대입해서, 식을 정리해 보면 다음과 같습니다.
즉, Fn 을 구하기 위해서는 아래 행렬의 (0,0) 값을 계산하면 됩니다.
행렬식의 계산은 다음과 같이 처리합니다.
1) 지수가 짝수인 경우,
2) 지수가 홀수인 경우,
위의 내용을 코드로 구현하면 다음과 같습니다.
def calc_matrix(m1, m2):
e00 = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]
e01 = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]
e10 = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]
e11 = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]
return [[e00, e01], [e10, e11]]
mBase = [[1, 1], [1, 0]]
def power(m, n):
if n <= 1:
return mBase
ret = power(m, n//2)
ret = calc_matrix(ret, ret)
if n % 2 == 1:
ret = calc_matrix(ret, mBase)
return ret
def fibo_mat(n):
if n < 1:
return 0
m = power(mBase, n-1)
return m[0][0]
지수 형태로 구현하였기 때문에, 시간 복잡도는 O(logN) 이 됩니다.
퍼포먼스 비교
각 방법에 대해서 F1000 을 구했을 때 걸리는 시간을 측정한 결과입니다.
recursion 의 경우, 시스템에 따라 다를 수 있지만 일정 갯수 이상이 되면, maximum recursion depth exceeded 에러가 발생합니다.
recursion 을 제외한 나머지에 대해서, F10000을 구했을 때 걸리는 시간을 측정한 결과 입니다.
파티션 문제는 list 의 원소들을 합이 같은 두 개의 부분 집합으로 나눌 수 있지를 확인하는 문제입니다.
Example
예를 들어 아래와 같은 리스트가 있다면,
[1, 5, 11, 5]
리스트를 아래와 같이 나누게 되면, 두 리스트의 합이 11로 같기 때문에, 결과는 True가 됩니다.
[1, 5, 5], [11]
Recursion 을 이용한 풀이
Recursion 을 이용할 때는, subset에 대한 합계를 체크하는 method를 정의해서 subset 합계가 전체 원소의 합의 절반이 되면 True를 리턴하게 작성합니다.
def isSubsetSum(arr, n, target):
# Termination Cases
if target == 0:
return True
if n == 0 and target != 0:
return False
# exclude last element or include last element
return isSubsetSum(arr, n-1, target) or isSubsetSum(arr, n-1, target-arr[n-1])
def findPartition(arr):
total = sum(arr)
if total % 2 != 0:
return False
return isSubsetSum(arr, len(arr), total // 2)
assert(findPartition([1,2,3,4,5]) == False)
assert(findPartition([1,5,11,5]) == True)
assert(findPartition([1,2,3,4,4,3,2,1]) == True)
이 경우, 시간 복잡도는 O(2^N) 이 되며, 공간 복잡도는 O(N) 이 됩니다.
Recursion 을 이용한 풀이 2 - memoization
Recursion 을 이용할 때는, subset sum 을 확인하는 과정에서 반복되는 계산이 나오기 때문에, 이를 기록해 두고 사용하면 반복 계산을 크게 줄일 수 있습니다. memoization 기법을 사용하여 개선한 코드는 다음과 같습니다.
def isSubsetSum(arr, n, target, dp):
# Termination Cases
if target == 0:
return True
if n == 0 and target != 0:
return False
# send result from memo
if dp[n][target] != -1:
return dp[n][target]
# save result
dp[n][target] = isSubsetSum(arr, n-1, target, dp) or isSubsetSum(arr, n-1, target-arr[n-1], dp)
# return result
return dp[n][target]
def findPartition(arr):
total = sum(arr)
if total % 2 != 0:
return False
n = len(arr)
# init memoization result
dp = [[-1]*(total+1) for i in range(n+1)]
return isSubsetSum(arr, n, total // 2, dp)
assert(findPartition([1,2,3,4,5]) == False)
assert(findPartition([1,5,11,5]) == True)
assert(findPartition([1,2,3,4,4,3,2,1]) == True)
여기서는 테스트한 list의 아이템이 많지 않아서, Recursion 보다도 느린 결과가 나올 수 있지만, 원소가 증가할 수록 큰 성능 향상을 확인할 수 있을 것입니다.
Dynamic Programming 을 이용한 풀이
이번에는 합계 / 원소 테이블을 생성해서, 테이블의 값을 채워가는 방식으로 문제를 해결해 보도록 하겠습니다. 이 방식의 아이디어는 다음과 같습니다.
1. row에는 부분집합의 합계를, column에는 리스트의 원소를 하나씩 추가할 수 있게 테이블을 준비합니다.
[1, 3, 7, 3] 의 케이스를 예를 들면,
전체 원소의 합은 14 (1 + 3 + 7 + 3) 이기 때문에, 원소들의 합이 같게 나눴을 때, 부분 집합의 원소의 합은 7이 되어야 합니다. (전체 원소 합의 절반) 그러면, 테이블은 아래와 같이 준비 됩니다.
[]
[1]
[1, 3]
[1, 3, 7]
[1, 3, 7, 3]
0
1
2
3
4
5
6
7
2. 부분 집합의 합계가 0이라는 것은, 부분 집합이 공집합이면 언제나 가능하기 때문에 어떤 부분 집합의 부분 집합에 대해서도 합계 0을 만들 수가 있습니다. 그래서 첫 번째 줄은 모두 가능하기 때문에 True로 채웁니다.
[]
[1]
[1, 3]
[1, 3, 7]
[1, 3, 7, 3]
0
True
True
True
True
True
1
2
3
4
5
6
7
3. 반대로, 원소가 없는 부분집합에 대해서는 원소의 합계는 항상 0이기 때문에 합계가 0보다 큰 경우는 만드는 것이 불가능합니다. 따라서 첫 번째 컬럼은 False로 채웁니다.
[]
[1]
[1, 3]
[1, 3, 7]
[1, 3, 7, 3]
0
True
True
True
True
True
1
False
2
False
3
False
4
False
5
False
6
False
7
False
4. 이제부터는 주어진 합계에 대해서, 원소를 채워가면서, 주어진 합계를 부분 집합의 합으로 만들 수 있는지를 체크합니다. 체크하는 방법은 마지막에 추가한 원소를 제외하고, 주어진 합계에서 해당 원소의 값을 뺀 경우에 대해서 부분 집합의 합을 만들 수 있는지를 체크하면 됩니다.
4-1. 먼저 부분 집합 [1] 의 부분 집합으로 합계 1을 만들 수 있는 지를 체크해 보겠습니다.
마지막에 추가한 원소는 "1" 이기 때문에, 해당 원소를 제거하고, 합계에서도 1을 뺍니다.
그러면, 부분 집합 []의 부분 집합으로 합계 0을 만들 수 있는 지를 체크해서, 그게 가능하면 부분 집합 [1]의 부분집합으로 합계 1을 만들 수 있는 지 알 수 있습니다. 우리는 이미 부분 집합 [] / 합계 0에 대해서 True로 채워 두었기 때문에 가능 하다는 것을 알 수 있습니다.
[]
[1]
[1, 3]
[1, 3, 7]
[1, 3, 7, 3]
0
True
True
True
True
True
1
False
True
2
False
3
False
4
False
5
False
6
False
7
False
4-2. 이번에는 부분 집합 [1, 3]의 부분 집합으로 합계 1을 만들 수 있는 지를 체크해 보겠습니다.
우리는 이미 부분 집합 [1]의 부분 집합으로 합계 1을 만들 수 있다는 것을 알고 있습니다. 그렇다면 [1]은 [1, 3]의 부분 집합이기 때문에, [1, 3]의 부분집합으로도 부분 집합의 합계 1을 만들 수 있습니다.
[]
[1]
[1, 3]
[1, 3, 7]
[1, 3, 7, 3]
0
True
True
True
True
True
1
False
True
True
2
False
3
False
4
False
5
False
6
False
7
False
5. 4번의 방법을 이용해서 테이블을 모두 채우면 아래와 같이 됩니다.
[]
[1]
[1, 3]
[1, 3, 7]
[1, 3, 7, 3]
0
True
True
True
True
True
1
False
True
True
True
True
2
False
False
False
False
False
3
False
False
True
True
True
4
False
False
True
True
True
5
False
False
False
False
False
6
False
False
False
False
True
7
False
False
False
True
True
6. 원래 우리가 찾던 답이 [1, 3, 7, 3]의 부분 집합 중에 합이 7인 것이 있는 지를 찾는 것이 었기 때문에, 위의 테이블의 가장 오른쪽 아래의 값을 읽어서 돌려주면 됩니다.
설명은 길었지만, 코드는 기존의 recursion 보다 짧습니다.
def findPartition(arr):
total = sum(arr)
if total % 2 != 0:
return False
half_sum = total // 2
n = len(arr)
# table setting
dp = [[True]*(n+1)] + ([[False]*(n+1)] * half_sum)
# fill the table
for i in range(1, half_sum+1):
for j in range(1, n+1):
if dp[i][j-1]:
dp[i][j] = True
continue
val = arr[j-1]
if i >= j and dp[i-val][j-1]:
dp[i][j] = True
# return result
return dp[half_sum][n]
assert(findPartition([1,2,3,4,5]) == False)
assert(findPartition([1,5,11,5]) == True)
assert(findPartition([1,2,3,4,4,3,2,1]) == True)
Dynamic Programming 공간 최적화
마지막으로 바로 전에 사용한 Dynamic Programming을 최적화 해보도록 하겠습니다. 위의 테이블을 잘 살펴보면, 실제로는 전체 테이블이 없어도 한 컬럼만 가지고 정보를 업데이트하면서 사용이 가능합니다. 다만 이전 단계의 결과를 체크하기 위해서는 top-down 방식이 아닌 bottom-up 방식으로 리스트를 채워가야 합니다.
1. 먼저 전체 리스트 원소의 합계의 절반 크기의 리스트를 생성합니다. 인덱스는 부분 집합의 합계를 나타내기 때문에, 0은 True로 세팅하고 나머지는 False로 세팅합니다.
0
1
2
3
4
5
6
7
Initial
True
False
False
False
False
False
False
False
2. 이번에는 원소를 하나씩 추가해가며, 합계를 제일 큰 수부터 순차적으로 체크해서 리스트를 업데이트 해줍니다.
체크는 다음과 같이 할 수 있습니다.
2-1. 해당 합계를 이미 만들 수 있다면 continue (dp[j] = True 인 경우)
2-2. 해당 합계에서 추가한 원소의 값을 뺀 값을 부분 집합의 합으로 만들 수 있는지를 체크해서 True인 경우, 해당 합계를 True로 업데이트 (dp[j - val] = True 인 경우)
ex)
첫번째 원소 1 추가
합계 7에서부터 역순으로 합계 0까지 체크
합계 7의 경우 현재 False 이기 때문에, dp[7-1] 에 있는 값을 체크
=> 현재 dp[6] = False 이기 때문에 업데이트를 하지 않고 진행
...
합계 1의 경우 현재 False 이기 때문에, dp[1-1]에 있는 값을 체크
=> 현재 dp[0] = True 이기 때문에 dp[1] = True로 업데이트
합계 0의 경우 이미 True 이기 때문에 continue
0
1
2
3
4
5
6
7
[1]
True
True
False
False
False
False
False
False
3. 순차적으로 원소를 추가하며 테이블을 업데이트 해주면.. 아래와 같이 업데이트 됩니다.
0
1
2
3
4
5
6
7
[1, 3]
True
True
False
True
True
False
False
False
0
1
2
3
4
5
6
7
[1, 3, 7]
True
True
False
True
True
False
False
True
0
1
2
3
4
5
6
7
[1, 3, 7, 3]
True
True
False
True
True
False
True
True
4. 리스트의 마지막 값인 dp[7] 을 읽어서 돌려 줍니다.
코드로 구현하면 다음과 같습니다.
def findPartition(arr):
total = sum(arr)
if total % 2 != 0:
return False
half_sum = total // 2
n = len(arr)
# init list
dp = dp = [True] + [False] * half_sum
# update list
for i in range(n):
val = arr[i]
for j in range(half_sum, val-1, -1):
if dp[j]:
continue
if dp[j-val] == True:
dp[j] = True
# return result
return dp[half_sum]
assert(findPartition([1,2,3,4,5]) == False)
assert(findPartition([1,5,11,5]) == True)
assert(findPartition([1,2,3,4,4,3,2,1]) == True)
실제로, 위의 코드에서 dp[half_sum] = True 가 되는 순간, 더 이상 for 문을 수행할 필요 없이 True를 돌려줘도 됩니다.
여기서는 이전 단계의 합계를 참조하기 위해서 bottom-up (가장 큰 합계를 먼저 체크) 하는 방식을 사용하였습니다.
DP 에서는 어떤 방향으로 테이블 혹은 리스트를 채우냐에 따라 공간 복잡도를 더 작게 구현할 수 있습니다.
이번 포스트에서는 PGP Key가 어떤 것인지 알아보고, PGP키를 생성 / 삭제 및 PGP 키를 이용해서 데이터를 encrypt / decrypt 하는 방법 등에 대해서 소개하겠습니다.
PGP 키
먼저, PGP는 Pretty Good Privacy 의 약자입니다. Phil Zimmermann 에 의해서 개발되었습니다. 초창기 PGP는 보안에 민감한 데이터를 취급할 때, 데이터를 받는 쪽에서만 decrypt 할 수 있게 하기 위해서 사용되었습니다.
PGP key를 이용해서 데이터를 받는 과정입니다.
1. 데이터를 받는 쪽에서 먼저 PGP 키를 생성합니다.
2. 데이터를 보내주는 쪽에 생성한 public key를 전달해 줍니다.
3. 데이터를 보내는 쪽에서는 전달 받은 public key를 이용해서 데이터를 encrypt 합니다.
4. 데이터를 전송합니다.
5. 데이터를 받는 쪽에서는 private key를 이용해서 데이터를 decrypt 합니다.
PGP 키는 발급시 public key 와 private key 가 생성되는데, public key는 encrypt 시에 사용되며, private key는 decrypt 시에 사용이 됩니다. 이런 비대칭성 (asymmetry) 때문에, public key는 공개 되어도 상관이 없습니다.
PGP vs GPG
PGP 키를 발급하는 과정에서, 검색을 하다보면 PGP 대신 GPG 가 검색이 되는 경우가 많습니다. GPG는 GNU Privacy Guard 의 약자로 Open Source 버전의 PGP 라고 생각하면 됩니다. Ubuntu 에서 기본으로 제공이 되기 때문에, 이 포스트에서는 GPG 커맨드를 이용해서 키를 관리해 보도록 하겠습니다.
PGP 키 생성
먼저, PGP키를 생성해 봅니다.
아래 커맨드를 이용하면 키를 생성할 수 있습니다.
> gpg --full-generate-key
참고로, 옵션 중에 --generate-key, --quick-generate-key 를 사용해도 키를 생성할 수 있으나, 알고리즘, 키 사이즈 혹은 유효기간 등을 원하는 방식으로 설정하기 위해서는 --full-generate-key 옵션을 사용해야 합니다.
커맨드를 실행하면, 몇 가지 물어보게 됩니다. 위에서 잠시 이야기 했던, 알고리즘, 키 사이즈, 유효기간을 설정하면 됩니다.
위의 필수 정보를 입력하고 나면, PGP 키 사용자에 대한 정보를 입력해야 합니다. (Real name, Email address, Comment)
이 중에 Real name은 아이디라고 생각하면 되는데, local에서 사용할 경우, Real name 만 입력해도 문제 없습니다. public 사이트에 공개해야 하는 경우에는 Email address도 입력해서 unique 한 인증 정보를 입력해야 합니다.
저는 Real name을 testpgp 로 설정하였습니다. 마지막에 O를 입력해서 Okay를 하면, 키가 생성이 됩니다.
PGP 키 확인
PGP 키가 생성이 되면, 생성된 키들은 key storage에 위치하게 됩니다.
키를 확인하기 위해서는 아래 커맨드를 사용합니다.
Pubilc key 확인 (소문자 k)
> gpg -k
Private key 확인 (대문자 K)
> gpg -K
실제로 입력을 해보면, 아래와 같이 생성된 키 정보를 확인할 수 있습니다.
데이터 encrypt, decrypt
이번에는 public key를 이용해서 데이터를 encrypt 해보고, private key를 이용해서 encrypt 된 데이터를 decrypt 해보도록 하겠습니다.
테스트를 위해서 간단한 텍스트 파일을 하나 생성하였습니다.
아래 커맨드를 이용해서 test.txt 파일을 encrypt 합니다.
> gpg -o test.gpg -e -r testpgp test.txt
커맨드에서 사용한 옵션은 다음과 같습니다.
-o: output filename, 여기서는 encrypt 되서 출력될 파일을 "test.gpg" 로 지정하였습니다.
-e: encrypt, encrypt 하라는 의미입니다.
-r: recipent, 수신자로 public key 이름을 적으면 됩니다.
마지막으로 test.txt는 encrypt 할 입력 파일 이름입니다.
커맨드 실행 후에는 아래와 같이 test.gpg 파일이 생성되었습니다.
이번에는 decrypt 하는 커맨드 입니다.
> gpg -o test_decrypted.txt -d test.gpg
커맨드에서 사용한 옵션은 다음과 같습니다.
-o: output filename, 여기서는 decrypt 되서 출력될 파일을 "test_decrypted.txt" 로 지정하였습니다.
-d: decrypt, decrypt하라는 의미입니다.
마지막으로 test.gpg 는 encrypt 된 입력 파일 이름입니다.
커맨드 실행 후에 생성된 test_decrypted.txt 파일을 열어보면, test.txt 파일과 같은 내용이 있음을 확인할 수 있습니다.
PGP 키 내보내기
이번에는 키를 export 해보겠습니다. public 키와 private 키 각각 export 옵션은 다음과 같습니다.
Pubilc key export
> gpg --export -a -r testpgp -o testpgp_pub.asc
Private key export (password 입력 필요)
> gpg --export-secret-key -a -r testpgp -o testpgp_pri.asc
위의 커맨드를 실행해보면, public key는 "testpgp_pub.asc" 파일로, private key는 "testpgp_pri.asc" 파일로 생성이 됩니다.
PGP 키 삭제하기
이번에는 키박스에 저장된 키들을 삭제해 보겠습니다. public key와 private key가 같이 있는 경우에는 private key 부터 삭제 합니다.
Private key 삭제
> gpg --delete-secert-key testpgp
Public key 삭제
> gpg --delete-key testpgp
커맨드 실행 후, 확인 명령어로 키를 체크해 보면, 삭제된 것을 알 수 있습니다.
PGP 키 가져오기
마지막으로 export 해 뒀던 키를 키박스로 가져오는 커맨드 입니다.
Pubilc key import
> gpg --import testpgp_pub.asc
Private key import (password 입력 필요)
> gpg --import testpgp_pri.asc
위의 명령어를 실행하면 아래와 같이 출력되면서, 키박스에 키들이 저장됩니다.
그런데, 가져오기 후에 PGP 키를 확인해 보면, 아래와 같이 trust 상태가 unknown으로 나오게 됩니다.
trust 상태를 바꿔주기 위해서 --edit-key 옵션을 사용합니다.
> gpg --edit-key testpgp
명령어를 입력하면 아래와 같은 프롬프트 화면이 나오게 됩니다.
프롬프트에 "trust" 를 입력하고, trust 상태를 지정합니다. (여기선 5)
y를 입력해서 변경사항을 확인해 주면 저장이 완료됩니다.
마지막으로 quit 를 입력해서 프롬프트를 종료합니다.
pgp 키 정보를 확인해 보면 trust 상태가 "ultimate" 으로 변경된 것을 확인할 수 있습니다.
