Tagged: 리눅스

DNF 사용하기

CentOS 8 로 넘어오면서 기본 패키지 매니지먼트로 dnf 가 되었다. 여전히 yum 을 지원하지만 앞으로는 dnf 로 쭉 간다고 하니 이참에 배워보자고 생각하지만….

겁나 빡치는게, 이제 그만 바꿨으면 한다. 뭔 yum 정도로도 충분히 잘 쓰고 있고 괜찮다고 싶다. 무슨 겁나 가볍네, 더 빠르네 어케 좋네… 응 yum 도 그렇게 느리고 그렇게 무겁지도 않아! 도대체 뭘 할때마다 갈아 엎고 이걸 새로 배우라고 하니.. 뭐 어쩌것나.. 그렇게 하겠다는데, 닥치고 배워야지!

dnf

햐.. 쓰기도 귀찮다… “DNF is the next upcoming major version of YUM, a package manager for RPM-based Linux distributions” 이렇게 맨 페이지에 설명이 나온다.

사용법

사용법은 아주 간단하다. yum 의 기본 사용법은 대동소이하다고 하겠다.

dnf사용법
ZSH
1
2
3
4
5
6
7
8
9
10
]# dnf check-update
]# dnf update
]# dnf install kernel
]# dnf remove kernel
]# dnf info kernel
]# dnf clean all
]# dnf history
 
]# dnf repolist
]# dnf repoinfo

이정도만 알아도 패키지를 다루는데는 문제가 없을 것이다.

CentOS에서 SNMP 설치 및 설정하기

SNMP(Simple Network Management Protocol) 은 원래 네트워크 장비를 관리하기 위한 통신 규약입니다. 그런데, 이제는 네트워크 장비뿐만아니라 컴퓨터, 전자장비까지 확장해서 사용하고 있습니다. 리눅스 시스템에서도 SNMP를 사용할 수 있습니다.

이를 이용하면 SNMP 를 이용해서 중앙집중식으로 각각의 장비들의 자원, 자원사용량등을 장비에 거의 모든 것을 알 수 있고 가지고 올 수 있습니다. 저의 경우에는 Cacti 라는 시스템 자원 모니터링 시스템에서 원격 시스템의 자원 사용량을 가지고 오기 위해서 각 서버마다 SNMP를 사용합니다.

준비

이 문서는 다음과 같은 환경에서 작성되었습니다.

  • CentOS 7
  • X86_64

SNMP는 서버/클라언트 구조를 가지고 있습니다. 중앙 집중식으로 한 곳에서 정보를 모을 경우에는 중앙 서버를 제외하고 SNMP 데몬만 설치해주면 됩니다.

설치

설치는 Yum 을 이용해 다음과 같이 해주면 됩니다.

SNMP 설치
Shell
1
yum install net-snmp [ net-snmp-utils ]

위에 뒷부분 ‘net-snmp-utils’ 는 SNMP 데몬하고는 아무런 관련이 없기 때문에 설치를 않해되 되지만 SNMP 데몬의 제대로 동작하는지를 테스트하기 위해서는 설치해주는 것이 좋습니다. ‘net-snmp-utils’ 는 말 그대로 SNMP를 다루기위한 여러가지 명령어들이 들어 있습니다.

설정

CentOS7 의 특징은 데몬이 실행될때에 옵션을 제공해 줄 수 있는데, 이를 위해서 ‘/etc/sysconfig’ 디렉토리에 데몬이름으로 파일을 가지게 됩니다. 그러면 데몬 실행 프로그램에서 이를 import 해서 사용하곤 하는데 SNMP 데몬도 이와 같습니다.

먼저 데몬 실행 옵션을 다음과 같이 설정 해줍니다.

SNMP 데몬 실행 옵션
Vim
1
OPTIONS="-LS1-5d -Lf /dev/null -p /var/run/snmpd.pid"

위 옵션들은 다음과 같습니다.

  • -Ls 는 로그 메시지 stderr, stdout 으로 내보내고 로그레벨을 정한다. 기본은 -Lsd 로 d 는 LOG_DEBUG 을 말한다. 로그의 수준은 0 ~ 7 까지 존재하는데 다음과 같다.
    SNMPD 로그 레벨
    Default
    1
    2
    3
    4
    5
    6
    7
    8
    0 or ! for LOG_EMERG,
    1 or a for LOG_ALERT,
    2 or c for LOG_CRIT,
    3 or e for LOG_ERR,
    4 or w for LOG_WARNING,
    5 or n for LOG_NOTICE,
    6 or i for LOG_INFO, and
    7 or d for LOG_DEBUG.

    이는 -LSwd 나 -LS4d 식으로 숫자와 알파벳으로 지정할 수 있다. -LSed / -LS3d 같은 예제이다. 또, -LS1-5d 처럼 로그레벨 수준을 어디서 어디까지로 정할 수도 있다. 위 예제에서는 데몬 메시지를 syslog 로 보내는데 로그 레벨 1~5까지를 보내라는 뜻이다.
  • -Lf 는 지정한 파일로 로그 메시지를 보낸다. 위 예제에서는 /dev/null 임으로 로그 메시지를 삭제하는 효과를 보인다.
  • -p 는 pid 파일을 지정해 준다.

다음으로 SNMP 자체 설정을 합니다. 아래의 예제는 시스템 자원을 읽기 전용으로만 설정하는 것입니다.

/etc/snmp/snmpd.conf
Vim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#       sec.name  source          community
com2sec readonly        192.168.96.0/20 Nrc65amr
com2sec readonly        127.0.0.1       Nrc65amr
 
#       groupName      securityModel securityName
group   MyROGroup v1           readonly
group   MyROGroup v2c           readonly
group   MyROGroup usm                   readonly
 
view    all     included        .1      80
 
#       group          context sec.model sec.level prefix read   write  notif
access  MyROGroup ""      any       noauth    exact  all none none
 
syslocation Unknown (edit /etc/snmp/snmpd.conf)
syscontact Root <root@localhost> (configure /etc/snmp/snmp.local.conf)

SNMP 설정은 ‘sec.name’ 별로 설정을 할 수 있습니다. sec.name 을 여러게 정의하면 group도 여러개 설정할  수 있고 이렇게 되면 access 도 여러개 설정할 수 있습니다. 주목할 것은 access 에서 뒷부분에 read, write, notif 가 보이는데, 위 예제가 시스템 자원을 읽기만 할 것이기 때문에 read 부분만 all 로 하고 나머지를 none 으로 한 것입니다.

마지막으로 systemd 에 snmpd 를 활성화 해주고 시작해 줍니다.

systemd 에 snmpd 를 활성화하고 시작
Shell
1
2
systemctl enable snmpd
systemctl start snmpd

로깅 변경

위 설정대로 하면 snmpd 로그가 /var/log/messages 에 저장이 됩니다. 하지만 /var/log/messages 는 커널 메시지도 저장되고 하는 중요한 것이여서 별도 파일에 저장하는 것이 좋습니다.

이를 위해서 snmpd 를 위한 별도의 로그 파일 설정을 해주는데, 먼저 /etc/sysconfig/snmpd 설정을 다음과같이 바꿔 줍니다.

rsyslog 를 위한 snmpd 설정
Vim
1
OPTIONS="-Ls6 -Lf /dev/null -p /var/run/snmpd.pid"

rsyslog 데몬에서 다음과 같이 설정해 줍니다.

rsyslog 에 snmpd 로그 설정
Vim
1
2
*.info;mail.none;authpriv.none;cron.none;local6.none                /var/log/messages
local6.* /var/log/snmpd.log

위에 예제에서 첫번째라인은 로그레벨 6 에 대해서는 /var/log/message 에서 제외하고 로그레벨6은 /var/log/snmpd.log 에 저장하도록 지정한 것입니다.

이렇게 해주고 데몬을 재시작 해줍니다.

snmpd, rsyslog 데몬 재시작
Shell
1
2
systemctl restart snmpd
systemctl restart rsyslog

로그 로테이션도 설정해 줍니다.

로그 로테이션
Vim
1
2
3
4
5
6
7
8
9
10
--- /etc/logrotate.d/syslog.orig 2015-12-29 22:10:00.089000000 +0900
+++ /etc/logrotate.d/syslog 2015-12-29 22:10:44.926000000 +0900
@@ -3,6 +3,7 @@
/var/log/messages
/var/log/secure
/var/log/spooler
+/var/log/snmpd.log
{
     missingok
     sharedscripts

만일 일일이 출력하고 싶지 않다면 /etc/snmp/snmpd.conf 파일에 다음과 같이 설정해 줍니다.

SNMP 로그 출력 않하기.
Vim
1
dontLogTCPWrappersConnects yes

 

Firewalld 설정

CentOS 7 에서는 iptables 에서 firewalld 로 변경되었습니다. snmpd 를 위해 firewalld 를 설정해 줘야 합니다.

먼저 snmp 관련해서 방화벽 열기위한 정보를 xml 파일로 작성해 줍니다.

vim /etc/firewalld/services/snmp.xml
XHTML
1
2
3
4
5
6
<?xml version="1.0" encoding="utf-8"?>
<service>
  <short>SNMP</short>
  <description>SNMP protocol</description>
  <port protocol="udp" port="161"/>
</service>

그리고 다음과 같이 public zone 에 등록해줍니다.

firewalld에 snmp 등록.
Shell
1
2
3
firewall-cmd --reload
firewall-cmd --zone=public --add-service snmp --permanent
firewall-cmd --reload

 

Nginx 설정.

이 문서는 Nginx  설정에 대한 문서 입니다. 계속적으로 업데이트가 됩니다.

요청 메소드 제한

요청 메소드는 GET, HEAD, POST, PUT, DELETE 등이 있다. 문제는 대부분 웹 서비스는 GET, HEAD, POST 만 필요로한다는 것이다. Nginx 에서 이를 다음과 같이 제한 할 수 있다.

GZIP 설정

 

Nginx + PHP-FPM + MariaDB 설치 (CentOS 7)

과거에는 APM (Apache + PHP + MySQL)이 인기있는 플랫폼이 였지만 최근에는 Nginx 가 나오고 PHP-FPM 이 나오면서 NPM 으로 많이 대체되고 있는 추세에 있습니다. 이 글은 Nginx,PHP-FPM, MariaDB 설치에 관한 것입니다.

준비

이 글에서 NPM을 설치하는 환경은 다음과 같습니다.

  • CentOS 7.2.1511
  • X86_64
  • Selinux Disable
  • 작성시간: 2015. 12. 27

설치하는 방법은 CentOS 7 에서 제공하는 패키지 관리 프로그램인 YUM을 이용하는 것입니다. 다음과 같이 CentOS 7 를 최신 버전으로 만듭니다.

 

PHP 설치

다음과같이 YUM 을 이용해서 설치해 줍니다.

PHP 설치.
Shell
1
yum install php-fpm php-mysql php-cli

php-mysql 은 MariaDB 와 연동하기 위한 것임으로 함게 설치해 줍니다.

systemctl 에 등록하고 시작해 줍니다.

systemctl 등록 및 시작.
Shell
1
2
systemctl enable php-fpm.service
systemctl start php-fpm.service

php-fpm 의 pool 설정을 다음과 같이 해줍니다.

vim /etc/php-fpm.d/www.conf
Vim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[www]
listen = 127.0.0.1:9000
listen.owner = nginx
listen.group = nginx
listen.mode = 0660
user = cacti
group = cacti
pm = dynamic
pm.max_children = 50
pm.start_servers = 5
pm.min_spare_servers = 5
pm.max_spare_servers = 35
chdir = /home/cacti/www/
 
php_value[session.save_handler] = files
php_value[session.save_path]    = /var/lib/php/cacti_session

세션(Session) 디렉토리의 소유권을 cacti 로 변경해 줍니다.

세션 디렉토리 소유권 변경
Shell
1
chown cacti: -R /var/lib/php/cacti_session

 

MariaDB 설치

MariaDB 의 최신 버전 설치를 위해서 다음과 같이 YUM 저장소를 추가해 줍니다. YUM 저장소 추가는 다음 내용을 파일로 저장해주면 됩니다.

vim /etc/yum.repos.d/MariaDB.repo
Vim
1
2
3
4
5
[mariadb]
name = MariaDB
baseurl = http://yum.mariadb.org/10.1/centos7-amd64
gpgkey=https://yum.mariadb.org/RPM-GPG-KEY-MariaDB
gpgcheck=1

현재 MariaDB 의 최신버전은 10.1 이기 때문에 baseurl 에 버전이 정확해야 합니다. 다음과 같이 설치를 해줍니다.

MariaDB 설치
Shell
1
yum install MariaDB-server MariaDB-client

systemctl 에 등록을 해주고 데몬을 시작해 줍니다.

systemctl 에 서비스 등록 및 시작
Shell
1
2
systemctl enable mariadb.service
systemctl start mariadb.service

mysql_secure_installation 을 실행해서 root 패스워드와 불필요한 데이터베이스를 삭제 합니다.

mysql_secure_installation 실행.
Shell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
[root@localhost ~]# mysql_secure_installation
....
Enter current password for root (enter for none): [그냥 엔터]
OK, successfully used password, moving on...
....
Set root password? [Y/n] Y
New password:
Re-enter new password:
Password updated successfully!
Reloading privilege tables..
... Success!
.....
Remove anonymous users? [Y/n] y
... Success!
.....
Disallow root login remotely? [Y/n] y
... Success!
.....
Remove test database and access to it? [Y/n] y
- Dropping test database...
... Success!
- Removing privileges on test database...
... Success!
.....
Reload privilege tables now? [Y/n] y
... Success!
[root@localhost ~]# systemctl restart mariadb # mariadb 재시작.

 

Nginx 설치

Nginx 의 최신 버전 설치를 위해서 다음과 같이 YUM 저장소를 추가해 줍니다. YUM 저장소 추가는 다음 내용을 파일로 저장해주면 됩니다.

vim /etc/yum.repos.d/Nginx.repo
Vim
1
2
3
4
5
6
[nginx]
name=nginx repo
baseurl=http://nginx.org/packages/centos/$releasever/$basearch/
gpgkey=http://nginx.org/keys/nginx_signing.key
gpgcheck=0
enabled=1

cacti 서비스를 예를들어 다음과 같이 cacti.conf 파일을 작성합니다.

vim /etc/nginx/conf.d/cacti.conf
Vim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
server {
    listen       80;
    server_name  cacti.system.com;
 
    #charset koi8-r;
    #access_log  /var/log/nginx/log/host.access.log  main;
 
    location / {
        root   /home/cacti/www
        index  index.html index.htm index.php;
    }
 
    #error_page  404              /404.html;
 
    # redirect server error pages to the static page /50x.html
    #
    error_page   500 502 503 504  /50x.html;
    location = /50x.html {
        root   /usr/share/nginx/html;
    }
 
    # proxy the PHP scripts to Apache listening on 127.0.0.1:80
    #
    #location ~ \.php$ {
    #    proxy_pass   http://127.0.0.1;
    #}
 
    # pass the PHP scripts to FastCGI server listening on 127.0.0.1:9000
    #
    location ~ \.php$ {
        root   /home/cacti/www;
        fastcgi_pass 127.0.0.1:9000;
        fastcgi_index index.php;
        fastcgi_param   SCRIPT_FILENAME  $document_root$fastcgi_script_name;
        include fastcgi_params;
    }
}

웹 서비스를 위한 홈 디렉토리가 ‘/home/cacti’ 를 만들어주고 www 디렉토리를 생성해 줍니다.

cacti 사용자 생성.
Shell
1
2
3
4
]# useradd cacti
]# chmod 755 /home/cacti
]# su - cacti
]$ mkdir www

nginx 문법체크를 하고 systemctl 에 서비스를 등록하고 서비스를 시작해 줍니다.

nginx 문법체크, systemctl 등록, systemctl nginx 시작.
Shell
1
2
3
]# nginx -t
]# systemctl enable nginx.service
]# systemctl start nginx.service

80(http) 방화벽 설정

80 포트, 즉 HTTP 를 위한 방화벽 설정을 다음과 같이 해줍니다.

80(HTTP) 포트 방화벽 오픈.
Shell
1
2
]# firewall-cmd --permanent --zone=public --add-service=http
]# firewall-cmd --reload

 

 

DNS amplification DDos attacks (DNS 증폭 DDos 공격)

최근에 관리하는 서버에 트래픽이 몰리는 현상이 발생했다. 웹 서비스 트래픽도 아니기에 뭔가 싶어 봤더니 53 포트를 통한 input 트래픽이였다. 그래서 ngrep 으로 53 포트를 모니터링 하니 대략 다음과 같이 나왔다.

뭔가 자꾸 DNS 서버에 쿼리(Query)를 보내고 있었고 이로 인해서 트래픽이 발생하는게 분명했다.

DNS amplification DDos attacks (DNS 증폭 DDos 공격)

‘DNS amplification DDos Attacks’ 는 DNS 증폭 DDos 공격으로 불리운다. 왜 ‘증폭’ 일까?

DDos 는 대량의 트래픽이 필요하다. 초당 수십 Gbps 를 유발시켜야 하는데 이렇게 할려면 많은 장비가 필요하다. 그러다보니 DDos 공격을 개인이 한다는 건 무리가 있다. 그런데, DNS 서버는 이런 많은 장비 없이도 대량의 트래픽을 유발시킬 수 있는 구조적인 면을 안고 있다.

DNS 는 인터넷을 위해서는 반드시 존재해야만 하는 서버다. 인터넷 전화번호부 라고도 불리우는 서버로 인간의 주로 사용하는 도메인을 컴퓨터가 알아볼수 있는 IP 주소로 변환한다. 브라우저 주소창에 도메인을 입력하면 DNS 서버에 그 도메인의 IP 주소를 질의(Query) 한 후에 받은 IP를 가지고 실제 서버에 접속하는 구조다.

이렇게 DNS 는 질의(Query)를 받아 응답한다. 그런데, DNS 에 보낼 수 있는 질의(Query)는 다양하며 그중에서 재귀적 질의(Recursive Query) 가 문제가 된다. 재귀적 쿼리는 DNS 서버가 보유한 도메인 리스트에 질의한 내용이 없을 경우 이를 다른 DNS 서버에 질의하는 것을 말한다.

예를들어 DNS-A 이라는 DNS 서버에 naver.com 을 질의했다면 DNS-A 서버는 먼저 자신의 도메인 리스트에 naver.com 이 있는지 찾게 된다. 없다면 최상의 DNS 서버인 ROOT-DNS 서버에 DNS-A 서버가 naver.com 서버의 IP가 무엇인지 질의하게 된다. ROOT-DNS 서버는 naver.com 주소의 TLD(Top Level Domain) 인 .com DNS 서버에 물어보라고 DNS-A 서버에 알려주고 다시 DNS-A 서버는 .com TLD 서버에 질의한다. .com TLD 서버는 naver.com 네임서버에게 물어보라고 응답하고 DNS-A 서버는 드디어 naver.com 을 가진 DNS 서버에 IP를 요청하고 이를 받아서 클라이언트에게 응답하는 것으로 임무는 종료 된다.

  • OS에 설정된 DNS-A 서버에 naver.com 의 IP를 요청한다.
  • DNS-A 서버는 자신의 도메인 리스트나 도메인 캐쉬에서 naver.com IP를 찾는다. 있다면 응답하고 끝나게되고 없다면 다음으로 진행.
  • DNS-A 서버에 naver.com 이 없음을 알게된 서버는 최상의 DNS 서버은 ROOT-DNS 에 naver.com IP를 질의한다.
  • ROOT-DNS 는 naver.com 의 TLD (Top Level Domain) 인 .com DNS 에 물어보라고 DNS-A 에게 알려준다.
  • .com DNS 서버는 naver.com 도메인의 DNS 서버에게 물어보라고 DNS-A 에게 알려준다.
  • 마침내 DNS-A 서버는 naver.com 도메인의 DNS 서버에 IP가 뭐냐고 질의한다.

여기에 질의 내용을 ‘ANY’ 로 할 경우에는 응답하는 양이 많아진다. 도메인의 DNS 구성에는 MX, A, TXT, CNAME 등 다양하다. 질의할때에는 어떤 타입을 원하는지를 정할 수 있게 되는데, ANY 타입의 질의는 도메인이 가지고 있는 모든 정보를 원하게 된다.

결국 재귀적 질의와 ANY 타입의 질의를 결합해 초당 수백건의 도메인 질의를 보내게 되면 DNS 서버는 이 질의에 응하게되고 수십Gbps 의 응답 트래픽을 발생시키게 된다. 이것이 바로 ‘DNS 증폭 DDos 공격’ 이다.

이 공격은 대부분 DNS 의 잘못된 설정 탓이다. BIND 9 의 경우에는 재귀적 질의를 맞음으로써 간단하게 해결할 수 있다.

BIND 9 의 기본 설정은 ‘recursion yes’ 임으로 이를 바꿈으써 ‘DNS 증폭 DDos 공격’을 막을 수 있다. 이 공격을 막았을 경우 로그는 다음과 같이 쌓인다.

 

gitlab 패스워드 리셋하기

gitlab 패스워드 리셋하기

Gitlab 을 사용하다가 갑자기 패스워드를 잊어버리는 경우가 생길 수 있습니다. 이럴때 보통 Web 에서 ‘Fogot your password’ 링크를 클릭하고 리셋될 패스워드를 가입할때 적어놓은 E-mail 로 발송을 해줍니다. 그런데, E-mail 주소가 없는 거라면 패스워드를 리셋할 수가 없어서 로그인을 못하게 됩니다.

이럴때는 Gitlab 서버에 터미널로 로그인을 해서 gitlab-rails console을 실행하고 패스워드를 바꿀 수 있습니다. 먼저 gitlab-rails console로 접속을 합니다.

gitlab-rails Console 로그인.
Default
1
2
3
4
]# gitlab-rails console
Loading production environment (Rails 4.2.4)
irb(main):001:0>
irb(main):002:0*

여기서 만일 E-mail 주소를 정확하게 알고 있다면 다음과 같이 user 객체를 지정할 수 있습니다.

E-mail 로 사용자 검색.
Ruby
1
2
irb(main):005:0* user = User.find_by(email: 'admin@local.host')
=> nil

그런데 위와같이 ‘nil’ 로 나오면 없는 사용자라는 거죠. 그럼 다음은 id 로 검색을 합니다. id 는 내부 데이터베이스에 저장될때에  사용되어진 primary key 인듯 합니다. 보통 사용자가 1명이라면 이 방법이 통하지만 수십명이면 안되겠죠.. (전 집에서 개인적으로 사용하기 때문에 사용자가 1명인 경우입니다. )

id 로 검색.
Ruby
1
2
irb(main):018:0* user = User.where(id: 1).first
=> #<User id: 1, email: "admin@example.com",

뭔가 나오네요… 그런데 이마저도 모르겠다!! 그러면 사용자 로그인 아이디로 검색을 해봅니다.

사용자 로그인 아이디로 검색
Ruby
1
2
rb(main):006:0* user = User.find_by(username: 'root')
=> #<User id: 1, email: "admin@example.com",

뭔가 나왔군요. 그러면 user 객체가 생성되어진 겁니다.

패스워드는 다음과 같이 바꾸면 됩니다.

패스워드 변경.
Ruby
1
2
3
4
5
6
rb(main):019:0> user.password = 'reset_password'
=> "reset_password"
irb(main):020:0> user.password_confirmation = 'reset_password'
=> "reset_password"
irb(main):021:0> user.save
=> true

그리고 바로 Web 에서 변경된 패스워드로 로그인이 가능합니다.

Suspend 된 게스트 시작 않될때 해결 방법.

Suspend 는 보통 게스트를 Paused 상태로 만드는 것을 말한다. 이는 동작상태를 하드디스크에 그대로 저장하고 끝내는 것을 말하며 이를 재시작하는 것을 Resume 이라고 한다. 명령어로는 그냥 start 명령어를 쓰지만 Suspend 에서는 부팅이 아닌 저장하고 끝난 부분을 풀고 바로 시작되는 것이 다르다.

그런데, Suspend 한 이미지를 시작하려고 할 때에 다음과 같이 오류가 나왔다.

아무리 Resume 을 할려고 하더라도 위와 같은 오류로 시작도 않되었다. 이럴때는 다음과 같이 해서 부티을 시도하는 것이 좋다.

이는 앞에서도 말했듯이 Supsend 될때에 저장된 이미지를 삭제하도록 한다. 앞에서 오류는 바로 이 저장된 이미지를 풀고 Resume 을 하려고 하는 것인데, 이 이미지가 잘못되었것이다. 이럴때는 어쩔수 없이 부팅을 해야하게이 이를 삭제하고 시작하면된다.

알고리즘 – 최대공약수(Great Common Divisor)

분수 알고리즘에서 마지막으로 약분(reduce a Fraction to Lowest Terms) 을 합니다. 약분은 분자와 분모의 최대공약수(GCD, Great Common Divisor)로 나누는 것을 말합니다. 따라서 약분을 하기 위해서는 최대공약수를 구하면 됩니다.

약분, 최대공약수를 구하라.

최대공약수 구하기 1

최대공약수를 구하는 방법은 여러가지가 있는데 그 첫번째로 분자, 분모 두개를 동시에 나누었을때에 나머지가 없는 수를 구하면 됩니다. 1부터 시작해서 분자, 분모 두수중에 작은 수까지 대입해서 하나씩 나누어서 0이 되는지를 찾아보는 겁니다.

최대공약수를 구하는 무한대입법이라고 보시면 됩니다.

작은 수가 무엇인지를 구하기 위해서 min 함수를 이용했습니다. 무한대입법을 이용하기 위해서 for 문을 이용했고, maxDiv 변수에 최대공약수 값을 저장하도록 했습니다.

근데, 이렇게하면 아시겠지만 아주 큰수의 경우에 아주 오래 걸립니다. for 문 그냥 막 돌아야하니까요.

최대공약수 구하기 2 – 뺄셈이용.

이 방법을 유클리드(Euclidean) 방법인지는 모르겠습니다. 유클리드 방법은 나눗셈을 이용하는 방법인데, 이것을 뺄셈으로 변환한 것으로 보이거든요.

두 숫자가 있다고 합시다. 두 숫자를 관호에 넣고 왼쪽엔 큰 숫자, 오른쪽엔 작은 숫자를 넣습니다. 그리고 이 둘을 뺀 값을 제수로 넣습니다. 그리고 다시 큰 수를 왼쪽에 넣고 다시 빼고 나온 값을 다시 제수로 넣고 이를 반복하다 보면 나머지가 0일때에 피제수값이 나오는데 이게 바로 최대공약수 입니다.

(3654, 1365)

이 둘을 빼면 2289 값이 나옵니다. 그러면 3654(제수)를 버리고 다음과 같이 적습니다.

(2289, 1365)

다시 둘을 빼면 다음과 같이 나옵니다.

(924, 1365)

왼쪽에는 항상 큰 숫자여야 해서 이 둘을 교환합니다.

(1365, 924)

이것을 한눈에 알아보도록 표기를 하면 다음과 같습니다.

위와 같은 방법이 되고 마지막에 (0, 21) 이니까 두수의 최대공약수는 21 이 되는 것입니다.

이 방법이 유클리드 호제법과 같다는 이유는 뺄셈하는 방법이지만 제수를 항상 나머지로 다시 넣기 때문입니다. 유클리드 호제법은 나눗셈을 이용해서 나온 나머지를 다시 제수로 넣는 방법인데 둘은 같습니다.

(3654, 1365) = (2289, 1365)

이를 공식으로 쓰면,,,

3654 = 1365*1 + 2289

이는 3654/1365 를 나눈 나머지 2289 랑 같습니다.

여기서 규칙은 한가지, 두수를 비교해서 큰수를 왼쪽에 넣어준다 입니다.

최대공약수 구하기 2 – 나눗셈이용.

이를 유클리드 호제법이라고 합니다. 앞에 뺄셈을 나눗셈으로 바꿔서 하는 방법입니다. 이게 뺄셈보다 좋은 점은 반복적인 뺄셈을 없애줍니다. 규측인 뺄셈과 같습니다.

위와같이 while 문을 이용해서 할수도 있지만 재귀호출(Recusive) 로도 다음과 같이 구현할 수 있습니다.

최대공약수(GCD)를 구했는데, 1이 값으로 나온다면 이는 최대공약수가 없다는 것을 의미합니다. 1은 모든수의 공약수이기 때문입니다.

알고리즘 – 분수(Fraction) 문제

알고리즘 – 분수(Fraction) 문제는 컴퓨터 알고리즘을 시작하는데 좋은 예제입니다. 분수는 어릴적 산수시간에 배운 그게 맞습니다. 1/2, 1/3, 1/4 식 입니다.

분수에는도 사칙연산을 할 수 있습니다. 더하기(add), 빼기(subtract), 곱셈(multiply), 나눗셈(divide) 가 그것입니다. 이를 컴퓨터 프로그램 언어를 이용해서 만들어보는 겁니다.

참고: http://interactivepython.org/runestone/static/pythonds/Introduction/ObjectOrientedProgramminginPythonDefiningClasses.html#a-fraction-class

분수의 정의와 제약사항

분수는 다음과 같이 정의됩니다.

수학에서 분수(分數, fraction)는 a/b 이나  \frac {a} {b} 꼴로 표시한다. 이것은 a를 b로 나눈 값, 즉 a와 b의 비를 뜻하며, 여기서 a는 분자, b는 분모라고 한다. 이 때 분모 b에 0이 들어가는  \frac {a} {0}(a는 상수)라는 수는 정의될 수 없으므로 b≠0 이어야 한다.

From 위키페디아

중요한 것이 분모는 0 이여서는 안됩니다. 또 한가지 이 글에서 제약조건을 걸어야 하는데, 분자와 분모 모두 양수로만 이루어진 분수를 다룹니다. 또, 모두 정수여야 합니다. 이를 정리하면 다음과 같습니다.

  • 분모는 0 이여서는 안됩니다.
  • 분자, 분모는 모두 양의 정수(양수이며 정수)

분수의 덧셈

분수의 덧셈은 먼저 분모를 ‘통분’해야 합니다. 무슨말이냐 하면 덧셈을 하기 위한 두개의 분수들의 분모 크기를 같은 값으로 만드는 것(=분모를 통일하는것)입니다. 예를들어

1/2 + 1/3 이 있다면 분모를 통분하는데 서로서로 분모값을 분자,분모에 곱해주면 됩니다. (1*3)/(2*3) + (1*2)/(3*2) = 3/6 + 2/6 = 5/6

분모가 같아지니까 분자만 그대로 더해주면 됩니다.

분수의 뺄셈

분수의 뺄셈은 분수의 덧셈과 마찬가지로 분모를 통분해주고 분자까리 빼주면 됩니다.

분수의 곳셈

분자는 분자까리, 분모는 분모끼리 곳해주면 끝~

분수의 나눗셈

나누는 분수을 역으로 바꾸고 둘을 곱셈하면 된다.

2/5 나누기 1/3 = 2/5 * 3/1 = 6/5

여기까지가 분수에 관한 수학적 알고리즘입니다.

컴퓨터 알고리즘

컴퓨터 알고리즘은 컴퓨터를 이용해서 문제를 해결하는 방법입니다. 그럴려면 아무래도 프로그래밍을 해야하고 프로그래밍을 위해서는 프로그램 언어를 이용해야 합니다. Python, Java, PHP 등이 여기에 속합니다.

한가지 컴퓨터 알고리즘을 할때에는 선택한 언어의 특성을 이용하는 경우가 있습니다. 예를들어 Python 을 이용할 경우에 내장 메소드를 이용할 수 있는데, 이번 분수 알고리즘에서 이를 사용할 것입니다. 다른 언어로 구현할 경우에는 이러한 Python 의 내장 메소드 기능을 제공하지 않기 때문에 다르게 구현을 해야합니다.

이 말은 결국 컴퓨터 알고리즘을 구현하는데 사용하는 언어에 영향을 어느정도 받는다는 것입니다.

Python 의 특징(python3.4 기준)

Python 은 내장 메소드를 지원합니다. 이는 모든 데이터를 객체로 인식하고 레퍼런스하기 때문에 가능한 것입니다. 단순한 숫자조차도 다양한 메소드를 지원합니다.

숫자 25의 메소드들.
Python
1
2
>>> dir(25)
['__abs__', '__add__', '__and__', '__bool__', '__ceil__', '__class__', '__delattr__', '__dir__', '__divmod__', '__doc__', '__eq__', '__float__', '__floor__', '__floordiv__', '__format__', '__ge__', '__getattribute__', '__getnewargs__', '__gt__', '__hash__', '__index__', '__init__', '__int__', '__invert__', '__le__', '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__', '__new__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__', '__rdivmod__', '__reduce__', '__reduce_ex__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__round__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__setattr__', '__sizeof__', '__str__', '__sub__', '__subclasshook__', '__truediv__', '__trunc__', '__xor__', 'bit_length', 'conjugate', 'denominator', 'from_bytes', 'imag', 'numerator', 'real', 'to_bytes']

위에 보시면 숫자에 대한 내장 메소드를 볼수 있습니다. 이 내장 메소드들은 특정한 연산을할때에 자동으로 작동합니다. 예를들어, ‘__add__’ 의 경우는 숫자를 더할때에 자동적으로 호출되어 작동합니다.

Python
1
2
3
4
>>> 25+10
35
>>> (25).__add__(10)
35

Python 에서 사칙연산에 관한 내장 메소드는 다음과 같습니다.

파이썬 사칙연산 내장 메소드
Default
1
2
3
4
5
6
7
8
>>> (25).__add__(10) # +
35
>>> (25).__sub__(10) # -
15
>>> (25).__mul__(10) # x
250
>>> (25).__truediv__(10) # /
2.5

구현하기

Fraction 이라는 클래스를 만들고 내장 함수들을 조작함으로써 완성함으로써 완성됩니다.

먼저 두개의 숫자를 입력받는걸로 분수를 만듭니다.

Python
1
2
3
4
5
6
#!/usr/bin/python3.4
 
class Fraction:
    def __init__(self, top, bottom):
        self.num = top
        self.den = bottom

그리고 덧셈 테스트를 해봅니다.

Python
1
2
3
4
5
6
7
8
9
10
11
>>> obj = Fraction(2,5)
>>> obj2 = Fraction(3,4)
>>> obj + obj2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'Fraction' and 'Fraction'
>>>
>>> obj.__add__(obj2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Fraction' object has no attribute '__add__'

같은 클래스의 객체를 만들어서 덧셈을 해보면 저렇게 내장 메소드가 없다라고 나옵니다. 그러면 저 내장 메소드를 만들어주면 됩니다.

Python
1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/python3.4
 
class Fraction:
    def __init__(self, top, bottom):
        self.num = top
        self.den = bottom
 
    def __add__(self, otherfraction):
        newnum = (self.num*otherfraction.den) + (otherfraction.num*self.den)
        newden = self.den*otherfraction.den
 
        print(newnum, '/', newden)

위와같이 덧셈 내장 메소드를 정의해주고 다음과 같이 테스트를 합니다.

Shell
1
2
3
4
5
6
7
>>> from Fraction import *
>>>
>>> obj = Fraction(2,5)
>>> obj2 = Fraction(3,4)
>>>
>>> obj + obj2
23 / 20

잘 되네요. 뺄셈, 곱셈, 나눗셈은 앞에서 말한 방법대로 내장 메소드를 이용해서 구현하면 됩니다.

분수의 사칙연산
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/python3.4
 
class Fraction:
    def __init__(self, top, bottom):
        if top < 0 or top == 0:
            raise RuntimeError("numerator must be above 0")
        if bottom < 0 or bottom == 0:
            raise RuntimeError("denominator must be above 0")
 
        self.num = top
        self.den = bottom
 
    def __add__(self, otherfraction):
        newnum = (self.num*otherfraction.den) + (otherfraction.num*self.den)
        newden = self.den*otherfraction.den
 
        print(newnum, '/', newden)
 
    def __sub__(self, otherfraction):
        newnum = (self.num*otherfraction.den) - (otherfraction.num*self.den)
        newden = self.den*otherfraction.den
 
        print(newnum, '/', newden)
 
    def __mul__(self, otherfraction):
        newnum = self.num*otherfraction.num
        newden = self.den*otherfraction.den
 
        print(newnum, '/', newden)
 
    def __truediv__(self, otherfraction):
        newnum = self.num*otherfraction.den
        newden = self.den*otherfraction.num
 
        print(newnum, '/', newden)

제약조건인 음수와 0에 대한 것을 예외로 처리하였습니다. 다음과 같이 실행 합니다.

분수 사칙연산 실행결과
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
>>> from Fraction import *
>>>
>>> obj = Fraction(2,5)
>>> obj2 = Fraction(3,4)
>>>
>>> obj + obj2
23 / 20
>>> obj - obj2
-7 / 20
>>> obj * obj2
6 / 20
>>> obj / obj2
8 / 15

마이너스(-) 표시가 마음에 안들긴하지만 일단 구현까지만하는 걸로..