flask @app.route('/')
def index():
    return render_template('index.html')

 

위와 같이 render_template을 사용하였는데 500 internal server error가 뜬다면

index.html 파일이 templates 폴더 안에 있는지 확인

저작자표시 비영리 변경금지

'Programming > Solution' 카테고리의 다른 글

[MySQL] function 생성: Sequel Pro  (0) 2020.06.27
[Error] JqGrid JsonReader: pager 데이터 출력 안됨(TIMESTAMP)  (1) 2020.06.19
[Error] 'lateinit' modifier is allowed only on mutable properties : Kotlin  (0) 2020.05.27
[Error] UnicodeEncodeError: 'latin-1' codec can't encode characters: Python  (0) 2019.12.08
[Error] flask 실행 실패: Errno 48  (0) 2019.12.07

OSError: [Errno 48] Address already in use

 

-> ps -fA | grep python

 

-> kill 36041

 

-> flask run 재실행

저작자표시 비영리 변경금지

'Programming > Solution' 카테고리의 다른 글

[MySQL] function 생성: Sequel Pro  (0) 2020.06.27
[Error] JqGrid JsonReader: pager 데이터 출력 안됨(TIMESTAMP)  (1) 2020.06.19
[Error] 'lateinit' modifier is allowed only on mutable properties : Kotlin  (0) 2020.05.27
[Error] UnicodeEncodeError: 'latin-1' codec can't encode characters: Python  (0) 2019.12.08
[Error] Flask 500 Internal Server Error: html  (2) 2019.12.07

웹 프로그램을 개발하고 테스트하는 데는 아무런 문제없지만 다른 사람이 쓸 수 있도록 배포하고자 할 경우에 웹서버를 운영하는 것에 어려움이 있다. 직접 서버를 운영하려면 항상 서버용 컴퓨터가 켜져 있어야 하기 때문에 부담스러운 일이다. 다행히 깃허브를 이용하면 무료로 웹호스팅 기능을 사용할 수 있다는 걸 알게 되었다.

 

방법

우선 Repositories를 새로 만들어야한다. 'New' 버튼을 눌러 새로운 저장소를 만든다.

다음과 같이 저장소 이름을 정한 다음 'Create repository' 버튼을 눌러 저장소를 생성한다.

웹 서버가 클라이언트에게 보여줄 페이지가 필요하니 html 파일을 저장소에 업로드하기 위해 'Upload files' 버튼을 누른다.

다음과 같은 내용의 index.html 파일을 업로드 한다.

<html>
    <head>
        <meta charset="utf-8">
    </head>
    <body>
      <h1>
        Hello
      </h1>
    </body>
</html>

 깃허브에서 변경된 사항을 업로드하기 위해서는 변경 사항을 설명하는 comment를 쓰고 'Commit Changes' 버튼을 눌러 변경 사항을 저장한다.

html 파일을 업로드한 후에 'Settings' 버튼을 누른다.

세팅 페이지에서 스크롤을 아래로 내리면 다음과 같이 GitHub Pages라는 부분을 볼 수 있다. None이라고 쓰인 부분을 누른다.

master branch 부분을 누른다.

성공적으로 등록이 된 경우 다음과 같이 주소가 나타난다.

주소를 통해 내가 올린 index.html 파일의 내용을 확인할 수 있다. 

 

https://hynjin.github.io/testForWebHosting/

 

hynjin.github.io

 

 

 

 

도메인 이름 변경

도메인을 <username>.github.io 외에 다른 것으로 하고자 할 경우 아래와 같은 방법이 있다.

생활코딩에서 이에 대한 자세한 설명을 제공하고 있다.

 

github pages에 도메인 연결하기 - 생활코딩

수업소개 나의 서버가 아닌 타사의 서비스를 이용하는 경우에 그 서비스에 도메인 이름을 연결시키는 방법을 알아봅니다. 티스토리나 카페 24 쇼핑몰과 같은 서비스에도 적용되는 방법입니다.  강의

opentutorials.org

 

깃허브 도메인 이름 변경 방법 설명

 

Managing a custom domain for your GitHub Pages site - GitHub Help

GitHub.com GitHub Pages Configuring a custom domain for your GitHub Pages site Managing a custom domain for your GitHub Pages site Managing a custom domain for your GitHub Pages site You can set up or update certain DNS records and your repository settings

help.github.com

깃허브 도메인 이름 변경에 문제가 생겼을 경우

 

Troubleshooting custom domains and GitHub Pages - GitHub Help

GitHub.com GitHub Pages Configuring a custom domain for your GitHub Pages site Troubleshooting custom domains and GitHub Pages Troubleshooting custom domains and GitHub Pages You can check for common errors to resolve issues with custom domains or HTTPS fo

help.github.com

단점

기본적으로 깃허브의 웹호스팅은 정적(static) 사이트만을 지원한다. 즉, php나 python 같은 언어로 웹사이트를 구현한 경우 '405 Not Allowed'와 같은 에러를 마주하게 된다.

이러한 문제를 해결하기 위해 깃허브는 지킬(Jekyll)을 built-in support를 추천한다. 이는 Ruby로 된 웹사이트에 특히 적합하다.

 

About GitHub Pages and Jekyll - GitHub Help

GitHub.com GitHub Pages Setting up a GitHub Pages site with Jekyll About GitHub Pages and Jekyll About GitHub Pages and Jekyll Jekyll is a static site generator with built-in support for GitHub Pages. GitHub Pages is available in public repositories with G

help.github.com

파이썬의 경우에는 펠리칸(Pelican)이 적합한 편이라고 한다. 다음 사이트에서 펠리칸의 설치과 사용 방법에 대해 자세히 알 수 있다.

 

Run your blog on GitHub Pages with Python

Create a blog with Pelican, a Python-based blogging platform that works well with GitHub.

opensource.com

 

참고

생활코딩, 웹호스팅(github pages), https://opentutorials.org/course/3084/18891

저작자표시 비영리 변경금지

'Programming > Side Project' 카테고리의 다른 글

[PHP] 단순 기록  (0) 2020.12.09
[개발] 전자세금계산서 엑셀 양식 작성 프로그램: 웹사이트 배포  (0) 2020.01.21
[개발] 전자세금계산서 엑셀 양식 작성 프로그램: Python  (0) 2019.12.02
[사이드프로젝트] 사이드 프로젝트 진행하기  (0) 2019.08.28
전자세금계산서 엑셀 양식 작성 프로그램

ERP 시스템(전사적 자원 관리 시스템)을 통해 다운로드한 엑셀 파일을 가지고 전자세금계산서 발급을 위한 엑셀 양식 파일을 채우는 프로그램을 만들기로 했다. 기존에 사람이 직접 전자세금계산서 발급을 위해서 엑셀 양식을 채우는 과정에서 빈번한 실수가 발생하여 이를 방지하기 위해 프로그램을 개발할 필요성이 있었다.

따라서, 기존에 회사에서 발급 양식을 채우던 방식 그대로 꼭 필수 항목이 아니더라도 양식을 채우기로 했다.

 

고려사항
  • 내가 받은 ERP 시스템에서 다운로드한 엑셀 파일에는 이메일 주소가 나와있지 않음
  • 최대 1000건의 엑셀 데이터를 다루어야함
  • 프로그래밍을 할 줄 모르는 사용자 고려 (프로그램을 실행하는 과정을 최대한 단순하게)
  • openpyxl 라이브러리는 xls 확장자를 지원하지 않음
  • 전자세금계산서 발급 양식은 어떤 경우에도 변경하지 않음
해결방안
  • 별도의 이메일 주소가 담긴 엑셀 파일을 준비
  • 파이썬의 openpyxl 라이브러리 사용
  • 쉽게 프로그램을 사용할 수 있도록 별도의 웹서버 운영 (진행 중)
  • ERP 시스템으로 xlsx 파일을 받을 수 있는지 확인, xlsx 파일로 전자세금계산서 발행이 가능한지 확인 (진행 중)
  • 전자세금계산서 발급 양식은 불변하므로 별도의 머릿글 행(열 이름)을 처리하지 않음
사용 언어
  • Python
데이터

프로그램 테스트를 위해 사용한 데이터는 다음과 같다.

erp.xlsx
email.xlsx
origin.xlsx
origin.xlsx
0.08MB
email.xlsx
0.01MB
erp.xlsx
0.03MB

 

코드
#!/usr/bin/env python
# coding: utf-8
import openpyxl
import os
import datetime

erpWB = openpyxl.load_workbook('data/erp.xlsx')
emailWB =  openpyxl.load_workbook('data/email.xlsx')
taxWB = openpyxl.load_workbook('data/origin.xlsx')

erpWS = erpWB[erpWB.sheetnames[0]]
emailWS = emailWB.active
taxWS = taxWB[taxWB.sheetnames[0]]

# 이메일 사업자 번호를 키로 해쉬테이블
emailAddress = dict()
for i in range(2,emailWS.max_row+1):
    emailAddress[emailWS[i][0].value] = emailWS[i][1].value
    print(emailWS[i][0].value,emailAddress[emailWS[i][0].value])

# erp 수금 기록 열 이름
# 사업자번호, 법인명, 대표자, 업태, 종목, 사업장주소, 공급가액, 세액 사용
erpDic = {'사업자번호':0,'법인명':1,'대표자':2,'업태':3,'종목':4,'사업장 주소':5,'공급가액':6,'세액':7}
erpHash = dict() #열 이름을 키값으로 갖는 셀 위치
erpName = []
for c in range (0,erpWS.max_column):
    erpHash[erpWS[2][c].value] = erpWS[2][c].coordinate.strip('0123456789')
    print(erpWS[2][c].value,erpHash[erpWS[2][c].value])

erpVal = []
for i in range (3,erpWS.max_row+1):
    temp = []
    if erpWS[erpHash['사업자번호']+str(i)].value!=None and erpWS[erpHash['수금액']+str(i)].value!=None: #사업자명이나 수금액이 없다면 저장하지 않음
        for j in erpDic:
            if j=='대표자': #대표자 이름 전처리
                temp.append(erpWS[erpHash[j]+str(i)].value.strip(' '))
            else:
                temp.append(erpWS[erpHash[j]+str(i)].value)
        if temp[0] in emailAddress.keys(): #저장된 이메일 주소가 없을 경우 None
            temp.append(emailAddress[temp[0]])
        else:
            temp.append(None)
        erpVal.append(temp)
        print(temp)

# 전자세금계산서 저장을 위한 이차원 배열
rowVal = []
dt = datetime.datetime.now();
for i in range (len(erpVal)):
    temp = []
    for j in range (taxWS.max_column):
        if j==0:
            temp.append('01')
        elif j==1:
            temp.append(dt.strftime("%Y%m%d"))
        elif j==2:
            temp.append(erpVal[i][erpDic['사업자번호']])
        elif j==4:
            temp.append(erpVal[i][erpDic['법인명']])
        elif j==5:
            temp.append(erpVal[i][erpDic['대표자']])
        elif j==6:
            temp.append(erpVal[i][erpDic['사업장 주소']])
        elif j==7:
            temp.append(erpVal[i][erpDic['업태']])
        elif j==8:
            temp.append(erpVal[i][erpDic['종목']])
        elif j==9:
            temp.append(erpVal[i][8]) #이메일
        elif j==11:
            temp.append(erpVal[i][erpDic['공급가액']])
        elif j==12:
            temp.append(erpVal[i][erpDic['세액']])
        elif j==14:
            temp.append(dt.strftime("%d"))
        elif j==15:
            temp.append(dt.strftime("%m")+'월 CCTV용역료')
        elif j==19:
            temp.append(erpVal[i][erpDic['공급가액']])
        elif j==20:
            temp.append(erpVal[i][erpDic['세액']])
        elif j==50:
            temp.append('01') #영수01 청구02
        else:
            temp.append('')
    rowVal.append(temp)
    print(temp)

for i in range (len(rowVal)):
    for j in range (taxWS.max_column):
        taxWS.cell(i+7,j+1,rowVal[i][j])
        print(rowVal[i][j])

taxWB.save('data/test.xlsx')

erpWB.close()
emailWB.close()
taxWB.close()

 

주피터 노트북으로 실행
taxInvoice-Copy1
In [1]:
from IPython.core.display import display, HTML
display(HTML("<style>.container {width:90% !important;}</style>"))
In [2]:
import openpyxl
import os
import datetime
In [3]:
erpWB = openpyxl.load_workbook('data/erp.xlsx')
emailWB =  openpyxl.load_workbook('data/email.xlsx')
taxWB = openpyxl.load_workbook('data/origin.xlsx')
In [4]:
erpWS = erpWB[erpWB.sheetnames[0]]
emailWS = emailWB.active
taxWS = taxWB[taxWB.sheetnames[0]]
In [5]:
emailWS[8][0].value
In [6]:
# 이메일 사업자 번호를 키로 해쉬테이블
emailAddress = dict()
for i in range(2,emailWS.max_row+1):
    emailAddress[emailWS[i][0].value] = emailWS[i][1].value
    print(emailWS[i][0].value,emailAddress[emailWS[i][0].value])

1111111111 java@java.com
2222222222 ccc@ccc.com
3333333333 data@base.com
4444444444 python@python.com
5555555555 ruby@ruby.com
6666666666 perl@cperl.com
None None
In [7]:
# erp 수금 기록 열 이름
# 사업자번호, 법인명, 대표자, 업태, 종목, 사업장주소, 공급가액, 세액 사용
erpDic = {'사업자번호':0,'법인명':1,'대표자':2,'업태':3,'종목':4,'사업장 주소':5,'공급가액':6,'세액':7}
erpHash = dict() #열 이름을 키값으로 갖는 셀 위치
erpName = []
for c in range (0,erpWS.max_column):
    erpHash[erpWS[2][c].value] = erpWS[2][c].coordinate.strip('0123456789')
    print(erpWS[2][c].value,erpHash[erpWS[2][c].value])

상호 A
미수 B
수금액 C
미수금 D
수금일자 E
입금수방 F
미수금사유 G
메모 H
사업자번호 I
법인명 J
대표자 K
주민번호 L
업태 M
종목 N
사업장 주소 O
실발행일자 P
입력자사번 Q
우편물(우) R
우편물 주소 S
(전)발급코드 T
(전)발급일자 U
(전)신고일자 V
(전)사유 W
관리담당 X
지역명 Y
선후납 Z
비고 AA
가입자번호 AB
지출증빙 AC
핸드폰(기초정보) AD
공급가액 AE
세액 AF
In [8]:
erpVal = []
for i in range (3,erpWS.max_row+1):
    temp = []
    if erpWS[erpHash['사업자번호']+str(i)].value!=None and erpWS[erpHash['수금액']+str(i)].value!=None: #사업자명이나 수금액이 없다면 저장하지 않음
        for j in erpDic:
            if j=='대표자': #대표자 이름 전처리
                temp.append(erpWS[erpHash[j]+str(i)].value.strip(' '))
            else:
                temp.append(erpWS[erpHash[j]+str(i)].value)
        if temp[0] in emailAddress.keys(): #저장된 이메일 주소가 없을 경우 None
            temp.append(emailAddress[temp[0]])
        else:
            temp.append(None)
        erpVal.append(temp)
        print(temp)

[1111111111, '자바', '제임스', '음식점업', '카페', '서울특별시 서초구 자바빌딩', 29000, 2900, 'java@java.com']
[2222222222, '씨', '벨연구소', '도.소매', '컴퓨터판매', '인천광역시 남구 씨대로 99', 35000, 3500, 'ccc@ccc.com']
[3333333333, '데이터', '디비', '도.소매', '공장', '서울특별시 강남구 데이터대로 베이스빌딩', 30000, 3000, 'data@base.com']
[4444444444, '파이썬', '귀도', '도.소매', '꽃집', '서울특별시 강남구 파이썬로 29', 60000, 6000, 'python@python.com']
[5555555555, '루비', '마츠모토', '도.소매', '보석상', '경기도 시흥시 루비상가', 20000, 2000, 'ruby@ruby.com']
[6666666666, '펄', '래리', '음식점업', '횟집', '서울특별시 종로구 펄길', 35000, 3500, 'perl@cperl.com']
In [9]:
# 전자세금계산서 저장을 위한 이차원 배열
rowVal = []
dt = datetime.datetime.now();
for i in range (len(erpVal)):
    temp = []
    for j in range (taxWS.max_column):
        if j==0:
            temp.append('01')
        elif j==1:
            temp.append(dt.strftime("%Y%m%d"))
        elif j==2:
            temp.append(erpVal[i][erpDic['사업자번호']])
        elif j==4:
            temp.append(erpVal[i][erpDic['법인명']])
        elif j==5:
            temp.append(erpVal[i][erpDic['대표자']])
        elif j==6:
            temp.append(erpVal[i][erpDic['사업장 주소']])
        elif j==7:
            temp.append(erpVal[i][erpDic['업태']])
        elif j==8:
            temp.append(erpVal[i][erpDic['종목']])
        elif j==9:
            temp.append(erpVal[i][8]) #이메일
        elif j==11:
            temp.append(erpVal[i][erpDic['공급가액']])
        elif j==12:
            temp.append(erpVal[i][erpDic['세액']])
        elif j==14:
            temp.append(dt.strftime("%d"))
        elif j==15:
            temp.append(dt.strftime("%m")+'월 CCTV용역료')
        elif j==19:
            temp.append(erpVal[i][erpDic['공급가액']])
        elif j==20:
            temp.append(erpVal[i][erpDic['세액']])
        elif j==50:
            temp.append('01') #영수01 청구02
        else:
            temp.append('')
    rowVal.append(temp)
    print(temp)

['01', '20191204', 1111111111, '', '자바', '제임스', '서울특별시 서초구 자바빌딩', '음식점업', '카페', 'java@java.com', '', 29000, 2900, '', '04', '12월 CCTV용역료', '', '', '', 29000, 2900, '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '01']
['01', '20191204', 2222222222, '', '씨', '벨연구소', '인천광역시 남구 씨대로 99', '도.소매', '컴퓨터판매', 'ccc@ccc.com', '', 35000, 3500, '', '04', '12월 CCTV용역료', '', '', '', 35000, 3500, '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '01']
['01', '20191204', 3333333333, '', '데이터', '디비', '서울특별시 강남구 데이터대로 베이스빌딩', '도.소매', '공장', 'data@base.com', '', 30000, 3000, '', '04', '12월 CCTV용역료', '', '', '', 30000, 3000, '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '01']
['01', '20191204', 4444444444, '', '파이썬', '귀도', '서울특별시 강남구 파이썬로 29', '도.소매', '꽃집', 'python@python.com', '', 60000, 6000, '', '04', '12월 CCTV용역료', '', '', '', 60000, 6000, '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '01']
['01', '20191204', 5555555555, '', '루비', '마츠모토', '경기도 시흥시 루비상가', '도.소매', '보석상', 'ruby@ruby.com', '', 20000, 2000, '', '04', '12월 CCTV용역료', '', '', '', 20000, 2000, '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '01']
['01', '20191204', 6666666666, '', '펄', '래리', '서울특별시 종로구 펄길', '음식점업', '횟집', 'perl@cperl.com', '', 35000, 3500, '', '04', '12월 CCTV용역료', '', '', '', 35000, 3500, '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '01']
In [10]:
for i in range (len(rowVal)):
    for j in range (taxWS.max_column):
        taxWS.cell(i+7,j+1,rowVal[i][j])
        print(rowVal[i][j])

01
20191204
1111111111

자바
제임스
서울특별시 서초구 자바빌딩
음식점업
카페
java@java.com

29000
2900

04
12월 CCTV용역료



29000
2900





























01
01
20191204
2222222222

씨
벨연구소
인천광역시 남구 씨대로 99
도.소매
컴퓨터판매
ccc@ccc.com

35000
3500

04
12월 CCTV용역료



35000
3500





























01
01
20191204
3333333333

데이터
디비
서울특별시 강남구 데이터대로 베이스빌딩
도.소매
공장
data@base.com

30000
3000

04
12월 CCTV용역료



30000
3000





























01
01
20191204
4444444444

파이썬
귀도
서울특별시 강남구 파이썬로 29
도.소매
꽃집
python@python.com

60000
6000

04
12월 CCTV용역료



60000
6000





























01
01
20191204
5555555555

루비
마츠모토
경기도 시흥시 루비상가
도.소매
보석상
ruby@ruby.com

20000
2000

04
12월 CCTV용역료



20000
2000





























01
01
20191204
6666666666

펄
래리
서울특별시 종로구 펄길
음식점업
횟집
perl@cperl.com

35000
3500

04
12월 CCTV용역료



35000
3500





























01
In [11]:
taxWB.save('data/test.xlsx')
In [12]:
erpWB.close()
emailWB.close()
taxWB.close()

 

결과

프로그램 실행 결과는 다음과 같다.

test.xlsx
test.xlsx
0.08MB

개선사항
  • 최대한 확장성을 고려해 다른 회사에서도 사용할 수 있게 만들고 싶었으나, 머릿글 행(열 이름)의 처리 문제
  • 전자세금계산서 발급을 위해서는 최대 1000건의 데이터만 입력해야 하는데 이를 위한 처리를 따로 해주어야 함
  • 결과 파일의 배경 색상이 바뀌는 것의 원인을 확인하고 해결 해야함
저작자표시 비영리 변경금지

'Programming > Side Project' 카테고리의 다른 글

[PHP] 단순 기록  (0) 2020.12.09
[개발] 전자세금계산서 엑셀 양식 작성 프로그램: 웹사이트 배포  (0) 2020.01.21
[개발] Github를 이용한 무료 웹서버 호스팅: Github Pages  (0) 2019.12.03
[사이드프로젝트] 사이드 프로젝트 진행하기  (0) 2019.08.28
경사 하강법(Gradient Descent)의 원리

선형 회귀 모델과 모델의 예측 평가 방법까지 알았으니 이제 어떻게 가장 최적의 모델을 찾을 것인지 알아보자. 이전 포스트에서 언급했듯이, 가장 최적의 모델은 가장 적은 비용(cost)을 갖는 모델이다. 모델이 최소 비용을 갖는 매개변수를 찾는 과정을 훈련한다고 하며 비용 최소화하기 위해서는 경사 하강법(Gradient Descent)을 이용한다. 이 방법의 원리는 산 정상에서 골짜기로 가장 빠르게 내려오는 방법인 가장 경사가 가파른 길을 골라 내려오는 것과 같다. 이 방법은 회귀뿐만 아니라 다양한 종류의 문제에서 최적의 해법을 찾을 수 있는 일반적인 최적화 알고리즘이다.

 

Gradient descent.png
경사 하강법을 실행하는 모습. x0에서 시작하여, 경사가 낮아지는 쪽으로 이동하여 차례대로 x1, x2, x3, x4를 얻는다.

 

이 그림에서 볼 수 있듯이, 등고선에서 고지를 찾는 방법은 임의의 시작점 x0에서 경사(기울기)가 낮아지는 쪽(등고선이 서로 가까울수록 경사가 가파르며 고지에 가까울수록 경사는 낮아진다)을 찾아 차례대로 이동하여 가장 경사가 낮은 곳(최적해)을 찾으면 된다. 이때 최종적으로 고지에 도달하면 경사가 0에 도달한다.

 

Gradient ascent (surface).png

그러나 위와 같은 형태의 곡면의 경우 임의의 시작점 ⍬0에서 출발하여 경사가 0에 도달해 찾은 고지가 다른 임의의 시작점 ⍬1에서 출발하여 찾은 고지와 다를 수 있다. 즉, 임의의 시작점 ⍬에서 찾은 지역적인 최적해(local minimum)가 전역적인 최적해(global minimum)라고 보장할 수 없다. 

 

다행히 비용 함수는 다음과 같은 모양의 이차 곡면을 가진다. 즉 하나의 전역 최솟값을 가지고 있다는 뜻이다.

Circular Paraboloid Quadric.png

학습률(Learning Rate)

경사 하강법에서 가장 중요한 파라미터는 스텝의 크기로 학습률 하이퍼파라미터로 결정된다. 여기서 하이퍼파라미터는 일반적인 파라미터와는 달리 데이터를 학습해서 얻을 수 없으며, 모델의 성능 향상을 위해 별도의 최적화 과정을 거쳐 찾아내야 하는 조정 파라미터(tuning parameter)를 말한다.

 

등고선에서 x0에서 x로 나아가기 위해서는 얼마나 멀리까지 이동을 할 것인가를 결정하는 것이 학습률 하이퍼파라미터를 결정하는 것이다.

Conjugate gradient illustration.svg

 

학습률이 너무 작으면 알고리즘이 수렴하기 위해 반복을 너무 많이 진행해야 하므로 시간이 오래 걸리며 전역 최솟값에 수렴하기 전에 지역 최솟값에서 모델이 학습을 중단할 수도 있다. 반면에 학습률이 너무 크면 골짜기를 가로질러 골짜기 아래로 내려가는 것이 아니라 반대로 올라갈 수도 있으며 알고리즘이 더 큰 값으로 발산하게 되어 적절한 해법을 찾을 수 없게 된다. 이를 overshooting이라고 한다. 따라서 적절한 해법을 찾기 위해서는 여러 가지 학습률을 적용해보고 비교하는 과정이 필요할 수도 있다.

학습률이 너무 작은 경우(왼)와 학습률이 너무 큰 경우(오)

경사 하강법에서의 계산 : 배치 경사 하강법(Batch Gradient Descent)

시작점 X0 출발하여 현제 Xi에 위치해 있을 때, 다음으로 이동할 점인 Xi+1은 다음과 같이 계산한다.

여기서 α는 이동할 거리를 조절하는 매개변수이다.

경사 하강법을 비용 함수에서 구현하려면 각 모델 파라미터 W에 대해 비용 함수의 경사(gradient)를 계산해야 한다. 이는 W가 조금 변경될 때 비용 함수가 얼마나 바뀌는지 계산한다는 의미이다. 이를 편미분(Partial Derivative)라고 한다. 이를 이용하여 비용 함수에서의 편미분을 구하는 방법은 다음과 같이 유도할 수 있다.

 

우선 간단한 계산을 위해 선형 회귀식 H(x)의 파라미터를 W만 남긴다.

이때 비용 함수는 다음과 같이 표현될 수 있다. 마찬가지로 간단한 미분을 위해 1/2을 한다. 1/m과 1/2m은 이 식에 큰 영향을 끼치지 않는다.

이렇게 정리한 비용 함수 cost(W)를 W에 대해서 편미분 하면 다음과 같은 식을 얻을 수 있다.

위의 경사 하강법 계산식의 ƒ(x)에 비용 함수를 대입하면 경사 하강법의 스텝 W에 대해 다음과 같은 정의를 할 수 있다. 여기서 α는 학습률이며 내려가는 스텝 W의 크기를 결정한다.

이러한 알고리즘을 배치 경사 하강법(Batch Gradient Descent)라고 한다. 이 알고리즘에서 매 스텝에서 훈련 데이터 전체를 사용하기 때문에 큰 훈련 데이터 세트에서 매우 느리다. 때문에 확률적 경사 하강법(Stochastic Gradient Descent)을 사용하기도 한다.

 

확률적 경사 하강법(Stochastic Gradient Descent)

매우 큰 훈련 데이터 세트에서의 배치 경사 하강법의 단점을 보완하기 위한 방법으로 확률적 경사 하강법이 있다. 이 방법은 매 스텝을 결정할 때마다 전체 훈련 데이터 세트를 이용하는 배치 경사 하강법과 달리 매 스텝에서 단 한 개의 데이터만 무작위로 선택하고 그에 대한 경사(Gradient)를 계산한다

 

다만 확률적(무작위)이기 때문에 배치 경사 하강법보다 불안정하다는 특성이 있다. 이 특성은 알고리즘이 지역 최솟값을 무시할 수 있도록 도와주지만 시간이 지나도 최솟값에 매우 근접할 뿐 최솟값을 찾기는 어렵다. 즉 배치 경사 하강법보다 전역 최솟값을 찾을 가능성이 높지만 전역 최솟값에 이르기 어렵다는 뜻이다.

 

 

이를 해결하기 위한 방법 중 하나는 학습률을 점진적으로 감소시키는 것이다. 이렇게 하면 알고리즘이 전역 최솟값에 도달하게 한다. 이렇게 매 스텝에서 학습률을 결정하는 함수를 학습 스케줄(learning schedule)이라고 한다.

 

 

미니 배치 경사 하강법(Mini-Batch Gradient Descent)

미니 배치 경사 하강법은 확률적 경사 하강법과 유사하다. 다만, 하나의 샘플이 아닌 미니 배치라 부르는 임의의 작은 샘플 세트에 대해서 경사를 계산한다는 점이 다르다. 

 

미니 배치 경사 하강법의 경우 확률적 경사 하강법에 비해 전역 최솟값에 더 빨리 가까이 도달하게 된다. 미니 배치 경사 하강법 역시 확률적 경사 하강법과 마찬가지로 전역 최솟값에서 멈추지 않고 그 주변을 반복적으로 맴돌 가능성이 있다. 이때 적절한 학습 스케줄을 통해 최솟값에 도달할 수 있다.

Stogra.png
미니 배치 경사 하강법에서 스텝의 변동

 

참고

오렐리앙 게론, "핸즈온 머신러닝", 한빛미디어, 2017년 3월

필드 케이디, "처음 배우는 데이터 과학", 한빛미디어, 2018년 2월

니킬 부두마, "딥러닝의 정석", 한빛미디어, 2018년 3월

Probst, Philipp, Anne-Laure Boulesteix, and Bernd Bischl. "Tunability: Importance of Hyperparameters of Machine Learning Algorithms." Journal of Machine Learning Research 20.53 (2019): 1-32.

Edwith, 머신러닝과 딥러닝 BASIC 중 'Linear Regression의 cost 최소화 알고리즘의 원리', https://youtu.be/TxIVr-nk1so

위키백과, 경사하강법, https://ko.wikipedia.org/wiki/%EA%B2%BD%EC%82%AC_%ED%95%98%EA%B0%95%EB%B2%95

위키백과, 이차 초곡면, https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%B0%A8_%EC%B4%88%EA%B3%A1%EB%A9%B4

Wikipedia, Gradient Descent, https://en.wikipedia.org/wiki/Gradient_descent

Wikipedia, Stochastic Gradient Descent, https://en.wikipedia.org/wiki/Stochastic_gradient_descent

저작자표시 비영리 변경금지

'Programming > Machine Learning' 카테고리의 다른 글

[개념] Linear Regression & Cost Function: 선형 회귀와 비용 함수  (0) 2019.10.14
[개념] Machine Learning: 머신러닝이란  (0) 2019.09.26
Linear Regression이란

Linear Regression(선형 회귀)는 이전 머신러닝 개념 포스트에서 간단히 다루었던 지도 학습(supervised learning)의 한 종류이다. 선형 회귀는 학습 데이터(training data set)를 이용한 학습(training) 과정을 거쳐 데이터에 가장 잘 맞는 선형 모델의 매개변수(parameter)를 찾아 예측하는데 여기서 예측의 범위는 연속적인 범위를 갖는다. 다시 말해, 종속변수 y와 한 개 이상의 독립변수 x와의 선형 상관관계를 모델링하는 회귀분석 기법이다. 한 개의 독립 변수(또는 설명 변수)에 기반한 경우에는 단순 선형 회귀, 둘 이상의 독립 변수에 기반한 경우에는 다중 선형 회귀라고 한다. 실제로 많은 데이터들이 아래의 그래프와 같이 선형(linear)으로 분포하는 경향이 있기 때문에 선형 회귀를 통해 예측이 가능하다. 

Normdist regression.png
독립변수 1개와 종속변수 1개를 가진 선형 회귀의 예

 

선형 회귀는 선형 예측 함수를 통해 회귀식을 모델링하며, 알려지지 않은 매개변수는 주어진 데이터로부터 추정한다. 이렇게 만들어진 회귀식을 선형 모델이라고 한다. 

 

선형 회귀의 대표적인 사용 사례는 다음과 같다.

  • 값을 예측하는 것이 목적일 경우: 선형 모델을 통해 독립변수 x에 따른 종속변수 y를 예측하기 위해 사용할 수 있다.
  • 종속변수 y와 독립변수 x 사이의 관계를 밝히는 경우: 선형 회귀 분석을 사용해 x와 y 사이의 관계를 정량화하기 위해 사용할 수 있다. 

왜 Regression이라 하는가?

Regression을 영어 사전에서 찾아보면, 후퇴, 복귀, 쇠퇴, 회귀라고 나온다. 그중에서도 통계학 용어인 회귀는 국어사전에서 '한 바퀴 돌아서 본디의 상태나 자리로 돌아오는 것'이라고 한다. 이러한 용어는 영국의 유전학자 프란시스 골턴(Francis Galton)이 부모의 키와 아이들의 키의 상관관계를 연구하면서 키가 큰 사람의 아이가 부모보다 작은 경향이 있다는 사실을 연구하면서 소개하였다. 다시 말해, 키가 큰 부모보다 작은 아이의 키가 전체 키 평균으로 회귀한다는 것이다. 프란시스는 두 변수 사이의 상관관계를 분석하기 위해 사용한 방법을 회귀라고 이름 붙였으며 이후 칼 피어슨(Karl Pearson)은 아버지와 아들의 키를 조사한 결과를 바탕으로 함수 관계를 도출하여 회귀 분석 이론을 수학적으로 정립하였다.

 

선형 회귀식

선형 회귀는 주어진 데이터 집합에서 종속변수 y와 연관된 독립변수 x가 d개 존개하는 경우에 회귀식은 다음과 같이 나타낼 수 있다.

d개의 독립변수에 따른 선형회귀식

d개의 독립변수에 따른 선형회귀식은 다음과 같은 형태로 나타낼 수 있다.

여기서 y는 종속 변수 혹은 응답 변수라고 하며 출력값이라고 볼 수 있다. x는 독립 변수, 예측 변수, 입력 변수라고 하며 입력값이라고 볼 수

있다. ⍵는 매개변수, 회귀 계수라고 불리기도 하는 상수이다. b는 오차항, 노이즈로 이는 종속변수 y에 대한 모든 오차 요인을 포함한다.

 

가장 간단한 선형 회귀식은 독립변수 x가 1개인 1차 방정식 형태이다. 쉬운 설명을 위해 다음과 같은 형태의 회귀식을 사용하도록 하자.

여기서 H(x)는 입력값 x에 따른 출력 값 y를 예측하는 가설(Hypothesis)이며, ⍵와 b는 모델 파라미터를 의미한다. 이 ⍵, b파라미터를 조정하여 선형 함수를 표현하는 모델을 얻을 수 있다. 이 모델을 사용하기 위해서는 ⍵와 b를 정의해야 하며 이를 훈련 데이터에 가장 잘 맞는 값을 찾는 과정을 훈련시킨다(training)라고 한다. 그렇다면 어떻게 ⍵와 b를 정의해야 할까? ⍵와 b의 정의에 따라 1차 함수의 기울기와 절편이 달라지기 때문에 데이터의 산포도와 가장 적합한 함수가 될 수 있도록 ⍵와 b를 정의해야 한다.

 

선형 회귀에서는 일반적으로 선형 모델의 예측과 훈련 데이터 사이의 거리를 재는 비용 함수(Cost Function)를 사용한다.

 

비용 함수(Cost Function)

선형 회귀에서는 일반적으로 선형 모델의 예측과 훈련 데이터 사이의 거리를 재는 비용 함수(Cost Function)를 사용한다. 간단히 말해 각 점과 선 사이의 거리를 계산하며 가설(선형 모델의 예측)과 실제 데이터(훈련 데이터)가 얼마나 다른지를 평가하는 것이다. 이때, 단순히 하나의 데이터(single data)와 모델의 예측의 차이를 계산하는 것을 손실 함수(Loss Function)라고 하며 모든 데이터에 대한 차이를 모두 합하여 모델을 평가하는 것이 비용 함수이다. 

 

 

선형 회귀식에서 ⍵와 b의 값에 따라 다양한 선형 회귀 모델을 만들 수 있다. 왼쪽의 그래프에서 볼 수 있듯이 세 가지의 선형 회귀 모델을 만들었다고 하자. 이 세 가지 모델 중에 가장 예측을 정확하게 하는 모델이 무엇인지 평가하기 위해서 비용 함수를 사용한다.

거리를 구하기 위해 위와 같은 식을 생각할 수 있으나 이 함수는 좋은 함수가 아니다. 단순하게 -y를 하기 때문에 y의 위치가 모델의 왼쪽과 오른쪽에 있을 때에 따라 같은 거리임에도 다르게 평가될 수 있기 때문이다. 따라서 비용 함수는 위의 함수를 제곱하여 사용한다. 다음 식에 m은 데이터의 개수를 의미하며 각 데이터에 대한 예측 결과를 실제 데이터와 비교하여 총 데이터에 대한 예측을 평가한다. 이 비용 함수의 결괏값이 적을수록 예측이 정확하다는 것을 의미한다. 가장 적은 비용을 갖는 ⍵와 b를 구하는 과정이 모델의 훈련 과정이다.

 

비용 함수를 이용한 예측 모델을 훈련시키는 방법은 다음 포스트에 이어진다.

 

참고

오렐리앙 게론, "핸즈온 머신러닝", 한빛미디어, 2017년 3월

필드 케이디, "처음 배우는 데이터 과학", 한빛미디어, 2018년 2월

Edwith, 머신러닝과 딥러닝 BASIC 중 'Linear Regression의 Hypothesis와 cost', https://youtu.be/Hax03rCn3UI

위키백과, 회귀분석, https://ko.wikipedia.org/wiki/%ED%9A%8C%EA%B7%80_%EB%B6%84%EC%84%9D

위키백과, 선형회귀, https://ko.wikipedia.org/wiki/%EC%84%A0%ED%98%95_%ED%9A%8C%EA%B7%80

Wikipedia, Linear Regression, https://en.wikipedia.org/wiki/Linear_regression

 

저작자표시 비영리 변경금지

'Programming > Machine Learning' 카테고리의 다른 글

[개념] Gradient Descent: 경사하강법  (1) 2019.10.15
[개념] Machine Learning: 머신러닝이란  (0) 2019.09.26
머신러닝이란

위키백과에서는 머신러닝을 "the scientific study of algorithms and statistical models that computer systems use to perform a specific task without using explicit instructions, relying on patterns and inference instead."라고 정의하고 있다. 즉, 컴퓨터 시스템이 패턴과 추론에 의지하는 대신에 명시적 지시를 사용하지 않고 특정 작업을 수행하는 데 사용하는 알고리즘 및 통계 모델에 대한 과학적 연구이다.

 

일반적으로 소프트웨어라고 생각하는 명시적인(explicit) 프로그램들은 한계를 가지고 있다. 스팸 메일 필터나 자율 주행 자동차를 떠올려보자. 계산기 프로그램을 만드는 것처럼 스팸 메일 필터를 만들면 어떻게 될까? 스팸 메일을 구분하기 위한 규칙들을 개발자가 직접 명시하기에는 너무나도 많은 경우의 수가 존재하며 이를 개발 단계에서 프로그래밍하기에는 명백한 한계를 가지고 있다. 그래서 나온 방법이 프로그램이 데이터로부터 스스로 학습하도록 프로그래밍하는 것이다. 스팸 메일의 경우 계속해서 진화하는 스팸 메일의 내용에 맞춰 프로그램이 스스로 학습하게 되면, 프로그램의 유지 보수가 용이해지며 정확도가 더 높아진다. 

 

머신러닝은 다음과 같은 경우에 적합하다.

  • 기존의 해결 방법으로는 많은 수동 조정과 규칙이 필요한 문제.
  • 전통적인 방법으로는 전혀 해결 방법이 없는 복잡한 문제.
  • 유동적인 환경에 적응해야 하는 문제.
  • 복잡한 문제와 대량의 데이터에서 통찰 얻기. (e.g. 데이터 마이닝)

 

"The field of study that gives computers the ability to learn without being explicitly programmed."
: "명시적인 프로그래밍 없이 컴퓨터가 학습하는 능력을 갖추게 하는 연구 분야다"
-아서 사무엘(Arthur Samuel), 1959

 

"A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by p, improves with experience E."
"어떤 작업 T에 대한 컴퓨터 프로그램의 성능을 P로 측정했을 때 경험 E로 인해 성능이 향상됐다면, 이 컴퓨터 프로그램은 작업 T와 성능 측정 P에 대해 경험 E로 학습한 것이다."
-톰 미첼(Tom Mithchell), 1997

 

학습 방법에 의한 구분

머신러닝의 학습 방법은 접근 방식, 입력 및 출력하는 데이터 유형 및 해결하려는 작업 또는 문제의 유형에 따라 다르다. 보다 다양한 학습 방법의 구분은 다음에서 확인할 수 있다.

 

그중에서 학습하는 동안의 감독의 형태에 따라 지도 학습과 비지도 학습으로 구분할 수 있는데 다음과 같다.

 

지도 학습(Supervised Learning)

지도 학습은 입력과 원하는 출력을 모두 포함하는 예제(labeld examples)를 학습 데이터셋(training data set)으로 활용하여 수학적 모델을 구축한다. 각각의 훈련 예제는 하나 이상의 입력과 각 입력에 대응해 기대하는 결과를 함께 포함하고 있다. 분류(classfication)가 전형적인 지도 학습 작업이며 에측 변수(predictor variable)라 부르는 특성(e.g. 공부시간, 과제점수 등)을 사용해 타깃(e.g. 최종 학점)의 수치를 예측하는 것 역시 지도 학습을 이용한 전형적인 작업에 속한다.

예를 들면, 여러 동물 사진을 가지고 각 사진이 어떤 동물인지를 구분하는 프로그램을 학습시키고자 할 때, 지도 학습 방법은 프로그램을 학습시킬 때, 각 사진이 어떤 동물의 사진인지를 구분(labeled)을 먼저 한 뒤에 프로그램을 학습시키는 방법이다.

 

비지도 학습(또는 자율학습, Unsupervised Learning)

지도 학습과 달리 비지도 학습은 훈련 데이터셋에 구분이 되어 있지 않다. 따라서, 프로그램이 스스로 도움 없이 학습을 해야한다. 이 학습 방법에서는 군집화(Clustering)가 중요하다. 프로그램은 데이터 간의 공통점을 식별하고 새로운 데이터의 이러한 공통점의 존재 여부에 따라 반응한다. 

예를 들면, 뉴스 기사를 구분 하고자 할 때, 비지도 학습 방법은 여러 뉴스 기사를 통해 다른 기사와 유사한 점과 유사하지 않은 점을 구분해 나가며 군집(Cluster)을 만들어 나가며 그룹을 짓는다. 즉, 감독의 개입 없이 데이터셋만 가지고 스스로 학습하는 것이다.

 

학습 데이터셋(Training Data Set)

머신러닝 알고리즘은 간단한 학습 데이터(training data)를 기반으로 명시적인 프로그래밍 없이 예측 또는 결정을 하기 위한 수학적인 모델을 만든다. 학습 데이터셋은 쉽게 말해 학습에 사용하기 위한 데이터들의 모음이다.

 

참고

오렐리앙 게론, "핸즈온 머신러닝", 한빛미디어, 2017년 3월

Edwith, 머신러닝과 딥러닝 BASIC 중 '기본적인 Machine Learning의 용어와 개념 설명', http://www.edwith.org/others26/lecture/10729/

MIT, Introduction to Machine Learning, https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/lecture-videos/lecture-11-introduction-to-machine-learning/

Wikipedia, Machine Learning, https://en.wikipedia.org/wiki/Machine_learning

 

 

저작자표시 비영리 변경금지

'Programming > Machine Learning' 카테고리의 다른 글

[개념] Gradient Descent: 경사하강법  (1) 2019.10.15
[개념] Linear Regression & Cost Function: 선형 회귀와 비용 함수  (0) 2019.10.14
Big-O Notation (빅오 표기법)이란

알고리즘의 복잡도를 나타내는 지표 혹은 언어로 계산 복잡도 이론에서 사용되는 점근 표기법이다. 또한, 란다우 표기법이라고 부르기도 하는데 복잡도 이론, 컴퓨터 과학, 수학에서 함수의 점근적 동작을 설명하기 위해 사용하며, 기본적으로 함수가 얼마나 빠르게 증가 혹은 감소하는지 알려준다. 따라서 Big-O 표기법은 알고리즘의 속도를 파악하는데 큰 도움이 된다.

 

개념의 비유(시간 복잡도)

만약 우리가 누군가에게 파일을 전달하고자 할 때를 생각해보자. 메일이나 FTP 등 온라인을 통해 상대방에게 파일을 전송할 수도 있고 직접 파일이 담긴 USB를 전달할 수도 있을  것이다. 온라인으로 파일은 전송하는 방법은 간단하고 손쉽다. 하지만 파일 크기가 1TB가 넘는다면? 이러한 경우에는 파일을 전달하는데 하루가 부족할지도 모른다. 파일 크기에 따라 걸리는 시간이 증가하는 것이다. 반면에, 직접 USB에 파일을 담아 전달할 경우, 파일 크기가 얼마나 크던 작던 상관없이 걸리는 시간은 변하지 않는다. 즉, 파일 전달까지 걸리는 시간이 파일 크기에 무관하게 일정한 시간이 걸리는 것이다. 이를 Big-O 표기법으로 나타내면, 온라인 전송의 경우, O(n) (여기서 n은 파일의 크기를 의미한다), 직접 전달의 경우 O(1)로 나타낼 수 있다. 이것이 바로 Big-O 시간에 대한 개념이다. 

파일 크기에 따른 소요시간의 변화

그 외의 개념 Big-O, Big-Θ, Big-Ω

Big-O : 학계에서 O는 상한을 나타낸다. 어떤 알고리즘은 O(n)으로 표현할 수 있지만, 이 외에 N보다 큰 big-O 시간으로 표현할 수도 있다. 예를 들어 O(n²), O(n³)도 옳은 표현이다. 다시 말해 알고리즘의 수행 시간은 적어도 이들 중 하나보다 빠르기만 하면 된다. 따라서 big-O 시간은 알고리즘 수행 시간의 상한이 되고, 이는 '작거나 같은' 부등호와도 비슷한 관계가 있다. 만약 철수의 나이가 X라면 X ≤ 100이라고 말할 수 있지만, X ≤ 1,000 혹은 X ≤ 1,000,000으로 나타내도 옳은 표기법이다. 수학적으로 이야기해서 이들 모두 참인 표현법이다. 마찬가지로 배열의 모든 값을 출력하는 알고리즘은 O(n)이라고 표현할 수 있을 뿐만 아니라 O(n³) 혹은 O(n) 보다 큰 어떤 수행 시간으로도 표현 가능하다.

 

Big-Ω : 학계에서 Ω는 등가 개념 혹은 하한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 Ω(n)뿐만 아니라 Ω(log(n)) 혹은 Ω(1)로도 표현할 수 있다. 결국, 해당 알고리즘은 Ω 수행 시간보다 빠를 수 없게 된다.

 

Big-Θ : 학계에서 Θ는 Ω와 O 둘 다를 의미한다. 즉, 어떤 알고리즘의 수행 시간이 O(n)이면서 Ω(n)이라면, 이 알고리즘의 수행 시간을 Θ(n)로 표현할 수 있다.

 

다양한 표기법과 그 의미

f(x) = o(g(x))는 f가 g보다 느리게 증가한다는 뜻이며 이는 비교에서 크게 중요하지 않다. Θ와 Ω는 컴퓨터 과학에서 종종 사용되며, 소문자 o는 수학에서는 흔하지만 컴퓨터 과학에서는 흔하지 않다. ω는 거의 사용하지 않는다. 

흔히 하는 실수는, Θ를 의미할 때 O를 사용하는 것이다. 예를 들어 힙 정렬은 Θ(n×log(n))라는 의미를 전달하고자 하는 의미로 O(n×log(n))이다.라고 말할 수 있다. 둘 다 맞는 말이지만 Θ(n×log(n))가 더 강한 주장이다. 업계에서 big-O의 의미는 학계에서 Θ의 의미와 가깝다. 이 글에서 아래에 설명하는 개념은 학계에서 Θ의 의미와 가까운 big-O 표기법을 사용하겠다.

 

공간 복잡도

위에서 살펴본 파일 크기에 따른 전송 시간은 시간에 대한 복잡도였다. 알고리즘에서는 시간뿐만 아니라 공간(메모리)에 대해서도 신경을 써야 한다. 예를 들어, 크기가 n인 배열을 만들고자 한다면, O(n)의 공간이 필요하다. 크기가 n×n인 이중 배열을 만들려면, O(n²)의 공간이 필요하다.

 

표기방법

big-O를 표기하는 방법은 다음과 같다. 

 

상수항은 무시한다. big-O는 단순히 증가하는 비율을 나타내는 개념이므로, n이 충분히 큰 숫자일 경우, O(n) 코드가 O(1) 코드보다 빠르게 동작하는 것이 가능하다. 이런 이유로 수행 시간에서 상수항을 무시해 버린다. 즉, O(2n)으로 표기되어야 할 알고리즘을 O(n)으로 표기한다. big-O 표기법은 수행 시간이 어떻게 변화하는지 표현해주는 것이므로 O(n)이 언제나 O(2n) 보다 나은 것은 아니다.

예를 들어, T(n) = 4 n²-2n+2의 경우, T(n)은 n²의 비율로 증가하며 이는 T(n) = O(n²)으로 표기할 수 있는 것이다. 

 

지배적이지 않은 항은 무시한다. O(n²+n)과 같은 수식이 있을 때는 어떻게 해야 할까? 우선 O(n²+n²)를 보자, 앞에서 상수항은 무시해도 된다고 언급했다. 따라서 O(n²+n²)은 O(2n²)이고 O(n²)이 된다. 이처럼 마지막 n²을 무시해도 된다면 그보다 작은 n항은 어떨까? 무시해도 된다. 즉, 수식에서 지배적이지 않은 항은 무시해도 된다.

O(n²+n)은 O(n²)이 된다.

O(n+log(n))은 O(n)이 된다.

예를 들어, f(n) = 10 log(n)+5(log(n))³+7n+3 n²+6 n³이라면, 이는 f(n) = O(n³)으로 표기할 수 있다.

하지만 언제나 수식에 합을 생략할 수 있는 것은 아니다. 예를 들어, O(B²+A)는 A와 B 사이에 존재하는 특별한 관계를 알고 있지 않은 이상 하나의 항으로 줄일 수 없다.

 

다음의 그래프는 흔히 사용되는 big-O 시간의 증가율을 나타낸다.

Comparison computational complexity.svg
입력 크기 n에 따른 함수의 연산 수 N에 대한 함수 그래프

 

알고리즘의 표기 방법

그렇다면 알고리즘에서 어떤 경우에 항을 덧셈으로 표기하고, 어떤 경우에 곱셈으로 표기하는지 알아보자.

for(int a : arrA)
{
	print(a);
}

for(int b : arrB)
{
	print(b);
}
//A의 일이 완전히 수행되고 난 뒤에 B의 일을 수행한다.

위의 알고리즘의 경우, 두 개의 for문이 각각 별개로 작업을 수행한다. 이러한 경우, 두 for문의 수행 시간을 더해야 한다. 즉, O(A+B)가 된다.

for(int a : arrA)
{
	for(int b : arrB)
    	{
    		print(a + "," +b);
	}
}
//A의 각 원소에 대해 B의 일을 수행한다.

위의 알고리즘의 경우, 두 번째 for문이 첫 번째 for문에 안에 위치해 있어, 첫 번째 for문이 한 번 수행될 때마다 두 번째 for문이 전체 수행된다. 이러한 경우, 두 for문의 수행 시간을 곱해야 한다. 즉, O(A×B)가 된다.

참고
저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바