음 아마 비둘기보단 똑똑할꺼야
준돌 Jundol / 2019.10.30 15:53 / 카테고리 없음

이미지출처. 에이콘출판사

 

RESTful 파이썬 웹 서비스 제작 책을 읽고있다.

예제를 따라하며 생긴 문제점과 현기준 최신버전의 pip 패키지를 사용했을 때 나타나는 에러들을 정리해봤다.

본 포스트는 1~4장까지인 Django rest framework를 학습하면서 명령어를 포함해 정리해보았다.

 


# 웹서버 실행
python manage.py runserver

윈도우 파워쉘 사용
cd pythonREST
python -m venv Django02
PythonREST\Django01\Scrlpts\Activate.ps1

가상환경 Activate 시 명령창 맨앞에 (Django01) 활성화됨

# django 설치
pip install django
pip install djangorestframework

# httpie 설치
pip install httpie

cd Django01

django-admin.py startproject gamesapi
cd gamesapi
python manage.py startapp games

# psycopg2 (postgresql 사용에 필요한 도구)
pip install psycopg2

# git 소스파일 복사 후 
python manage.py makemigrations games

# 필드 필터링 기능 사용을 위해
pip install django-filter

# 브라우저 API가 다른 필터를 렌더링하는 방법을 향상시키는 패키지
pip install django-crispy-forms

# 단위 테스트 설정
pip install coverage
pip install django-nose

# 종속성 리스트 생성
pip freeze > requirements.txt

 


get 메서드 실행시 RetrieveUpdateDestroyAPIView 슈퍼클래스에 정의돼 있으며, mixins.RetrieveModelMixin 정의된 retrieve 메서드를 호출한다.

 

models.py 에서 unique=True 설정시 중복값 저장이 불가능하다.

 

PATCH메서드 통해 단일필드 업데이트가 가능하다.

 

pagination

rest_framework.pagination.LimitOffsetPagination 클래스 사용한다.

pagination 기본 클래스 설정에 최대제한값을 설정하는 부분이 없다.

그러므로 LimitOffsetPagination 상속하는 별도의 클래스를 만들어 max_limit=10 이라는 설정을 통해 최대값을 제한해야한다. (안그러면 최대제한값에 제한이 없어 큰일난다…)

 

권한 인증

rest_framework.authentication.BasicAuthentication # 사용자 이름과 암호에 대한 HTTP 기본 인증을 제공한다.

rest_framework.authentication.SessionAuthentication #장고의 인증을 위한 세션 프레임워크로 작동한다.

 

스로틀

api get 제한을 거는 방법이다.

인증되지 않은사용자와 인증된사용자에 각각 차별된 get 제한을 있다.

rest_framework.throttling 모듈에서 3개의 스로틀 클래스를 제공한다.

BaseThrottle -> SimpleRateThrottle 클래스의 서브클래스다.

  • AnonRateThrottle : 익명사용자가 요청 있는 요청 비율 제한 (ip 걸러짐)
  • UserRateThrottle : 특정 사용자가 요청할 있는 속도 제한
  • ScopedRateThrottle : throttle_scope 속성에 할당된 값으로 식별되는 API 특정 부분에 대한 요청 비율을 제한한다.

 

필터

클래스

  • django_filters.NumberFilter
  • django_filters.DateTimeFilter

lookup_expr 값은 조회(lookup) 표현식 'gte', 'lte' 사용

gte: 크거나 같음 (greator then or equal)

lte: 작거나 같음 (less than or equal)

  • django_filters.AllValueFilter

지정문자열과 일치하는 필터 적용

이중 밑줄(__) 모델의 필드로 읽거나 개의 밑줄을 하나로 대체해 읽을 있다.

 

error

ImportError: Could not import 'rest_framework.filters.DjangoFilterBackend' for API setting 'DEFAULT_FILTER_BACKENDS'. ImportError: Module "rest_framework.filters" does not define a "DjangoFilterBackend" attribute/class.

 

중요)DjangoFilterBackend was deprecated in 3.7

Removed DjangoFilterBackend inline with deprecation policy. Use django_filters.rest_framework.FilterSet and/or django_filters.rest_framework.DjangoFilterBackend instead

 

settings.py

REST_FRAMEWORK > DEFAULT_FILTER_BACKENDS > rest_framework.filters.DjangoFilterBackend

use) django_filters.rest_framework.DjangoFilterBackend

 

 

error

AttributeError: module 'rest_framework.filters' has no attribute 'FilterSet'

views.py

from rest_framework import filters

use) django_filters.rest_framework import FilterSet

 

 

error

TemplateDoesNotExist at /player-scores/

django_filters/rest_framework/crispy_form.html

 

django rest framework 에서 cripsy_form 사용하기 위해서는 INSTALLED_APPS django_filters 추가해줘야한다.

 

error

filter_class 속성은 DRF 되었다. filterset_class 대체한다.

 

아래 명령어를 통해 종속성이 있는 패키지 리스트를 txt 파일로 export 해놓을 있다.

배포를 하기위해서는 항상 남겨놓는것이 좋다.

pip freeze > requirements.txt


 

5장부터는 플라스크를 이용한 API 이다.

열심히 읽자!

댓글 0
비밀글
준돌 Jundol / 2019.10.15 10:46 / Android

 

PC와 안드로이드 기기가 같은 무선망에 연결되어야한다.

0. 크롬 브라우저가 필요함.

1. PC에 안드로이드 adb 설치가 되어있어야한다. 

adb 설치는 구글에 찾아보면 나온다.

2. 안드로이드기기의 개발자 모드가 활성화 되어있어야한다.

3. pc와 안드로이드 기기를 usb 를 통해 연결한다.

usb 디버깅을 허용해야한다.

PC에 연결시 안드로이드 기기에 뜨는 얼럿창을 통해 컴퓨터 RSA키 지문 확인 과정을 거친 뒤 PC의 cmd 창에 adb devices 명령어를 통해 연결된 기기가 있음을 확인한다.

컴퓨터 RSA 키 지문 확인
adb devices 명령어

크롬 개발자 도구 (단축키 F12) 를 켜고 Main Menu (오른쪽 점 3개)를 클릭하고 More tools > Remote devices를 선택

Main Menu 를 통해  Remote Devices  탭 열기.

Discover USB devices 확인란이 활성화되었는지 확인

Discover USB Devices  확인란이 활성화되었습니다.
좌측 창에 안드로이드 기기명과 함께 Connected 가 보이면 연결에 정상적으로 성공한것이다.

 

4. proxy 설정이 필요하다. 

안드로이드 기기가 pc의 네트워크망을 통해 접속해야 한다.

proxy 설정에는 여러 유틸 프로그램이 있겠지만 여기서는 fiddler를 사용한다.

https://www.telerik.com/fiddler

 

Fiddler - Free Web Debugging Proxy - Telerik

Fiddler is a free web debugging tool which logs all HTTP(S) traffic between your computer and the Internet. Inspect traffic, set breakpoints, and fiddle with incoming or outgoing data.

www.telerik.com

 

fiddler proxy 설정

Tools > Options > Connections 탭

port 는 pc가 사용하지 않는 포트로 설정해야한다 (ex: 8888, 5555 등)

(중요)!! 여기서 허용할 포트는 인바운드 허용이되어있거나 이 테스트를 진행할때에는 PC의 방화벽을 해제해야한다.

Allow remote computers to connect 에 체크한다.

안드로이드 기기에서 연결된 와이파이 네트워크를 길게 눌러 설정에 들어가 pc의 무선네트워크 ip와 방금 proxy 설정한 포트를 기입해준다.

안드로이드기기에 proxy 설정

설정 후 안드로이드에서 인터넷 접속 시 pc의 fiddler 상에 접속 패킷 로그가 주르륵 뜨게된다.

안드로이드 통신 패킷 수집

 

5. 안드로이드 기기에서 pc의 hosts 파일에 정의한 사용자설정 로컬 도메인에 접속한다.

웹브라우저 앱 (ex. 삼성브라우저, 크롬)을 켜고 로컬 도메인에 접속한다.

정상적으로 접속 될것이며 구글 개발자 도구에서 안드로이드 기기 모델명을 클릭 > Inspect 클릭 하면 아래와 같이 새로운 창이 뜨게된다. 

개발자 도구에서 안드로이드 기기 inspect

모바일 레이아웃의 경우 확인이 어려운 경우가 종종 발생하는데 이런 디버깅 툴을 이용하면 웹 디버깅을 손쉽게 할 수 있다.

 

정말 좋은세상이다 ㅋㅋㅋㅋㅋ

 

참고사이트

1. Google Tools for Web Developers - 로컬 서버 액세스
https://developers.google.com/web/tools/chrome-devtools/remote-debugging/local-server

 

로컬 서버 액세스  |  Tools for Web Developers  |  Google Developers

개발용 컴퓨터 웹 서버에서 사이트를 호스팅한 다음 Android 기기에서 콘텐츠에 액세스합니다.

developers.google.com

2. Google Tools for Web Developers - Android 기기 원격 디버깅 시작하기
https://developers.google.com/web/tools/chrome-devtools/remote-debugging/

 

Android 기기 원격 디버깅 시작하기  |  Tools for Web Developers  |  Google Developers

Windows, Mac 또는 Linux 컴퓨터에서 Android 기기의 라이브 콘텐츠를 원격으로 디버그합니다.

developers.google.com

 

댓글 0
비밀글
준돌 Jundol / 2019.03.15 15:44 / ASP.NET4/MVC

서버 환경 

windows 7 professional K

IIS 7.5 

ASP.NET framework 4 설치완료인 상태에서 


MVC5 로 제작된 사이트를 구동하려 올렸으나 제목과 같은

Could not load file or assembly 'System.Web.WebPages.Razor, Version=2.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35' or one of its dependencies. The located assembly's manifest definition does not match the assembly reference. (Exception from HRESULT: 0x80131040)


Razor version2.0.0.0 의 dll 파일을 로딩하지 못한듯한 에러를 뿜어냈다.


https://stackoverflow.com/questions/19963307/how-to-install-asp-net-mvc-5-on-a-server


스택오버 플로우를 뒤져봤지만 별도로 MVC 를 설치하는게 아니라는 답변만 달려있었다.

이건 나도 알고있다. MVC는 설치하는게 아니라는걸.

근데 왜 안될까 더 검색해보니

https://stackoverflow.com/questions/11246861/could-not-load-file-or-assembly-system-web-webpages

[ install the Web Pages Version 2 on the server. ]

Web Pages Version 2 를 서버에 install 하라는 말이 있어 얼른 설치해봤다.


install 파일 다운로드 페이지

https://www.microsoft.com/ko-KR/download/details.aspx?id=34600


설치하고 iis 다시시작하니 정상적으로 로딩!


아마 낮은 버전의 iis에서는 별도로 install 해줘야 하는것같다.


파일명: AspNetWebPages2Setup.exe

첨부된 파일은 위변조되지않은 정상적인 MS사에서 제공하는 파일입니다.

의심되시면 위 URL insatll 다운로드 페이지에서 다운받아 설치하세요~

AspNetWebPages2Setup.exe



댓글 0
비밀글
준돌 Jundol / 2019.01.22 14:26 / iOS

꼼꼼한 재은씨의 스위프트 실전편 330p


버전업이 되면서 예문에 나오는 코드에서 변형이 있다.


change color and font in swift 4.2


원본

1
2
3
4
5
6
7
8
9
10
11
12
if let tbC = self.window?.rootViewController as? UITabBarController {
    if let tbItems = tbC.tabBar.items {
        for tbItem in tbItems {
            // 폰트 색상 변경
            tbItem.setTitleTextAttributes([NSAttributedStringKey.foregroundColor.rawValue: UIColor.gray], for: .disabled)          
            tbItem.setTitleTextAttributes([NSAttributedStringKey.foregroundColor.rawValue: UIColor.red], for: .selected)
          
              // 전체 아이템의 폰트 크기를 설정한다.
              tbItem.setTitleTextAttributes([NSAttributedStringKey.font.rawValue: UIFont.systemFont(ofSize: 15)], for: .normal)        
        }
    }
}                    
cs


Swift 4.2

1
2
3
4
5
6
7
8
9
10
11
12
if let tbC = self.window?.rootViewController as? UITabBarController {
    if let tbItems = tbC.tabBar.items {
        for tbItem in tbItems {
            // 폰트 변경
            tbItem.setTitleTextAttributes([NSAttributedString.Key(rawValue: NSAttributedString.Key.font.rawValue): UIFont.systemFont(ofSize: 30)], for: .normal)
            
            // 폰트 색상 변경
            tbItem.setTitleTextAttributes([NSAttributedString.Key(rawValue: NSAttributedString.Key.foregroundColor.rawValue): UIColor.yellow], for: .selected)
            tbItem.setTitleTextAttributes([NSAttributedString.Key(rawValue: NSAttributedString.Key.foregroundColor.rawValue): UIColor.green], for: .disabled)
        }
    }
}                    
cs


기존에는 rawValue 속성에 다이렉트로 값을 할당했던것 같다. 4.2에서는 rawValue에 할당해서 Key로 넘기는 방식이다.

또한 TabBar Item State 속성에서 .disabled 가 작동하지않는다;;

왜 작동이 안되는건지 모르겠다.


아시는 분 계시면 댓글 부탁드립니다...


추가)

.disabled가 왜 안되는지 모르겠지만 .normal 속성에 같이 할당하면 지장없이 사용할 수 있을것 같다.

예시

1
2
3
4
5
6
7
8
9
10
11
if let tbC = self.window?.rootViewController as? UITabBarController {
    if let tbItems = tbC.tabBar.items {
        for tbItem in tbItems {
            // 색상과 폰트 크기 같이 변경
            tbItem.setTitleTextAttributes([NSAttributedString.Key(rawValue: NSAttributedString.Key.font.rawValue): UIFont.systemFont(ofSize: 30), NSAttributedString.Key(rawValue: NSAttributedString.Key.foregroundColor.rawValue): UIColor.green], for: .normal)
            
            // 선택시 색상 변경
            tbItem.setTitleTextAttributes([NSAttributedString.Key(rawValue: NSAttributedString.Key.foregroundColor.rawValue): UIColor.yellow], for: .selected)    
        }
    }
}                    
cs



댓글 0
비밀글
준돌 Jundol / 2019.01.14 11:32 / iOS

꼼꼼한 재은씨의 스위프트 실전편

Chapter01 기본 기능 다루기: 메모장 앱 제작

이미지 피커 컨트롤러에서 이미지가 선택되었을 때 호출되는 델리게이트 메소드에서

info[UIImagePickerControllerEditedImage] 이부분이 에러발생한다.

Swift4.2에서는 책에 쓰인 4.0과는 약간의 수정이 있기 때문에 고쳐서 사용해야한다.


기존 예제 소스코드

1
2
3
4
5
6
7
8
  // 이미지 선택을 완료했을 때 호출되는 메소드
  func imagePickerController(_ picker: UIImagePickerController, didFinishPickingMediaWithInfo info: [String : Any]) {
    // 선택된 이미지를 미리보기에 표시한다.
    self.preview.image = info[UIImagePickerControllerEditedImage] as? UIImage
    
    // 이미지 피커 컨트롤러를 닫는다.
    picker.dismiss(animated: false)
  }
cs


변경 소스코드

1
2
3
4
5
6
    private func imagePickerController(_ picker: UIImagePickerController, didFinishPickingMediaWithInfo info: [UIImagePickerController.InfoKey : Any]) {
        if let editedImage = info[.editedImage] as? UIImage{
            self.preview.image = editedImage
            picker.dismiss(animated: false)
        }
    }
cs


[error] if let 구문을 사용해서 info[.editedImage] 에서 editedImage 상수에 할당해서 이미지를 불러온다.

[warning] imagePickerController를 private 접근제한자로 감싸줘야한다.

댓글 0
비밀글
svn2git을 이용해서 SVN에서 Git(bitbucket)으로 마이그레이션 하기
준돌 Jundol / 2018.12.24 15:02 / 형상관리

svn2git 사용기

난 자칭 git 찬양론자 예찬론자 무한git교 다.

회사내에서는 svn을 주로 사용하다가 git으로 점점 변화하는 추세이다.

신규프로젝트의 경우 대부분 git을 이용해서 시작한다.

하지만 기존 프로젝트들의 경우 svn을 계속해서 이용했는데 이는 변화를 두려워하는 동굴속의 이들도 한 몫을 하고있었다.

기존의 이력을 버리고 옮겨야된다는 두려움(변명) 때문에 깃으로 옮기지 못한다는... 


그래서 내가 내 담당 프로젝트들만이라도 svn 커밋 이력을 가지고 통채로 git으로 마이그레이션을 하고자 했다.


svn2git를 윈도우에서 그대로 사용하려했으나 몇시간의 삽질끝에 빡쳐서 virtualbox에 리눅스 올렸다.


1. 리눅스 설치 ubuntu 16.04 LTS 설치

Error: piix4_smbus base address uninitialized

Solution: Turn off the option "Enable Nested Paging" in the VirtualBox configuration under Settings->System->Acceleration.

This allowed me to get Ubuntu running with the desktop.


2. putty를 이용 접속하기 위해 vm 네트워크 포트포워딩


3. openssh 설치 

프로그램 확인

dpkg -l | grep openssh

클라이언트밖에 없을경우 openssh-server가 필요함

apt-get install openssh-server

ssh 실행

service ssh start

ssh 항목이 있는지 확인

service --status-all | grep +

몇번 포트로 되어있는지 확인

netstat -antp


3. putty 를 이용 리눅스 접속

host ip 에 본인의 로컬 PC IP를 입력 후 접속


4. 편하게 쓰기 위해 ubuntu vi 에디터 설정

vim 설치

apt-get install vim

사용자 계정의 홈 디렉터리 하위에 설정파일을 생성하여 설정파일 기재


cd ~

vim .vimrc

================================

set syntax on

set nu

set tabstop=4

set autoindent

set ruler

set showcmd

set title

set wmnu

set showmatch

set nocompatible

=================================

설정 저장 후 source 명령어로 .vimrc 파일을 적용한다.

source .vimrc



gem, jdk, git, ruby, svn2git 설치

5. gem 설치

apt-get install gem


6. jdk 설치

java 확인 (미설치시 설치되어있지않다고 뜸)

java -version

jdk (java) 설치

apt-get install default-jdk

java -version

(필자의경우 1.8로 설치되어있는것을 확인함)


7. git 설치

add-apt-repository ppa:git-core/ppa

apt-get update && sudo apt-get dist-upgrade

apt-get install git-core

git version

git version 2.20.1


8. ruby 설치

apt-get install ruby-full


9. svn2git 설치

gem install svn2git


10. 여기서부터 미친듯이 진짜로 엄청 중요하다. 기존 svn프로젝트에서 커밋 author 리스트를 추출해서 별도의 authors.txt 로 만들어놔야 svn history checkout 혹은 git push 할때 오류가 나지 않는다.

mkdir -p /home/svn/repos

cd /home/svn/repos

wget을 이용하여 변환도구를 다운로드 받는다.

wget https://bitbucket.org/atlassian/svn-migration-scripts/downloads/svn-migration-scripts.jar

정상 다운로드 확인

java -jar svn-migration-scripts.jar verify

svn author 정보 추출

java -jar svn-migration-scripts.jar authors http://svn.example.com/project {username} {passwd} > authors.txt

여기서 username 과 passwd 는 svn 계정정보로 변경한다.

mkdir ~/.svn2git

cp authors.txt ~/.svn2git/authors.txt

필자의 경우 svn사용시 브랜치와 태그를 사용하지 않았다. 하여 svn 프로젝트를 local git으로 이관하는 명령어 사용 시 옵션으로 브랜치와 태그를 가져오지않는다는 옵션을 사용했다.

svn2git https://svn.example.com/svn/myproject --nobranches --notags --authors ~/.svn2git/authors.txt

위 명령어 사용시 리비전넘버가 1부터 최근 리비전넘버까지 쭉쭉 올라가면서 git으로 가져오는게 보인다.

중간에 멈추거나 git svn fetch 에러 같은게 발생하면 대부분 authors 가 맞지않아서 발생하는 문제다.

authors 정보를 확인해서 수정한다.

리비전넘버가 끝까지왔고 에러를 뿜으면서 중지되는데 필자의경우 git gc 에러라고 보이며 멈추었다.

여기까지만되도 상관없는것으로 보인다.

git remote add origin [email protected]:group/myproject.git

git push -u origin master

퍼센트가 올라가면서 git master 에 푸시되는게 보인다.

여기까지되면 svn의 모든 history 를 git으로 이관하는게 완료되었다.

만약 막히는 부분이 있다면 아래 참고사이트 목록을 참고하여 열심히 삽질해보자!!



참고 사이트

1. vmware 에러 https://askubuntu.com/questions/298290/smbus-bios-error-while-booting-ubuntu-in-virtualbox

2. openssh 설치 https://jimnong.tistory.com/713

3. virtualbox vm 포트포워딩 http://hahaite.tistory.com/283

4. vi 에디터 설정 http://freestrokes.tistory.com/40

5. jdk 설치 https://m.blog.naver.com/opusk/220985259485

6. git 설치 https://thisblogbusy.tistory.com/entry/%EC%9A%B0%EB%B6%84%ED%88%AC-1604%EC%97%90%EC%84%9C-GIT-%EC%84%A4%EC%B9%98%ED%95%98%EA%B8%B0

7. ruby 설치 https://www.ruby-lang.org/ko/documentation/installation/

8. svn 계정정보 추출 http://lux.cuenet.kr/21

9. svn2git 사용법 https://www.lesstif.com/pages/viewpage.action?pageId=23757066

태그: bitbucket, git, Migration, SVN, svn2git, ubuntu
댓글 0
비밀글
[알고리즘] 5강 동적 프로그래밍 알고리즘
준돌 Jundol / 2018.06.18 00:53 / 방송통신대학교12/컴퓨터과학과 [3학년 1학기]

1. 동적 프로그래밍 방법의 원리

문제의 크기가 작은 소문제에 대한 를 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법

동적 프로그래밍 dynamic programming => 동적 계획법 (타 서적, 교육에서는 동적 계획법이라 많이 부른다.)

최솟값/최댓값을 구하는 최적화 문제에 적용

2. 피보나치 수열 문제

 

3. 연쇄 행렬 곱셈 문제

'방송통신대학교12 > 컴퓨터과학과 [3학년 1학기]' 카테고리의 다른 글

[알고리즘] 5강 동적 프로그래밍 알고리즘  (0) 2018.06.18
[알고리즘] 4강 분할정복 알고리즘 2  (1) 2018.05.25
[알고리즘] 3강 분할정복 알고리즘 - 1  (0) 2018.05.22
[알고리즘] 2강 알고리즘 소개  (0) 2018.05.22
[데이터베이스] 9강 인덱싱  (0) 2018.05.22
[데이터베이스] 8강 데이터의 저장  (0) 2018.05.18
댓글 0
비밀글
[알고리즘] 4강 분할정복 알고리즘 2
준돌 Jundol / 2018.05.25 00:27 / 방송통신대학교12/컴퓨터과학과 [3학년 1학기]

2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 3강 분할정복 알고리즘 - 1

2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

1. [복습] 분할정복 방법의 원리

순환적으로 문제를 푸는 하향식 접근 방법
주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식

'분할' - '정복' - 결합

특징
- 분할된 문제는 원래 문제와 동일(입력 크기만 감소) 하고 서로 독립적

적용 알고리즘
- 이진 탐색, 퀵 정렬, 합병 정렬, 선택 문제

 

2. 합병 정렬

분할 정복 방법을 가장 잘 표현하고 있는 알고리즘이다.

배열을 동일한 크기의 두 개의 부분배열로 분할하고,
각각의 부분배열을 순환적으로 정렬한 후, (정복)
정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦.

분할: 입력 크기 n인 배열을 크기 n/2 인 두 부분배열로 분할
정복: 각 부분배열에 대해서 합병 정렬을 순환적으로 적용하여 두 부분배열을 정렬
결합: 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

합병 정렬에서 분할은 신경쓸 필요없다. 합병이 중요한 부분이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
MergeSort(A[], n){
    if(n > 1){
        Mid = n/2;
        B[0..Mid-1= MergeSort(A[0..Mid-1], Mid);
        C[0..n-Mid-1= MergeSort(A[Mid..n-1], n-Mid);
        A[0..n-1= Merge(B[0..Mid-1], C[0..n-Mid-1], Mid, n-Mid);
    }
    return A;
}
 
Merge(B[], C[], n, m)
{
    i = j = k = 0;
    while(i<&& j<m){
        if(B[i] <= C[j]){
            A[k++= B[i++];
        }else{
            A[k++= C[j++];
        }
    }
    for(; i < n; i++) A[k++= B[i];
    for(; j < m; j++) A[k++= C[j];
    return A[0..n+m-1];
}
cs

 

성능 분석

두 부분배열 간의 비교 횟수 n/2 ~ ( n/2 + n/2 -1 = n - 1 )
최악의경우: Θ(n)
입력 데이터 개수만큼의 저장 장소가 추가로 필요하다.

합병 정렬 MergeSort() 수행시간
- 크기 n/2 인 두 번의 MergeSort() 순환 호출 + 한 번의 합병 Merge()
T(n) = T(n/2) + T(n/2) + Θ(n) (n>1)
T(1) = 1
                  ▼▼▼
         T(n) = 2T(n/2) + Θ(n)
                  ▼▼▼
             T(n) = O(nlogn)

퀵 정렬과 동일한 수행시간을 갖는다.

 

3. 선택 문제

선택문제란?
n개의 원소가 임의의 순서로 저장된 배열 A[0..n-1]에서 번째로 작은 원소를 찾는 문제

i = 1 > 최솟값
i = n/2 > 중간값
i = n > 최댓값

직관적인 방법
- 오름차순으로 정렬한 후 i번째 원소를 찾는 방법 > O(nlogn)
- 최솟값 찾는 과정을 i번 반복((i-1)번째까지는 최솟값을 찾은 후 삭제) > O(in)

최악 O(n2제곱), 평균 O(n) 알고리즘
최악 O(n), 평균 O(n) 알고리즘

3-1) 최솟값 찾기
각 데이터를 하나씩 모두 비교하는 방법
n개의 데이터에 대해서 최소한 (n-1)번의 비교가 필요 > O(n)

3-2) 최솟값과 최댓값 모두 찾기

최솟값 찾은 후 최댓값 찾는 방법(또는 최댓값 찾은 후 최소값 찾기)
n개의 데이터에서 최솟값을 찾는데 (n-1)번의 비교
 + (n-1)개의 데이터에서 최댓값을 찾는데 (n-2)번의 비교
==> 2n - 3 번의 비교

2n-3번의 비교가 아닌 (3/2)n -2번의 비교로 수행 가능
모든 원소를 두 개씩 짝을 이루어 동시에 최솟값/최댓값과 비교

1
2
3
4
5
6
7
8
9
10
11
12
FindMinMax(A[], n, min, max)
{
    if(A[0< A[1]){ min = A[0]; max = A[1]; }
    else { min = A[1]; max = A[0]; }
    for (i = 2; i < n; i++){
        if(A[i] < A[i+1] { small = A[i]; large = A[i+1]; }
        else { small = A[i+1]; large = A[i]; }
        
        if ( small < min ) min = small;
        if ( large > max ) max = large;
    }
}
cs

3-3) i번째로 작은 원소 찾기_ 최악 O(n2제곱), 평균 O(n)

개념과 원리
퀵 정렬의 분할 함수 Partition()을 순환적으로 적용한다.

분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할, i가 피벗의 인덱스와 같으면 피벗의 값을 반환하고 종료
정복: 인덱스 i가 포함된 부분배열에 대해서 선택 알고리즘을 순환적으로 적용
결합: 필요없음

1
2
3
4
5
6
7
8
9
10
11
12
int Selection(A[], n, i)
{
    Left = 0; Right = n -1;
    p = Partition(A, n);
    
    if(i == p + 1)
        return A[p];
    else if ( i < p + 1)
        Selection(A[Left..p-1], (p-1)-Left+1, i);
    else
        Selection(A[p+1..Right], Right-(p+1)-1, i-p-1);
}
cs

성능 분석

최악의경우 = 퀵 정렬의 최악의 경우
- 분할 함수가 항상 하나의 부분배열만 생성하는 경우
- 오름차순으로 정렬된 상태에서 i = n 을 찾는 경우 > 분할 함수 호출할 때 마다 피벗의 인덱스는 1씩 증가 > Partition()을 O(n)번 호출 => O(n제곱)
- 해결책 > 항상 일정한 비율의 두 부분배열로 분할, 최악의 경우에도 O(n)]

평균적인 경우 O(n)

 

3-4) i번째로 작은 원소 찾기_최악 O(n), 평균 O(n)

개념과 원리
특정한 성질을 만족하도록 피벗을 선택
> 항상 일정한 비율의 두 부분배열로 분할

피벗선택방법
① 크기 n인 배열의 원소를 5개씩 묶어 n/5개의 그룹 형성
- 5의 배수가 되지 않아 그룹을 생성하지 못한 채 남는 원소는 그대로 남겨 둔다.
② 각 그룹에 대해서 중간값을 찾음
③ n/5 개의 중간값들을 대상으로 다시 중간값을 찾음 > "중간값들의 중간값" => "피벗"

'방송통신대학교12 > 컴퓨터과학과 [3학년 1학기]' 카테고리의 다른 글

[알고리즘] 5강 동적 프로그래밍 알고리즘  (0) 2018.06.18
[알고리즘] 4강 분할정복 알고리즘 2  (1) 2018.05.25
[알고리즘] 3강 분할정복 알고리즘 - 1  (0) 2018.05.22
[알고리즘] 2강 알고리즘 소개  (0) 2018.05.22
[데이터베이스] 9강 인덱싱  (0) 2018.05.22
[데이터베이스] 8강 데이터의 저장  (0) 2018.05.18
태그: 알고리즘, 합병정렬
댓글 1
램브 / 2018.08.27 22:15 / 수정/삭제 / 댓글쓰기
혹시 티스토리 가입 초대장좀 보내주실 수 있을까요?
사진 게시를 위해 티스토리를 시작하려합니다
메일주소는 [email protected] 입니다 감사합니다!~
비밀글
[알고리즘] 3강 분할정복 알고리즘 - 1
준돌 Jundol / 2018.05.22 19:18 / 방송통신대학교12/컴퓨터과학과 [3학년 1학기]

2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

 

1. 분할정복 방법의 원리

1) 적용 알고리즘에서의 분할 과정

1-1) 이진탐색

중간 값을 기준으로 양쪽으로 분할한다. 한쪽은 사용 할 필요가 없다. 한쪽에서 분할 하고 분할하고 분할되지 않을때까지 분할한다.

n > n/2 , n/2 > n/4 , n/4 ...

1-2) 합병 정렬

정확히 절반크기의 두 개로 분할한다. 여기까지는 이진탐색과 동일하나 이진탐색은 한쪽은 사용하지않지만 합병정렬은 양쪽을 전부 사용한다.

n > n/2 , n/2 > n/4 , n/4 , n/4 , n/4 > ... 

1-3) 퀵 정렬

두개로 분할하는것은 맞으나 합병정렬은 정확히 두 개로 분할했다면 퀵정렬은 크기를 모름. 한쪽은 크고 한쪽은 작고 똑같을 수 도있고 크기가 다양한 일정하지않은 두 개로 분할하는 특징을 가진다.

n (=a+b) > a , b > ...

1-4) 선택 문제

 

 

2. 이진 탐색

탐색방법

이진탐색의 분할 정복 결합 적용

알고리즘_(순환형태)

1
2
3
4
5
6
7
8
BinarySearch(A[], Left, Right, x)
{
    if(Left > Right) return -1// 탐색실패
    Mid = (Left + Right)/2;
    if(x==A[Mid]) return Mid;
    else if (x<Mid) BinarySearch(A, Left, Mid-1, x); // 왼쪽 부분배열
    else BinarySearch(A, Mid+1, Right, x); // 오른쪽 부분배열
}
cs

     알고리즘 (반복형태)

1
2
3
4
5
6
7
8
9
10
11
BinarySearch_Iteration(A[], n, x)
{
    Left = 0; Right = n-1;
    While(Left <= Right){
        Mid == (Left+Right) / 2;
        if(x==A[Mid]) return Mid;
        else if (x<Mid) Right = Mid - 1// 왼쪽 부분배열
        else Left = Mid + 1;    // 오른쪽 부분배열
    }
    return -1// 
}
cs

 

이진 탐색에서의 분할과 비교

n/2의k제곱 = 1 이 될때 까지 → k = log n


성능 분석

T(n) = 입력 크기 n에 대한 탐색 과정에서의 모든 비교 횟수의 합
     = 맨 바깥 수준에서의 비교 횟수 + 순환 호출에서의 비교 횟수

T(n) = T(n/2) + O(1) (n>1), T(1) = 1

T(n) = logN

이진탐색 특징

 

3. 퀵 정렬

특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식
- 오름차순으로 정렬한다고 가정한다.

피벗 pivot
두 부분배열로 분할할 때 기준이 되는 특정 원소 (보통 주어진 배열의 첫 번째 원소로 지정)

(피벗을 기준으로 왼쪽과 오른쪽으로 나누고 각각의 부분배열에 대해서 퀵정렬을 순환적으로 한다.)

 

1) 피벗이 제자리를 잡도록 하여 정렬하는 방식

분할 전 데이터 : 30, 45, 20, 15, 40, 25, 35, 10

1. (첫 데이터인 30을 피벗으로 정한다.)

분할 후 : { 25, 10, 20, 15 } 30 { 40, 35, 45 }
             왼쪽 부분배열       오른쪽 부분배열

피벗을 기준으로 보았을 때 왼쪽부분배열의 모든값은 피벗보다 작은 값들이다.
오른쪽 부분배열의 모든 값은 피벗보다 다 크다.

 

 

2) 알고리즘

1
2
3
4
5
6
7
8
QuickSort(A[], n)
{
    if(n>1){
        pivot = Partition(A[0..n-1], n);    // 두 부분배열로 분할
        QuickSort(A[0..pivot-1], pivot);     // 왼쪽 부분배열에 대한 순환 호출
        QuickSort(A[pivot+1..n-1], n-pivot-1);    //오른쪽 부분배열에 대한 순환 호출
    }
}
cs

 

알고리즘 분할함수 Partition()

1
2
3
4
5
6
7
8
9
10
11
12
13
int Partition(A[], n)
{
    Left = 1; Right = n-1;
    while(Left < Right){                // 피벗 A[0]
        // 피벗보다 큰 값의 위치를 찾음
        while(Left < n && A[Left] < A[0]) Left++;
        // 피벗보다 작은 값의 위치를 찾음
        while(Right > 0 && A[Right] >= A[0]) Right--;
        if(Left < Right) 교환(A[Left] ↔ A[Right])
        else 교환(A[0] ↔ A[Right])
    }
    return Right;
}
cs

 

3) 분할과정

 

퀵 정렬의 적용 예

85보다도 88 피벗이 더 큰값이므로 맨오른쪽에 무한대의 값이 있다고 가정한다.

 

4) 성능분석

4-1) 분할함수 Partition() 수행 시간

피벗을 제외한 모든 원소는 1번~ 최대 2번 비교한다.
n ~ 2n
선형시간 Θn 을 갖는다.

4-2) 퀵 정렬 Quicksort() 수행 시간

한 번의 분할 Partition() + 두 번의 Quicksort() 순환 호출
T(n) = T(배열) + T(배열) + Θ(n) (n > 1)
T(1) = Θ(1)

 

4-3) 최악의 경우

피벗만 제자리를 잡고, 나머지 모든 원소가 하나의 부분배열로 분할되는 경우

극심한 불균형적 분할
- 피벗만 제자리를 잡고, 나머지 모든 원소가 하나의 부분배열로 분할되는 경우
- 피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우
- 입력 데이터가 정렬된 경우 AND 피벗을 배열의 처음 원소로 지정한 경우

T(n) = (Tn-1) + T(0) + Θ(n) (n>0), T(0)=0
                        ▼▼▼
                T(n) = T(n-1) + Θ(n)
                        ▼▼▼
                   T(n) = O(n2제곱)

 

4-4) 최선의 경우

피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우

가장 균형적인 분할
- 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
- 피벗이 항상 부분배열의 중간값이 되는 경우

T(n) = T(n/2) + T(n/2) + Θ(n) (n>1)
T(1) = 1
                        ▼▼▼
            T(n) = 2T(n/2) + Θ(n)
                        ▼▼▼
                    T(n) = O(nlogn)

 

4-5) 평균적인 경우

부분배열의 모든 분할 비율에 따른 수행시간의 평균
- 피벗은 동일한 확률로서 분할 후 배열의 어느 곳에나 위치 가능
- 0:n-1, 1:n-2, 2:n-3, ... , n-2:1, n-1:0

T(1) = T(0) = 0
T(n) = 1/n n∑i=1 (T(I-1) + T(n-I)) + Θ(n),  n ≥ 2
                        ▼▼▼
                     T(n) = O(nlogn)

퀵 정렬의 특징

'방송통신대학교12 > 컴퓨터과학과 [3학년 1학기]' 카테고리의 다른 글

[알고리즘] 5강 동적 프로그래밍 알고리즘  (0) 2018.06.18
[알고리즘] 4강 분할정복 알고리즘 2  (1) 2018.05.25
[알고리즘] 3강 분할정복 알고리즘 - 1  (0) 2018.05.22
[알고리즘] 2강 알고리즘 소개  (0) 2018.05.22
[데이터베이스] 9강 인덱싱  (0) 2018.05.22
[데이터베이스] 8강 데이터의 저장  (0) 2018.05.18
태그: 분할정복, 알고리즘, 이진탐색, 퀵정렬, 피벗
댓글 0
비밀글
[알고리즘] 2강 알고리즘 소개
준돌 Jundol / 2018.05.22 13:42 / 방송통신대학교12/컴퓨터과학과 [3학년 1학기]

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

1. 알고리즘의 설계

1) 최댓값 찾기

1-1) 값들을 하나씩 모두 비교해 가면서 최댓값을 찾는 방법
1-2) 토너먼트 방식
    둘씩 비교해서 큰값을 찾아가는 방법
더 효율적인것을 결정해야한다.

(n-1)번 1-1과 1-2 의 효율성은 7번으로 같다.

2) 뒤섞인 카드에서 원하는 카드 찾기

2-1) 순차탐색(Sequential Search) 순차적으로 전부 다 뒤집는다

1
2
3
4
5
6
7
8
SequentialSearch(A[], n, x)
// 배열 A[0..n-1]에서 x를 찾는 알고리즘
{
    for(i = 0; i < n; i ++){
        if(x == A[i]) return i;
    }
    return -1;
}
cs

모든 배열의 원소를 전부 다 비교


2-2) 카드가 오름차순으로 나열되어 있다면 이진탐색(binary search)

1
2
3
4
5
6
7
8
BinarySearch(A[], Left, Right, x)
{
    if(Left>Right) return -1;
    Mid = (left + right) / 2;
    if(x == A[mid]) return Mid;
    else if (x<A[mid]) BinarySearch(A, Left, Mid-1, x)
    else BinarySEarch(A,Mid+1,Right,x);
}
cs

데이터가 뒤죽박죽일때는 순차탐색, 정렬되어있다면 이진탐색이 더 좋다.

> 주어진 문제, 속성, 조건 등의 매우 다양
 => 일반적이고 범용의 기법은 미존재

> 대표적인 설계 기법
- 분할정복 divide and conquer 방법
- 동적 프로그래밍 dynamic programming 방법
- 욕심쟁이 greedy 방법

2. 알고리즘의 분석

1) 정확성 분석 (다루지않음 이미 정확하다고 증명이 된 알고리즘만 학습한다.)

2) 효율성 분석 (보통의 알고리즘 분석은 효율성 분석을 말한다.)

3) 시간 복잡도

1
2
3
4
5
6
7
8
9
10
11
SumAverage(A[], n)
//A[0.. n-1], n : 입력 배열과 데이터 개수
    sum = 0;
    i = 0;
    while(i<n){
        sum = sum + A[i];
        i = i + 1;
    }
    average = sum / n;
    print sum, average;
}
cs

 

시간복잡도와 점근성능 빅오 표기법으로 까지 도출 할 수 있어야 한다.

 

3. 점근 성능

정의: 입력크기 n이 무한대로 커짐에 따라 결정되는 성능

데이터의 개수가 증가한다. 15개를 기준으로 효율성의 크기가 달라진다.

수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현
(최고차항만이 가장 큰 영향력을 행사하기 때문이다.)
수행시간의 어림값, 수행 시간의 증가 추세 파악이 용이 > 알고리즘의 우열을 표현

1) 점근성능의 표기법

1-1) 정의 'Big-oh' 점근적 상한 (최악의 수행시간)

어떤 양의 상수 c와 n0이 존재하여 모든 n≥n0에 대하여 f(n)≤cㆍg(n)이면 f(n) = O(g(n))이다.

1-2) 'Big-omega' 점근적 하한 (최선의 수행시간)

어떤 양의 상수 c와 n0이 존재하여 모든 n≥n0에 대하여 f(n)≥cㆍg(n)이면 f(n)=Ω(g(n)) 이다.

1-3) 'Big-theta' 점근적 상하한 (알고리즘의 수행시간을 좀 더 엄밀하게 나타낼 수 있다)

어떤 양의 상수 c1, c2와 n0이 존재하여 모든 n≥n0에 대하여 c1ㆍg(n)≤f(n)≤c2ㆍg(n) 이면 f(n) = Θ(g(n)) 이다.

(점근적 상하한)

 

2) 주요 O-표기 간의 연산 시간의 크기 관계


◀◀◀효율적                                                                                                                    비효율적▶▶▶
상수시간: 데이터의 개수와 상관없이 소요시간은 일정하다.

 

3) 효율적인 알고리즘의 중요성

 

4) 알고리즘의 시간 복잡도 구하기

알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도로 취함
g(n)은 최고 차수에 의존

 

4. 순환 알고리즘의 성능

1) 순환 recursion, 재귀
알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태

BinarySearch() 를 계산하면 T(n) = T(n/2) + O(1), T(1) = c1

이진탐색의 수행시간은 O(log n) 이다.

일일이 점화식으로 계산하기엔 여간 복잡한게 아니다.

모두 다 기억하긴 어렵지만 2,3,6번은 기억해야한다.

한가지만 기억해도 본전 뽑는다 최! 고! 차! 항! 만 기억하자!

태그: 빅오표기법, 알고리즘
댓글 0
비밀글
© 2015 Jundol in 음 아마 비둘기보단 똑똑할꺼야
Designed by DH / Powered by Tistory
169 / 1 / 162,282