Docker Compose를 이용한 설치를 한 상황을 기준으로 하겠다.

  - https://www.whatwant.com/entry/Apache-Airflow-install

 

[ Status ]

    - Docker Compose를 이용해서 Apache Airflow를 설치한 상태이다.

 

> docker ps

 

    - 하지만, example들이 엄청 많이 보인다.

        . 공부하기 위해 참조할 수는 있지만, 삭제해도 다시 살아나고..... 지워버리고 싶은 상황이다.

 

http://localhost:8090/home

 

[ Docker Compose Down ]

    - 현재 설치된 것을 모두 지워버려야 한다.

 

> docker compose down

 

> docker compose down

 

[ Edit docker-compose.yaml ]

    - YAML 파일의 내용을 살짝 바꿔줘야 한다.

 

> nano docker-compose.yaml

 

> nano docker-compose.yaml

 

    - 빨간 박스에 있는 것 처럼, 해당 값을 false로 변경해주면 된다.

 

[ Re-install ]

    - 이제 설치/실행 진행하면 된다.

 

❯ docker compose up airflow-init


❯ docker compose up

 

    - 그리고 웹브라우저 다시 열고 접속하고 로그인 하면... 깨끗한 화면을 볼 수 있다!

 

http://localhost:8090/home

 

깔끔!

반응형

'AI_ML > MLOps' 카테고리의 다른 글

Apache Airflow install (아파치 에어플로우 설치)  (1) 2024.05.04

▷ Basic Info ...

    - MLOps에 대해서 공부를 하다보면 누구나 한 번 이상 꼭 듣게 되는 도구 ... Apache Airflow !!!

    - 공식 사이트를 방문해보면 바람개비와 함께 산뜻한 페이지가 반긴다.

        . https://airflow.apache.org/

 

https://airflow.apache.org/

 

    - 하지만, 우리같은(?) 도구쟁이들은 GitHub 사이트가 더 좋다 ^^

        . https://github.com/apache/airflow

 

https://github.com/apache/airflow

 

    - 최신병에 걸려있기 때문에(^^), 릴리즈 정보를 확인해봐야 한다.

        . https://airflow.apache.org/announcements/

 

https://airflow.apache.org/announcements/

 

▷ Prerequisites

    - 기본적으로 POSIX 호환 운영체제에서 Python만 있으면 설치는 가능하다.

        . Linux 배포판 및 MacOS가 기본적인 지원 운영체제이지만

        . WSL2에서도 실행은 가능하다. 다만, 주력 지원 환경은 아니기에 Production 환경으로는 추천하지 않는다.

        . Kubernetes 환경에서 동작 가능한 것이지 설치할 때 필수 환경은 아니다.

 

    - 메모리는 최소 4GB 이상이 필요하다.

 

    - 설치할 때 SQLite를 같이 포함해서 설치를 진행할 수 있지만, Production에서는 별도 DB 구성을 추천한다.

 

https://airflow.apache.org/docs/apache-airflow/2.9.0/installation/prerequisites.html

 

▷ Environments

    - 설치 과정을 함께할 운영체제는 Ubuntu 20.04 환경이다.

        . Airflow는 Debian 계열하고 제일 친한 것 같다. 그렇다면 Ubuntu가 최선이지 않을까!?

 

❯ lsb_release -a

No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 20.04.6 LTS
Release: 20.04
Codename: focal

 

    - 일단 메모리 상황을 점검해보자.

        . 메모리는 마음대로 할 수 있는 것이 아니니 부족하다면... 다른 서버를 찾아야 한다 ㅠ

 

❯ free -h

                  total        used          free       shared    buff/cache   available
Mem:       7.8Gi       679Mi       6.4Gi          13Mi          677Mi        6.8Gi
스왑:        2.0Gi          0B         2.0Gi

 

    - Python 버전을 확인해보자.

        . Python 버전 관리를 위해서는 Pyenv를 사용하는 것을 권장합니다 !!!

        . https://www.whatwant.com/entry/pyenv

 

❯ pyenv --version   

pyenv 2.3.9-11-g3d83bcdb


❯ python --version

Python 3.8.16

 

▷ Install #1 - PyPI + venv

    - Apache Airflow를 설치하는 여러 방법이 있는데,

      PyPI를 이용하는 방법과 Docker를 이용하는 방법에 대해서 살펴보고자 한다.

 

① pyenv

    - Python 3.10 버전 환경에서 설치를 해보고자 한다.

    - pyenv를 이용해서 원하는 버전을 설치하도록 하겠다.

 

❯ pyenv versions  

  system
* 3.8.16 (set by /home/chani22/.pyenv/version)

# 사용하고자 하는 버전이 설치되어 있는지 확인


❯ pyenv install -l

Available versions:
  2.1.3
  2.2.3
...

# 설치가 가능한 버전 확인


❯ pyenv install 3.10.9

Downloading Python-3.10.9.tar.xz...
-> https://www.python.org/ftp/python/3.10.9/Python-3.10.9.tar.xz
Installing Python-3.10.9...
Installed Python-3.10.9 to /home/chani22/.pyenv/versions/3.10.9

 

② workspace / venv

    - Airflow를 설치할 디렉토리를 확보하고,

    - Python venv를 이용하여 가상환경까지 생성해보자.

 

❯ mkdir airflow

❯ cd airflow

❯ pyenv local 3.10.9 

❯ python -m venv .venv

❯ ls -al

합계 16
drwxrwxr-x 3   chani22 chani22 4096  4월 29 01:18 .
drwxr-xr-x 3    chani22 chani22 4096  4월 29 01:16 ..
-rw-rw-r-- 1      chani22 chani22      7  4월 29 01:16 .python-version
drwxrwxr-x 5   chani22 chani22 4096  4월 29 01:18 .venv

❯ source .venv/bin/activate

 

③ ENV

    - 설치에 필요한 정보들을 위해서 환경 변수들을 설정해준다.

    - "/srv/install/airflow" 디렉토리는 위에서 만들어 놓은 것을 사용해도 된다.

    - "AIRFLOW_VERSION"은 지금 현재 가장 최신 버전을 선택했다.

    - "PYTHON_VERSION"의 경우에 그냥 명시적으로 "3.10"이라고 설정해버려도 된다.

    - "CONSTRAINT_URL" 역시 그냥 명시적으로 버전을 지정할 수도 있다.

 

❯ export AIRFLOW_HOME=/srv/install/airflow

❯ export AIRFLOW_VERSION=2.9.0

❯ export PYTHON_VERSION="$(python -c 'import sys; print(f"{sys.version_info.major}.{sys.version_info.minor}")')"

❯ export CONSTRAINT_URL="https://raw.githubusercontent.com/apache/airflow/constraints-${AIRFLOW_VERSION}/constraints-${PYTHON_VERSION}.txt"


❯ echo $PYTHON_VERSION

3.10


❯ echo $CONSTRAINT_URL

https://raw.githubusercontent.com/apache/airflow/constraints-2.9.0/constraints-3.10.txt

 

④ install

    - 준비 끝. 설치 시작!

 

❯  pip install "apache-airflow==${AIRFLOW_VERSION}" --constraint "${CONSTRAINT_URL}"

...


❯ pip list | grep airflow                                                          

apache-airflow                                          2.9.0
apache-airflow-providers-common-io       1.3.0
apache-airflow-providers-common-sql     1.11.1
apache-airflow-providers-fab                    1.0.2
apache-airflow-providers-ftp                     3.7.0
apache-airflow-providers-http                   4.10.0
apache-airflow-providers-imap                 3.5.0
apache-airflow-providers-smtp                 1.6.1
apache-airflow-providers-sqlite                3.7.1

 

⑤ DB init

    - 그냥 실행하는 방법도 있지만, 하나씩 차근차근 셋업하는 것을 추천한다.

 

❯ airflow db migrate

DB: sqlite:////srv/install/airflow/airflow.db
Performing upgrade to the metadata database sqlite:////srv/install/airflow/airflow.db
[2024-04-29T02:20:10.674+0900] {migration.py:216} INFO - Context impl SQLiteImpl.
[2024-04-29T02:20:10.710+0900] {migration.py:219} INFO - Will assume non-transactional DDL.
[2024-04-29T02:20:10.713+0900] {migration.py:216} INFO - Context impl SQLiteImpl.
[2024-04-29T02:20:10.714+0900] {migration.py:219} INFO - Will assume non-transactional DDL.
INFO  [alembic.runtime.migration] Context impl SQLiteImpl.
INFO  [alembic.runtime.migration] Will assume non-transactional DDL.
INFO  [alembic.runtime.migration] Running stamp_revision  -> 1949afb29106
Database migrating done!

 

⑥ make admin account

    - 관리자 계정을 만들어주자.

    - "--role Admin" 부분만 잘 지켜주고, 나머지는 각자 취향대로.

 

❯ airflow users create --username whatwant --firstname whatwant --lastname boss --role Admin --email whatwant@whatwant.com

...
Password:
Repeat for confirmation:
[2024-04-29T02:31:53.165+0900] {override.py:1516} INFO - Added user whatwant
User "whatwant" created with role "Admin"

 

⑦ run

    - 이제 웹 UI를 확인해보자.

 

airflow webserver --port 8080

 

    - 웹브라우저를 실행해서, 다음 주소로 접속하면 된다.

        . http://localhost:8080

 

http://localhost:8080/

 

    - 앞에서 생성한 계정과 패스워드를 이용해서 Sign in 하면 된다.

 

http://localhost:8080/

 

    - 뭔가 화면은 나왔는데, 위에 뭔가 알람이 많이 보인다.

 

⑧ notice

    - 어?! 그런데 뭔가 경고같은 메시지가 보인다.

 

notice

 

    - 가장 위에 있는 메시지를 보면 실행중인 "scheduler"가 안보인단다. 해결해보자.

 

⑨ scheduler

    - 새로운 터미널을 추가로 띄워서 scheduler를 실행하면 된다.

 

new terminal

 

   - 터미널을 새로 띄우면 Python 가상환경도 추가 설정해야 한다.

 

❯ cd airflow

# 앞에서 진행했던 airflow 디렉토리로 이동


❯ source .venv/bin/activate


❯ airflow scheduler

 

    - 웹브라우저를 reload(F5) 하면 갑자기 못보던 샘플 DAGs 가 보인다.

 

http://localhost:8080/home

 

    - 상단에 보이는 알람 메시지가 3개에서 2개로 줄어들었다.

    - 나머지 2개는 production 환경에서 SQLite나 SeuentialExecutor를 사용하지 말라는 메시지다. 일단 무시!

 

http://localhost:8080/dags/example_params_trigger_ui/grid?tab=graph

 

    - Sample을 하나 선택해서 살펴보면 뭔가 멋지다! ^^

 

 

▷ Install #2 - Docker + Compose

    - docker를 이용한 airflow 설치를 해보자.

    - 그냥 docker image를 이용한 실행말고, 여러 모듈들을 같이 구성하기 위해 docker compose를 사용하겠다.

    - https://airflow.apache.org/docs/apache-airflow/2.9.0/howto/docker-compose/index.html

 

① docker / docker-compose

    - docker 및 docker-compose가 설치되어 있어야 한다.

        . Ubuntu 20.04 기준으로 Quick-Guide는 다음과 같다.

 

❯ mkdir docker 

❯ cd docker      

❯ wget https://download.docker.com/linux/ubuntu/dists/focal/pool/stable/amd64/containerd.io_1.6.31-1_amd64.deb

❯ wget https://download.docker.com/linux/ubuntu/dists/focal/pool/stable/amd64/docker-buildx-plugin_0.14.0-1\~ubuntu.20.04\~focal_amd64.deb

❯ wget https://download.docker.com/linux/ubuntu/dists/focal/pool/stable/amd64/docker-ce-cli_26.1.1-1\~ubuntu.20.04\~focal_amd64.deb

❯ wget https://download.docker.com/linux/ubuntu/dists/focal/pool/stable/amd64/docker-ce_26.1.1-1\~ubuntu.20.04\~focal_amd64.deb

❯ wget https://download.docker.com/linux/ubuntu/dists/focal/pool/stable/amd64/docker-compose-plugin_2.27.0-1\~ubuntu.20.04\~focal_amd64.deb


❯ ls -al

합계 109212
drwxrwxr-x 2 chani22 chani22     4096  5월  1 10:31 .
drwxr-xr-x 4 chani22 chani22     4096  5월  1 10:29 ..
-rw-rw-r-- 1 chani22 chani22 29821672  4월 11 21:01 containerd.io_1.6.31-1_amd64.deb
-rw-rw-r-- 1 chani22 chani22 29650176  4월 30 01:48 docker-buildx-plugin_0.14.0-1~ubuntu.20.04~focal_amd64.deb
-rw-rw-r-- 1 chani22 chani22 14601364  5월  1 00:17 docker-ce-cli_26.1.1-1~ubuntu.20.04~focal_amd64.deb
-rw-rw-r-- 1 chani22 chani22 25267932  5월  1 00:17 docker-ce_26.1.1-1~ubuntu.20.04~focal_amd64.deb
-rw-rw-r-- 1 chani22 chani22 12478416  5월  1 00:17 docker-compose-plugin_2.27.0-1~ubuntu.20.04~focal_amd64.deb


❯ sudo dpkg --install containerd.io_1.6.31-1_amd64.deb 

❯ sudo dpkg --install docker-ce-cli_26.1.1-1\~ubuntu.20.04\~focal_amd64.deb 

❯ sudo dpkg --install docker-ce_26.1.1-1\~ubuntu.20.04\~focal_amd64.deb    

❯ sudo dpkg --install docker-buildx-plugin_0.14.0-1\~ubuntu.20.04\~focal_amd64.deb 

❯ sudo dpkg --install docker-compose-plugin_2.27.0-1\~ubuntu.20.04\~focal_amd64.deb 


sudo usermod -aG docker $USER

# 터미널 재시작


❯ docker --version

Docker version 26.1.1, build 4cf5afa


❯ docker compose version

Docker Compose version v2.27.0

 

② download YAML

    - airflow 설치 과정을 위한 디렉토리 만들고

    - docker-compose YAML 파일을 다운로드 받자

 

❯ mkdir airflow-docker

❯ cd airflow-docker

❯ wget https://airflow.apache.org/docs/apache-airflow/2.9.0/docker-compose.yaml

--2024-05-01 10:44:57--  https://airflow.apache.org/docs/apache-airflow/2.9.0/docker-compose.yaml
airflow.apache.org (airflow.apache.org) 해석 중... 151.101.2.132, 2a04:4e42::644
다음으로 연결 중: airflow.apache.org (airflow.apache.org)|151.101.2.132|:443... 연결했습니다.
HTTP 요청을 보냈습니다. 응답 기다리는 중... 200 OK
길이: 11197 (11K)
저장 위치: `docker-compose.yaml'

docker-compose.yaml                 100%[==========================================>]  10.93K  --.-KB/s    / 0s       

2024-05-01 10:44:57 (45.5 MB/s) - `docker-compose.yaml' 저장함 [11197/11197]

 

    - YAML 파일 내용을 살펴보면 알겠지만, 많은 서비스가 별도의 docker로 구성되어 있다.

        . airflow-scheduler

        . airflow-webserver

        . airflow-worker

        . airflow-triggerer

        . airflow-init

        . postgres

        . redis

 

    - 그래서 메모리가 충분히 필요한데, 최소 4GB / 권장 8GB 이다.

 

③ mkdir

    - 여러 종류의 파일들을 저장할 디렉토리들을 만들어 놓자.

        . ./dags - you can put your DAG files here.
        . ./logs - contains logs from task execution and scheduler.
        . ./config - you can add custom log parser or add airflow_local_settings.py to configure cluster policy.
        . ./plugins - you can put your custom plugins here.

 

❯ mkdir -p ./dags ./logs ./plugins ./config


❯ ls -al

합계 36
drwxrwxr-x 6 chani22 chani22  4096  5월  1 10:53 .
drwxr-xr-x 5 chani22 chani22  4096  5월  1 10:44 ..
drwxrwxr-x 2 chani22 chani22  4096  5월  1 10:53 config
drwxrwxr-x 2 chani22 chani22  4096  5월  1 10:53 dags
-rw-rw-r-- 1 chani22 chani22 11197  4월  8 20:42 docker-compose.yaml
drwxrwxr-x 2 chani22 chani22  4096  5월  1 10:53 logs
drwxrwxr-x 2 chani22 chani22  4096  5월  1 10:53 plugins

 

④ UID

    - airflow가 실행될 UID도 설정해주자.

 

❯ echo -e "AIRFLOW_UID=$(id -u)" > .env


❯ cat .env

AIRFLOW_UID=1000

 

⑤ Customizing

    - YAML 파일을 수정할 수도 있다.

    - port만 살짝 바꿔봤다. (각자 취향)

 

❯ nano docker-compose.yaml

 

⑥ Initialize the database

    - DB 초기화를 진행하자.

 

❯ docker compose up airflow-init

 

    - 잘 실행되면 아래와 같은 화면이 나온다.

 

❯ docker compose up airflow-init

 

    - 아래와 같이 Permission denied 상황이 나올 수도 있는데,

      sock 파일의 권한을 조정하거나 그래도 안되면 재부팅 한 번 해주면 잘 된다.

 

❯ docker compose up airflow-init

permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Get "http://%2Fvar%2Frun%2Fdocker.sock/v1.45/containers/json?all=1&filters=%7B%22label%22%3A%7B%22com.docker.compose.config-hash%22%3Atrue%2C%22com.docker.compose.project%3Dairflow-docker%22%3Atrue%7D%7D": dial unix /var/run/docker.sock: connect: permission denied


❯ sudo chown root:docker /var/run/docker.sock

 

    - 현재 상태를 확인해보면 다음과 같다.

 

❯ ls -al

합계 40
drwxrwxr-x 6 chani22 chani22  4096  5월  1 11:00 .
drwxr-xr-x 5 chani22 chani22  4096  5월  1 10:44 ..
-rw-rw-r-- 1 chani22 chani22    17  5월  1 10:55 .env
drwxrwxr-x 2 chani22 chani22  4096  5월  1 10:53 config
drwxrwxr-x 2 chani22 root     4096  5월  1 10:53 dags
-rw-rw-r-- 1 chani22 chani22 11197  5월  1 11:00 docker-compose.yaml
drwxrwxr-x 2 chani22 root     4096  5월  1 10:53 logs
drwxrwxr-x 2 chani22 root     4096  5월  1 10:53 plugins


❯ docker ps

CONTAINER ID   IMAGE          COMMAND                   CREATED         STATUS                   PORTS      NAMES
1dfae6410fa0   postgres:13    "docker-entrypoint.s…"   4 minutes ago   Up 4 minutes (healthy)   5432/tcp   airflow-docker-postgres-1
466bc0539812   redis:latest   "docker-entrypoint.s…"   4 minutes ago   Up 4 minutes (healthy)   6379/tcp   airflow-docker-redis-1

 

⑦ Run Airflow

    - 이제 Airflow를 실행하자.

 

  docker compose up

...

 

   - 뭔가 잔뜩 메시지가 흘러나온다.

 

❯ docker compose up

 

    - 웹브라우저를 열어서 접속해보자.

        . http://localhost:8090/

        . 접속 정보: airflow / airflow

 

http://localhost:8090/

 

    - 어!? 뭔가 되게 깔끔한 화면이 나온다.

 

http://localhost:8090/home

 

    - Container 정보를 살펴보자.

 

> docker ps

 

 

우와~~~~ 뭔가 엄청 길었다.

추가적으로 살펴볼 것이 많이 남아있지만 일단 "설치 후 실행"이라는 것에 주안점을 두었다.

 

"운영" 측면에서는 더 알아봐야할 것이 많겠지만 지금은 여기까지만~~~ ^^

반응형

'AI_ML > MLOps' 카테고리의 다른 글

Airflow remove Example DAGs (에어플로우 예제 삭제)  (0) 2024.05.04

출처: https://www.whatwant.com

 

이번에는 Greedy Algorithm을 살펴보도록 하겠다.

 

앞서 살펴본 Dynamic Programming의 경우에는 모든 경우의 수를 고려하여 최적의 솔루션을 찾는 방식이었다면

Greedy Algorithm은 어떤 순간에 최선으로 보이는 것을 선택해서 문제를 푸는 방식이다.

 

뭔 말이냐고!? 일단 하나 살펴보자.

 

 

[Overview]

어떤 활동(activity)들의 집합이 있다고 해보자.

 

출처: https://www.whatwant.com

 

이처럼 여러 activities들이 있을 때,

서로 겹치지 않고 동시에 할 수 있는 activities 중 가장 큰 subset을 선택하는 문제는 어떻게 풀면 좋을까?

 

예를 들자면,

강의실이 하나만 있을 때 여러 수업들을 어떻게 배치해야 가장 많은 수업들을 배치할 수 있는지를 정하는 것과 같다.

 

[Sample]

예시를 하나 들어보자.

 

출처: https://www.whatwant.com

 

위와 같이 activity들이 있다고 했을 때 어떤 조합들이 가능할까?!

 

출처: https://www.whatwant.com

 

우선 {a3, a9, a11} 집합의 경우 mutually compatible 하게 잘 묶여 있다.

서로 배타적이면서 같이 어울릴 수 있는 조합이라는 말이다.

 

하지만, 이 집합은 주어진 상황에서 largest set이라고 할 수는 없다.

 

출처: https://www.whatwant.com

 

{a1, a4, a8, a11} set은 largest set이라고 할 수 있다.

4개보다 더 큰 조합은 찾을 수 없기 때문이다.

 

하지만 unique한 largest set은 아니다.

 

출처: https://www.whatwant.com

 

{a2, a4, a9, a11}의 경우도 largest set이다.

 

그런데, 이렇게 눈으로 정답을 찾는 것은 뭔가 좀..... ^^

 

[Optimal substructure]

일단 아래와 같은 문제가 주어졌다고 했을 때, 각 activity들의 시작 위치와 종료 위치를 작성해보자.

 

출처: https://www.whatwant.com

 

여기에서는 문제가 index 순서에 따라 종료 시간(f)이 순서대로 나와 있어서 정렬을 할 필요가 없지만,

종료 시간의 오름차순으로 정렬까지 해줘야 한다.

 

출처: https://www.whatwant.com

 

이렇게만 했으면 나머지는 쉽다.

 

출처: https://www.whatwant.com

 

제일 먼저 종료되는 시간 이후로 첫번째로 시작하는 activity를 선택하고,

그 activity가 종료되는 시간을 확인하고 또 다시, 그 종료 시간 이후로 시작하는 activity를 찾고... 반복하면 된다.

 

끝이다.

 

뭔가 허무한데, 끝이다.

 

 

[Elements of the greedy strategy]

어째서 Dynamic Programming과 다르게 Greedy Algorithm은 이렇게 문제를 풀 수 있는지에 대해서 알아보자.

 

출처: https://www.whatwant.com

 

subproblem을 모두 풀어야지만 솔루션을 선택할 수 있는 경우에는 Dynamic Programming 문제이고,

모든 subproblem을 풀기 전에 솔루션을 선택할 수 있는 문제는 Greedy Algorithm을 적용할 수 있다.

 

출처: https://www.whatwant.com

 

Zero-One 배낭 문제는 물건을 갯수 단위로만 가방안에 넣을 수 있는 경우에 해당하는 문제이다.

물건들의 가격과 무게가 모두 다르다고 했을 때, 어떻게 넣어야지 가장 비싸게 물건을 훔칠 수 있는지를 찾는 것이다.

모든 조합을 고려해야 문제가 풀리는 것이다.

 

출처: https://www.whatwant.com

 

이와는 다르게, 만약 아이템을 조각내서 가방에 담을 수 있다고 하면 어떻게 될까?

그러면 개별 단가가 가장 비싼 것들로 정렬해서 그냥 그렇게 넣으면 된다.

담을 수 있는 무게와 딱 떨어지지 않을 경우에는 조각내면 된다.

모든 조합을 고려할 필요가 없는 것이다.

 

예시를 들어보자.

 

출처: https://www.whatwant.com

 

⒜와 같이 상황이 주어졌다고 해보자.

배낭은 담을 수 있는 무게의 한계가 있다.

 

⒝는 Dynamic Programming 방식으로 해답을 찾아보는 것이다. 모든 조합을 검토하는 것이다.

 

⒞는 Greedy Algorithm 방식이다. 무게당 단가를 계산해서 가장 비싼 것들부터 넣기 시작하다가

무게 제한에 걸리는 시점에는 해당 아이템을 잘라내서 무게에 맞추면 되는 것이다.

 

확실히 문제의 유형이 다르다!!!

반응형

출처: https://www.whatwant.com

 

이번에 살펴볼 Dynamin Programming 알고리즘은

Matrix-Chain Multiplication (연쇄 행렬 곱셈)이다.

 

[Background]

우선 알아야할 내용은 바로 "행렬 곱" 규칙이다.

 

 

'행렬 곱'을 하기 위해서는 앞 행렬의 column 길이와 뒤 행렬의 row 길이가 같아야 한다.

그러면, 앞 행렬의 row 와 뒤 행렬의 column 길이만큼의 결과가 나온다.

 

두번째로 알아야할 내용은 행렬 곱에서 '결합 법칙'이 성립한다는 것이다.

 

 

그런데, 여기에서 우리가 주의깊게 살펴봐야할 사실이 하나 등장한다.

 

행렬 곱에서 결합을 어떻게 하는지에 따라 계산 횟수가 달라진다는 것이다.

 

 

위의 예시와 같이 3개의 행렬이 주어졌을 때,

계산 횟수를 살펴보면 10배의 차이가 발생한다는 것을 알 수 있다.

 

 

[Problem]

그러면 우리가 여기에서 해결하고자 하는 문제가 무엇일까?

 

 

곱셈을 해야하는 여러 행렬이 순서대로 주어졌을 때,

어떻게 결합을 해야 전체 계산 횟수를 최소화 할 수 있을지를 찾아내는 것이다.

 

 

[Brute force approach]

일단 무식하게 살펴보자.

 

 

총 4개의 행렬이 주어졌을 때, 총 5가지의 묶음 방법이 존재한다.

 

이를 분류해보면

앞에서부터 1개 묶음을 하면 총 2종의 결합 방법이 존재하고

2개 묶음을 하면 1종,

3개 묶음을 하면 2종의 결합 방법이 있기에 총 5종의 결합 방법이 있게 된다.

 

이 과정을 공식으로 살펴보면 다음과 같다.

 

 

공식을 유도하고 분석하는 것은 생략하도록 하겠다.

 

그런데, 이를 Asymptotic 하게 생각해보면, 다음과 같다.

 

 

마찬가지로 계산식 유도 및 분석은 생략하고.... 결론적으로 엄청난 경우의 수가 나오기에...

이렇게 문제를 푸는 것은 말이 안됨! ^^

 

[Solution]

똑똑하게 문제를 풀어보자.

 

 

지금까지 살펴본 내용을 공식화한 것으로 생각하면 된다.

위 공식을 가지고 직접 손으로 계산을 해보자.

 

행렬에 따라서 row와 column은 다음과 같이 살펴볼 수 있다.

 

 

왜 이렇게 표현이 되는지 이해가 안되면 안된다.

앞에서 충분히 살펴본 내용을 곰곰히 생각해보면 된다.

 

예시를 하나 들어보자.

행렬이 6개가 주어졌다고 했을 때, p값이 다음과  같이 제시 되었다고 해보자.

 

 

이 문제를 풀기 위해 우리는 m, s 행렬을 작성해야 한다.

 

 

왜 이렇게 하는지는 문제를 풀어보면서 알아보자.

 

 

위 공식을 살펴보면 알겠지만,

i=j 조건에서는 모두 0 값을 갖게 되고 i보다 j는 항상 커야 되기 때문에 표의 아랫부분은 계산하지 않아도 된다.

 

 

m[1][2] 값부터 계산해보면 위와 같이 정리해볼 수 있다.

k값은 ( i ≤ k < j ) 조건이므로 ( 1 ≤ k < 2 )와 같고, 그렇기 때문에 k값은 1밖에 갖을 수 없다.

 

s 행렬의 s[1][2] 값은 k값이 1이므로 1값을 작성하면 된다.

 

이런식으로 m[2][3], m[3][4], m[4][5], m[5][6] 부분을 채울 수 있다.

 

 

이번에는 m[1][3]을 계산해보자.

 

앞에서와 달리 k값은 ( 1 ≤ k < 3 )이므로, k값은 1, 2 의 2가지 경우가 있을 수 있다.

그러므로, 최종 결과가 2개 나오고, 그 중에서 min 값을 선택하면 된다.

 

k값이 1인 경우를 선택했으므로 s[1][3] 위치에는 1을 작성하면 된다.

 

 

하나씩 하나씩 이렇게 채워나가면 된다.

 

전부 채우면 다음과 같다.

 

 

끝~

 

[Pseudo Code]

이 과정을 가지고 pseudo code로 만들어보자.

 

 

이렇게 만들어진 결과물을 출력하기 위한 code는 다음과 같다.

 

 

[Time & Space]

time complexity 와 memory space를 계산해보면 다음과 같다.

 

먼저 Time Complexity를 살펴보자.

 

 

무려 n의 3승 이다.

 

메모리 공간을 계산해보면 다음과 같다.

 

 

알고리즘을 위해 추가로 사용하는 메모리는 m, s 배열이 필요하다.

Asymptotic 하게 해보면.... 결국은 n의 제곱만큼의 공간을 필요로 한다.

 

반응형

갑자기 한글 음성으로 더빙된 게임을 해보고 싶다는 강력한 욕망(?)이 들어 찾아본 게임이다 ^^

 

 

남코(NAMCO)에서 만든 명작 시리즈 게임~~~

 

 

게임 시작하자마자 내가 좋아하는 에니메이션.... 매패니메이션...

음악도 상당히 괜찮다 !!! 우와~~~

 

 

역시 유명한 게임들은 유명한 이유가 있다니까!!!

 

 

테일즈 오브 데스티니 2 (Tales of Destiny 2)

1편 주인공들의 아들이 주인공이 되어 이야기를 이어가는 것이라고 한다. (1편을 안해봐서 ㅠㅠ)

 

 

게임을 시작하면 나오는 것이 바로 1편의 이야기인 것 같다.

 

 

그렇게 주인공이 자랐다 !!! ^^

 

 

잉!? 게임을 시작하니..... 이등신 캐릭터가 !!!

 

살짝 실망....

 

그런데, 한글 잘 나오고... 음성이 한국어로 더빙이 되어있고.... 거기다가 상당히 많은 분량으로 음성이 나온다 !!!

 

많은 감동 !!!

 

 

제대로 나오는 그림도 그렇고, 이등신 캐릭터도 그렇고...

제일 마음에 안드는 캐릭터가 바로 주인공이다 ㅠㅠ

 

저 삐쭉 머리는 대체 뭐야.....

 

 

조작법을 설명해주는 방법도 마음에 든다.

마을에서 냇가를 지나갈 때 들리는 물소리를 들었을 때에는 정말 깜짝 놀랐다!!!

 

 

게임 곳곳에 배치되어 있는 저런 유머 코드들은 게임의 재미를 배가 시켜준다.

 

 

전투 방식은 의외로 재미있다.

내가 직접 실시간으로 조작을 해야한다.

 

그리고 설정에서 동료들의 전투 방식을 설정해줄 수도 있다.

스킬들의 컨트롤러 키배치도 설정에서 모두 정해줄 수 있다.

 

 

응?! 마을에서 나오니까 갑자기 이등신 캐릭터가 3D가 되어버렸다.

이럴거면 그냥 이등신 캐릭터 대신에 마을 안에서도 이렇게 하지....

 

 

퍼즐처럼 진행해야 하는 부분들이 있다.

매뉴얼을 찾아보고 싶은 충동이 일긴 하지만.... ^^

 

그런데, 아예 못 풀 정도는 아니라서.... 좀 해메다보면 갑자기 번쩍 !!!

 

게임 중간에 갑자기 스토리 진행하면서 나오는 에니메이션을 보는 재미가 쏠쏠하다 ^^

 

 

 

화면캡쳐를 위해 PCSX2로 게임을 했는데 전투씬을 들어가거나 하면 화면이 엄청 깨지는 것이다.

그래서 무서운 분의 눈을 피해서 거실로 슬금슬금 걸아가... PS2를 키고 게임을 했었다.

 

하지만, 블로그에 포스팅 하려면 화면 캡쳐가 좀 필요한데... 아쉬운데....

 

PCSX2에서  Renderer 부분을 Software로 변경을 하니까 화면이 안깨지고 진행이 되었다.

하지만 화질이 좀.... 게임은 그냥 PS2로 해야겠다 ^^

 

 

반응형

출처: https://www.whatwant.com

 

[ Terminology & Problem ]

이번에 살펴보고자 하는 알고리즘은 "Longest Common Subsequence (LCS)" 이다.
어떤 문제를 해결하고자 하는 것인지 설명하기 전에 용어에 대한 정의부터 살펴보겠다.

 

출처: https://www.whatwant.com

 

여기에서 주의깊게 살펴봐야 할 것은 "Substring"인데, 연속적인 character를 의미한다.

 

출처: https://www.whatwant.com

 

반면, "Subsequence"는 비연속적인 character 순서를 포함한다.

 

출처: https://www.whatwant.com

 

2개의 string이 주어졌을 때, 공통적으로 있는 subsequence를 "Common Subsequence"라고 한다.

그리고 "Common Subsequence" 중에서 가장 긴 길이를 갖는 것을 "Longest Common Subsequence (LCS)"라고 한다.

 

이런 LCS를 구하는 방법을 찾는 것이 이번 목표이다 ^^

 

[Brute force approach]

착실하게 (무식하게?) 찾는 방법은 다음과 같다.

 

출처: https://www.whatwant.com

 

당연히 이렇게 찾는 것은 말이 안된다.

입력 string의 갯수가 n개라고 했을 때 2의 n승만큼 subsequence가 나오기 때문이다.

 

[Notation]

이후 설명할 내용에서 사용하는 notation을 정리하면 다음과 같다.

 

 

[Idea]

똑똑하게 해결하기 위한 아이디어는 다음과 같다.

 

출처: https://www.whatwant.com

 

복잡해보이는데, 가만히 살펴보면 엄청 당연한 이야기를 하고 있다.

 

특정 위치의 chracter가 같다면 LCS는 그 같은 값은 일단 LCS에 포함되는 것이고,

각 입력 string에서 동일한 값보다 1씩 작은 string의 LCS값을 더해주면 전체 LCS가 된다.

 

반면, 특정 위치의 chracter가 같지 않다면 LCS는 입력 string중 하나의 값을 1 차감한 내역으로 다시 LCS를 구하면 된다.

 

 

[ Longest Common Subsequece - Dynamic Programming Algorithm ]

위의 아이디어를 정리하면 다음과 같은 알고리즘이 된다.

 

 

이걸 어떻게 하는 것인지 살펴보자.

 

다음과 같은 2개의 string이 입력되었을 때 다음과 같은 표를 그리고 초기화 하자.

  - X = ABCBDAB

  - Y = BDCABA

 

출처: https://www.whatwant.com

 

앞에서 정리한 알고리즘을 기반으로 하나씩 값을 채워나가면 된다.

 

출처: https://www.whatwant.com

 

① x ≠ y 이므로 둘 중 큰 값 선택해야 하는데, 둘 모두 0이므로, 0

② ③ 상동

④ ⑥ x = y 이므로, 왼쪽 대각선 위의 값 + 1

⑤ x ≠ y 이므로 둘 중 큰 값 선택해야 하는데, ④ 값이 1이므로, 1

 

그리고, 어느 곳에서 값을 받아갔는지 화살표로 표기 해줘야 한다.

 

이런식으로 하나씩 값을 작성해 나가면 다음과 같이 된다.

 

출처: https://www.whatwant.com

 

LCS값이 어떻게 되었는지는 다음과 같이 추적해볼 수 있다.

 

출처: https://www.whatwant.com

 

화살표를 보면 알겠지만, 정답이 하나만 있는 것은 아니다.

 

출처: https://www.whatwant.com

 

[Pseudo Code]

손으로 진행했던 것을 코드로 만들어 보자.

 

출처: https://www.whatwant.com

 

손으로 진행했던 것과 차이가 있는 부분 위주로만 설명해봤다.

위 표에서 화살표를 살짝 끄적였는데, code에서는 b array를 통해 기록하도록 했다.

 

결과를 출력하기 위한 코드는 다음과 같다.

 

 

[Time & Space]

code를 보면 직관적으로 파악 가능한 것 처럼 Time complexity는 다음과 같다.

 

 

Space는 b array + c array 공간이 추가적으로 필요하기에 다음과 같다.

 

 

그런데, Space를 줄일 수 있는 경우가 있다.

실제 String 정보까지는 필요없고, 길이값만 필요하다고 하면 다음과 같이 작은 space만 필요로 한다.

 

 

또 다른 경우로는 다음과 같은 case가 있을 수 있다.

 

출처: https://www.whatwant.com

 

LCS에 대해서는 여기까지~

반응형

라이선스 이슈를 피해서 Anaconda 사용하는 방법에 대해서 이미 포스팅을 했었다.

  - 회사에서 Anaconda 사용하기 (Miniconda + conda-forge)

 

 

그런데, Ubuntu 운영체제를 기준으로 작성했다보니

Windows 환경을 사용하는 분들의 불만 아닌 불만이 있는 것 같아서... Windows 버전도 추가로 작성해본다.

 

① Miniconda 설치

② conda-forge 등록

③ conda 가상환경 생성

④ Jupyter Notebook 설치 

 

 

 

① Miniconda 설치

  - Windows 버전의 Miniconda3 Installer를 다운로드 받아서 설치하면 된다.

    . https://docs.anaconda.com/free/miniconda/

 

Miniconda

 

  - 약 78MB 정도의 용량의 설치파일이 다운로드 된다.

 

Installer

 

  - 이후 옵션은 모두 default로 해서 설치를 진행하도록 하자 (경로 등록 등도 일단 그냥 무시하자)

 

 

Complete

 

  - 우리는 설명서 따위는 보지 않는 ...... ^^

 

② conda-forge 등록

  - Windows 키보드를 눌러보면 새로 설치된 앱을 확인할 수 있다.

 

실행

 

  - 본인 취향대로 골라서 실행하면 되지만, 여기에서는 밑에 있는 "Anaconda Prompt (miniconda3)"를 선택했다.

 

prompt

 

  - 명령어는 다음과 같다.

(base) C:\Users\whatw>conda config --add channels conda-forge

(base) C:\Users\whatw>conda config --set channel_priority strict

(base) C:\Users\whatw>conda config --show channels
channels:
  - conda-forge
  - defaults

 

③ conda 가상환경 생성

  - 일단 conda 가상환경을 생성해야 한다. 이 때, 사용할 Python 버전을 지정하면 된다.

 

conda

 

  - 중간에 계속 설치를 진행할 것인지 묻는 부분이 나오는데, 그냥 엔터 때리면(?) 된다.

(base) C:\Users\whatw>conda create -n p39 python=3.9.15
Channels:
 - conda-forge
 - defaults
Platform: win-64
Collecting package metadata (repodata.json): done

...

done
#
# To activate this environment, use
#
#     $ conda activate p39
#
# To deactivate an active environment, use
#
#     $ conda deactivate

 

  - 설치 완료 부분을 보면 가상환경을 실행하는 방법과 종료하는 방법을 알려준다.

 

④ Jupyter Notebook 설치

  - 앞에서 생성한 가상환경 內 Jupyter Notebook을 설치해야하기에 우선 가상환경을 실행하자.

 

active

 

  - 프롬프트 앞 부분을 보면 현재 실행중인 환경 정보를 알려준다. 항상 신경쓰자.

 

  - 이제는 Jupyter Notebook 패키지를 설치하자.

(p39) C:\Users\whatw>pip install jupyter notebook ipykernel
Collecting jupyter
  Downloading jupyter-1.0.0-py2.py3-none-any.whl.metadata (995 bytes)
Collecting notebook
  Downloading notebook-7.1.2-py3-none-any.whl.metadata (10 kB)

...

 

  - 커널도 등록하자

(p39) C:\Users\whatw>python -m ipykernel install --user --name p39 --display-name "python 3.9"
Installed kernelspec p39 in C:\Users\whatw\AppData\Roaming\jupyter\kernels\p39

 

  - 'Jupyter Notebook'이 실행될 경로를 하나 만든 뒤, 그 곳에서 실행하자.

 

execute

 

  - 갑자기 웹브라우저가 아래와 같이 실행되면 성공한 것이다.

 

jupyter notebook

 

  - 오른쪽 "New" 버튼을 통해 notebook을 생성하자.

 

hello

 

잘 된다!

 

반응형

출처 : https://www.whatwant.com

 

이번에 살펴볼 것은 한글로 말하자면, "막대 자르기" 알고리즘이다.

어떤 문제를 해결하기 위한 알고리즘인지 알아보자.

 

[Problem]

n만큼의 길이를 갖고 있는 막대기가 있다고 하자.

 

출처 : https://www.whatwant.com

 

이 막대기를 잘라서 팔아야 하는데, 길이에 따라서 판매되는 가격이 다르다고 했을 때

어떻게 잘라서 팔아야 최대 이익이 나오는지를 찾아내야 하는 것이 문제이다.

 

 

위와 같이 막대기 길이에 따른 수익은 제시가 된다.

알아야 할 notation 규칙은 다음과 같다.

 

 

[Brute force approach]

"n = 4" 만큼의 길이를 갖고 있는 막대기가 있고, 길이에 따른 가격은 다음과 같다.

 

출처 : https://www.whatwant.com

 

이 때, 나올 수 있는 모든 경우의 수를 다 살펴보자면 다음과 같다.

 

출처 : https://www.whatwant.com

 

최대 수익을 얻기 위해서는 ⑶번과 같이 2개 묶음으로 나누는 경우가 10만큼의 수익을 얻을 수 있다.

그런데, 이처럼 모든 경우의 수를 나열해서 모두 계산해보기에는 너무 비효율적이다.

 

[Rod-Cutting Algorithm]

일단 다음과 같은 계산식을 살펴보자.

 

 

n 길이의 막대기가 있을 때, i 길이의 가격과  'n - i' 길이일 때의 최대 수익의 합이 최대인 i값을 찾는 것을 의미 한다.

 

출처 : https://www.whatwant.com

 

다음과 같은 문제가 주어졌다고 해보자.

 

 

r[i], s[i] 값은 다음과 같이 계산해볼 수 있다.

 

 

그러면 다음과 같은 결과를 얻을 수 있다.

 

 

이렇게 만들어진 표가 있다면,

8 길이만큼의 막대기가 주어졌을 때 다음과 같이 활용할 수 있다.

 

출처 : https://www.whatwant.com

 

[Pseudo Code]

 

 

[Time & Space]

이 알고리즘에서는 r[n], s[n] 값을 저장하기 위한 메모리 공간을 필요로 한다.

길이 n 값에 선형으로 비례하는 만큼 사용하기 때문에 다음과 같이 정리할 수 있다.

 

 

소요 시간은 Pseudo Code를 보면 중복 for문이 사용되는 부분을 잘 살펴봐야 하는데,

다음과 같이 정리 해볼 수 있다.

 

 

수고하셨습니다 !!!

반응형

+ Recent posts