codility 4-4. MaxCounters

|

문제출처

문제

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4
the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)
that, given an integer N and a non-empty zero-indexed array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

a structure Results (in C), or
a vector of integers (in C++), or
a record Results (in Pascal), or
an array of integers (in any other programming language).
For example, given:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Assume that:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].
Complexity:

expected worst-case time complexity is O(N+M);
expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

풀이코드

def solution(N, A):
    result = [0] * N
    for i in A:
        if 1 <= i <= N:
            result[i-1] += 1
        else:
            result = [max(result)] * N # O(N)
    return result

다른사람 코드

def solution(N, A):

    counters = N * [0]
    next_max_counter =  max_counter = 0

    for oper in A:
        if oper <= N:
            current_counter = counters[oper-1] = max(counters[oper-1] +1, max_counter+1)
            next_max_counter = max(current_counter, next_max_counter)
        else:
            max_counter = next_max_counter

    return [c if c > max_counter else max_counter for c in counters]

클래스 기반 뷰 (Class Based View) - ListView, DetailView

|

0. 들어가기

django를 사용하여 웹페이지를 만들다 보면 아래와 같은 view를 작성하는 경우가 많이 생긴다.

  1. 특정 DB table의 모든 record를 가져와서 List로 표시 (예: 게시판 글 목록 전체)
  2. 특정 DB table의 톡정 record를 가져와서 Detail 내용 표시 (예 : 게시판의 특정 글 상세 내용)

파이썬 웹프로그래밍 책의 내용 중 동일한 view를 FBV(Function Based View) 와 CBV (Class Based View) 로 각각 구현하는 부분이 있었다. 해당 내용을 실습하며 용도에 맞춰 사용한다면 CBV를 활용해서 더 간단하게 view를 구현할 수 있다는 걸 알 수 있었다.


1. 글 목록 전체 표시 (List)

1-1. FBV 를 활용하여 글 목록 전체 표시

  • urls.py
from django.conf.urls import url
from . import views

urlpatterns = [
    url(r'^$', views.index, name='index'),
]
  • views.py
from django.shortcuts import render
from .models import Question


def index(request):
    latest_question_list = Question.objects.order_by('-pub_date')[:5] # 최근 5개의 질문 리스트만 가져온다.
    context = {'latest_question_list' : latest_question_list}
    return render(request, 'polls/index.html', context)

1-2. CBV - ListView 를 활용하여 글 목록 전체 표시 (예시1)

  • 게시판의 글 목록 전체를 표시하거나, 특정 DB table의 record 전체 (혹은 일부)를 List로 표시할 때 활용할 수 있다.
  • 리스트가 테이블의 모든 레코드인 경우 모델 클래스만 지정하면 된다.
  • urls.py
from bookmark.views import BookmarkLV

urlpatterns = [
	url(r'^bookmark/$', BookmarkLV.as_view(), name='index' ),
]
  • views.py
from django.views.generic import ListView
from bookmark.models import Bookmark

class BookmarkLV(ListView):
	"""
	ListView 디폴트 지정 속성
	1) 컨텍스트 변수 : object_list
	2) 템플릿 파일 : bookmark_list.html (모델명소문자_list.html)
	"""
	model = Bookmark

1-3. CBV - ListView 를 활용하여 글 목록 전체 표시 (예시2)

  • urls.py
from django.conf.urls import url
from . import views

urlpatterns = [
    url(r'^$', views.IndexView.as_view(), name='index'), # as_view() 클래스 함수를 통해 함수뷰 생성
]
  • views.py
from django.views.generic import ListView
from .models import Question

class IndexView(ListView):
    template_name = 'polls_cbv/index.html' # 디폴트 템플릿명: <app_label>/<model_name>_list.html
    context_object_name = 'question_list' # 디폴트 컨텍스트 변수명 :  object_list
    def get_queryset(self): # 컨텍스트 오버라이딩
      return Question.objects.order_by('-pub_date')[5:]
  • 디폴트 설정을 그대로 사용한다면 아래와 같이 간단하게 작성할 수 있다.
from django.views.generic import ListView
from .models import Question

class IndexView(ListView):
    def get_queryset(self): # 컨텍스트 오버라이딩
      return Question.objects.order_by('-pub_date')[5:]

2. 특정 글 상세 표시 (Detail)

  • 게시판 글 상세내용을 표시하는 것과 같이, 특정 DB table의 특정 record 상세내용을 표시할 때 활용할 수 있다.
  • 조회시 사용할 Primary Key 값은 URLconf에서 추출하여 뷰로 넘어온 파라미터(PK) 를 사용한다.

2-1. FBV 를 활용하여 특정 글 상세내용 표시

  • urls.py
from django.conf.urls import url
from . import views

urlpatterns = [
    url(r'^(?P<question_id>\d+)/$', views.detail, name='detail'),
]
  • views.py
from django.shortcuts import get_object_or_404, render
from .models import Question

def detail(request, question_id):
    question = get_object_or_404(Question, pk=question_id)
    return render(request, 'polls/detail.html', {
        'question': question,
    })

2-2. CBV - DetailView 를 활용하여 특정 글 상세내용 표시 (예시 1)

  • urls.py
from bookmark.views import BookmarkDV

urlpatterns = [
	url(r'^bookmark/(?P<pk>\d+)/$', BookmarkDV.as_view(), name='detail'),
]

  • views.py
from django.views.generic import DetailView
from bookmark.models import Bookmark

class BookmarkDV(DetailView):
	"""
	DetailView 디폴트 지정 속성
	1) 컨텍스트 변수 : object (URLConf 에서 pk 파라미터 값을 활용하여 DB 레코드 조회)
	2) 템플릿 파일 : bookmark_detail.html (모델명소문자_detail.html)
	"""
	model = Bookmark

2-3. CBV - DetailView 를 활용하여 특정 글 상세내용 표시 (예시 2)

  • urls.py
from django.conf.urls import url
from . import views

urlpatterns = [
    url(r'^(?P<pk>\d+)/$', views.DetailView.as_view(), name='detail'),
]
  • views.py
from django.views.generic import DetailView
from .models import Question


class DetailView(DetailView):
    model = Question # 해당 모델 - URLConf 의 PK 변수를 활용하여 해당 모델의 특정 record를 컨텍스트 변수(object)에 담는다.
    template_name = 'polls_cbv/detail.html' # 디폴트 템플릿명: <app_label>/<model_name>_detail.html
    context_object_name = 'question' # 디폴트 컨텍스트 변수명 :  object
  • 디폴트 설정을 그대로 사용한다면 아래와 같이 간단하게 작성할 수 있다.
from django.views.generic import DetailView
from .models import Question


class DetailView(DetailView):
    model = Question

3. (참고) CBV - ListView 에서 pagination 구현하기

  • views.py
class IndexView(ListView):
    model = Question
    paginate_by = 10 # 한 페이지에 보여줄 오브젝트의 갯수

  • 템플릿

<h2>설문조사 질문 리스트</h2>

{% if object_list %}
<ul>
  {% for question in object_list  %}
  <li><a href="{% url 'polls_cbv:detail' question.id %}">{{ question.question_text }}</a></li>
  {% endfor %}
</ul>
{% else %}
<p>설문조사 목록이 없습니다.</p>
{% endif %}

<!-- bootstrap style을 적용한다. -->
{% if is_paginated %}
<ul class="pagination">
  {% if page_obj.has_previous %}
    <li><a href="?page={{ page_obj.previous_page_number }}">&laquo;</a></li>
  {% else %}
    <li class="disabled"><span>&laquo;</span></li>
  {% endif %}
  {% for i in paginator.page_range %}
    {% if page_obj.number == i %}
      <li class="active"><span>{{ i }} <span class="sr-only">(current)</span></span></li>
    {% else %}
      <li><a href="?page={{ i }}">{{ i }}</a></li>
    {% endif %}
  {% endfor %}
  {% if page_obj.has_next %}
    <li><a href="?page={{ page_obj.next_page_number }}">&raquo;</a></li>
  {% else %}
    <li class="disabled"><span>&raquo;</span></li>
  {% endif %}
</ul>
{% endif %}


views
ListView에서 pagination 구현결과

170501-0507_TIL

|

5월 7일 (일)

오늘 할 일 (계획)

오늘 한 일 (회고)

  • 파이썬 웹 프로그래밍 실전편을 읽고 실습내용인 blog, bookmark 앱을 만들었다.
    • FBV가 아닌 CBV를 사용하여 구현하는 내용이라 익숙치 않아서 시간이 더 걸렸다.
    • 전에 배웠던 ListView, DetailView에 더해서 날짜관련 (dates) generic 뷰를 사용해보았다.
    • ArchiveIndexView, YearArchiveView, MonthArchiveView, DayArchiveView, TodayArchiveView
    • 날짜를 기준으로 연도별, 월별, 일별 포스트를 표시하는 뷰를 구현할 때 유용하게 활용할 수 있겠다는 생각이 들었다. (pytz 패키지 필요)
  • AskDjango 장고 기본강의를 들었다.
    • Form Validation
    • Form 클래스 내 clean 멤버함수를 통해 유효성 검사를 수행하고 리턴값을 통해 값을 변환할 수 있다. (멤버함수명 : clean_필드명)
  • 알고리즘 문제를 풀었다.
    • 다른 사람의 풀이를 보면 비트연산자를 활용한 경우가 종종 있는데, 비트연산자를 공부해야겠다는 생각이 든다.
    • 찾아보니 codecademy에 비트 단위(Bitwise) 연산자 입문 코스가 있다.

내일 할 일

5월 6일 (토)

오늘 한 일 (회고)

내일 할 일


5월 5일 (금)

오늘 한 일 (회고)

  • AskDjango 장고 기본강의를 들었다.
    • URL Reverse : 모델 클래스 내 get_absolute_url 함수를 활용해서 코드를 좀 더 간결하게 만들 수 있다고 한다. 내용정리
    • django template engine - template tag, template filter
    • HTML Form
    • Cross Site Request Forgery
    • 뷰 함수 호출 시 인자와 리턴값 (HttpRequest, HttpResponse)
  • 알고리즘 문제를 풀었다. 시간복잡도를 고려하면서 풀어야겠다고 생각했다. 찾아보니 파이썬 자료형 주요 시간복잡도를 정리해 놓은 페이지(TimeComplexity) 가 있어서 따로 정리해두었다. 내용정리

내일 할 일


5월 4일 (목)

오늘 할 일 (계획)

오늘 한 일

내일 할 일


5월 3일 (수)

오늘 한 일 (회고)

내일 할 일


5월 2일 (화)

오늘 한 일 (회고)

  • 파이썬 웹프로그래밍을 읽고 polls 애플리케이션을 CBV를 활용하여 재구현했다.
  • AskDjango 장고 기본강의 클래스 기반 뷰 (Class Based View) 부분을 들었다. 용도에 맞게 FBV, CBV 를 구분해서 사용하는게 중요하고, form 관련 처리 view는 FBV에 충분히 익숙해 질 때까지 CBV는 사용하지 않는게 좋다고 한다.
  • django rest framework, Django REST Swagger를 설치하고 페이지를 띄우는 것 까지는 했는데 Rest framework라는게 뭔지, 이게 왜 필요한지 이해가 부족하여 일단 멈춤.

내일 할 일


5월 1일 (월)

오늘 한 일 (회고)

  • 파이썬 웹프로그래밍 4장과 5장을 읽었다.
    • form을 처리하려면 2가지 view가 필요한데 (form을 보여주는 view, 제출 된 form을 처리하는 view) 장고에서는 하나의 view에서 get 요청과 post 요청을 처리하는 것이 권장된다고 한다. (그동안 별도의 view로 처리해야 한다고 생각하고 있었다)
    • 두번째 실습으로 CBV를 활용해서 어플리케이션을 만들었다. FBV 에서 여러줄로 코딩했던 부분을 2-3줄로 짧게 처리할 수 있다는 점이 놀라웠다.
    • DB Table의 레코드 list를 표시하거나 (ListView), 특정 레코드의 상세내용을 (DetailView) 표시하는 view를 만들 때 편리하게 사용할 수 있겠다는 생각이 든다. (우선 FBV 부터 익숙해져야..)
  • postgreSQL 을 설치하고 django project에 적용해보았다. 선생님께 vagrant라는 가상환경 관리툴을 사용해서 postgreSQL 서버를 실행하라는 조언을 들었지만 어려워서 나중에 적용하기로.. 일단은 가장 간단한 방법으로 psycopg2 패키지 설치, postgreSQL 프로그램 설치, django 설정 파일 수정 후 적용만 진행했다.

내일 할 일


이번 주에 읽은 글

codility - OddOccurrencesInArray

|

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the elements at indexes 0 and 2 have value 9, the elements at indexes 1 and 3 have value 3, the elements at indexes 4 and 6 have value 9, the element at index 5 has value 7 and is unpaired. Write a function:

def solution(A)

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the function should return 7, as explained in the example above.

Assume that:

N is an odd integer within the range [1..1,000,000]; each element of array A is an integer within the range [1..1,000,000,000]; all but one of the values in A occur an even number of times. Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(1),

beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

풀이과정

  • 빈 배열 idxs 를 정의
  • list A 를 for문으로 순환하면서 해당 item과 동일한 요소가 list A 안에 있다면
    • 배열 idxs 에 해당하는 요소들의 index 값을 추가한다.
    • 배열 idxs 에 추가된 index에 해당하는 요소들은 비교를 수행하지 않는다.(continue 처리)
  • list A 를 for문으로 순환하면서 해당 item과 동일한 요소가 list A 안에 없다면
  • 해당 item을 리턴한다.

풀이코드

  • detected time complexity: O(N**2)
  • for 문 안에서 if 문을 통해 배열을 탐색 => N^2
  • 시간복잡도 O(N**2)이라서 몇가지 테스트는 시간 초과로 통과하지 못했다.
def solution(A):
    idxs = []
    for idx, item in enumerate(A):
        if idx in idxs:
            continue
        elif item in A[idx+1:]:
            idxs.append(idx)
            idxs.append(A[idx+1:].index(item) + idx + 1)
        else:
            return item

다른사람 코드 1

  • Detected time complexity: O(N) or O(N*log(N))
  • 파이썬에서 sorted() 메소드는 O(N*log(N)) 의 성능을 가진다고 한다.
  • 간단하고 빠르다! 이렇게 단순하게 문제에 접근하는 습관을 들여야겠다. 이런 코드 좋다 :)
def test3(A):
    if len(A) == 1:
        return A[0]

    A = sorted(A)
    print(A)
    for i in range(0, len(A), 2):
        if i+1 == len(A):
            return A[i]
        if A[i] != A[i+1]:
            return A[i]

test3([1,2,1,2,3])

다른사람 코드 2

  • Detected time complexity: O(N) or O(N*log(N))
  • 한 줄로 풀어버리다니..
  • 파이썬의 ^ 연산자에 대한 설명
  • 2개의 수를 2진수로 바꿔서 비교한다. 각 자리수가 같으면 0, 다르면 1
def solution(A):
  return reduce(lambda x,y: x^y, A)

매번 찾아보는 python 개발환경 세팅 (pyenv, virtualenv, autoenv) + django 프로젝트 및 앱 생성하기

|

목차

프로젝트별 버전관리, 패키지 의존성 관리를 위해서 pyenv, virtualenv, autoenv 를 활용한다.


들어가기

django로 연습 프로젝트를 만들다 보면 항상 처음에 아래 2가지를 진행하게 된다.

  1. python 개발환경 세팅
  2. django 프로젝트 및 app 생성

명령어를 외우지 못해서 매번 찾아보게 되는데, 이번 기회에 참고하기 쉽도록 정리해두려고 한다.


1. pyenv

  • pyenv (파이썬 버전관리 프로그램) 를 활용하여 원하는 파이썬 버전을 설치한다.

pyenv 설치

  • 파이썬 버전관리 프로그램 (Simple Python Version Management)
  • pyenv 설치
# 설치
$ brew update
$ brew install pyenv

#~/.zshrc - zsh을 사용하는 경우
$ atom ~/.zshrc # atom을 통해서 파일에 아래 내용 입력

export PYENV_ROOT=/usr/local/var/pyenv
if which pyenv > /dev/null; then eval "$(pyenv init -)"; fi
if which pyenv-virtualenv-init > /dev/null; then eval "$(pyenv virtualenv-init -)"; fi

$ source ~/.zshrc #재실행
$ exec "$SHELL" # shell 재실행

pyenv를 활용한 python 설치

  • 파이썬 설치 전 필요 패키지 설치
    • https://github.com/yyuu/pyenv/wiki/Common-build-problems
$ pyenv version
$ pyenv install --list # 설치 가능한 패키지 목록 (파이썬 버전별 목록)
$ pyenv install 3.6.0 # python 설치
$ pyenv shell 3.6.0 # pyhotn 3.6.0으로 shell 실행 > autoenv를 사용하면 별도 지정이 필요 없음
$ python --version
  • pyenv global 설정을 통해서 기본으로 실행될 python 버전을 설정 가능하다. (시스템 python에는 영향 없음)
$ pyenv global 3.5.3
$ python --version
# Python 3.5.3

$ pyenv global system
$ python --version
#Python 2.7.10

2. virtualenv

  • virtualenv(독립된 개발환경을 제공해주는 프로그램) 를 활용하여 가상 개발환경을 구축한다.
  • 가상환경 위에서 원하는 버전의 django 및 패키지를 설치한다.

virtualenv 설치

# brew로 설치
$ brew install pyenv-virtualenv

# 설치 후 .zshrc 파일에 아래 내용 추가
eval "$(pyenv init -)"
eval "$(pyenv virtualenv-init -)"

가상환경 추가 및 실행

$ pyenv virtualenv 3.6.0 css-3.6.0 # css-3.6.0 이라는 가상환경을 추가
$ pyenv versions # 가상환경 리스트 확인 - .pyenv 폴더 안에 존재

# 가상환경 실행 및 종료
$ pyenv activate css-3.6.0
$ pyenv deactivate

가상환경 위에 django 및 패키지 설치

$ pip install django==1.10 # django 설치
$ pip install jupyter # jupyter 설치
$ pip freeze # 설치한 패키지 리스트 확인

# 유용한 패키지 예시

$ pip install django-extensions # settings.py 내 INSTALLED_APPS에 django_extensions 추가 필요
$ pip install "ipython[notebook]"
$ python manage.py shell_plus # 익스텐션 앱을 설치하면 shell_plus 사용가능, 필요한 모델을 자동 import 해줘서 편리함
$ python manage.py shell_plus --notebook # jupyter notebook을 통해서 djnago shell을 사용하면 좀더 친숙한 UI로 볼 수 있고, 이미지 결과를 확인 할 수 있다. 입력 이력을 로그로 남길 수 있음

requirement.txt

  • 필요한 라이브러리(ipython, django 등)를 설치하여 개발환경 세팅 후 requirements.txt를 만든다.
  • requirements.txt가 있다면 다음 명령을 통해 동일한 파이썬 패키지들을 한번에 설치할 수 있다.
$ pip3 freeze > requirements.txt  # 패키지 목록을 txt 파일로 만들기
$ pip3 install -r requirements.txt  # 한번에 패키지 설치

3. autoenv

(추가) local에 가상환경 설정

  • pyenv local 명령을 통해서 원하는 디렉토리에 가상환경을 지정할 수 있다. (자동 on/off) 따라서 별도로 아래의 autoenv를 설치할 필요가 없다!
  • 사용할 폴더로 이동 후 아래 명령을 시행하면 .python-version 파일이 생성된다.
pyenv local fc-python(가상환경이름)
pyenv global <가상환경이름> # 기본으로 사용할 환경 설정

autoenv

  • autoenv를 설치하고 프로젝트 폴더에 .env 파일을 만들어 자동으로 가상환경이 실행되도록 만든다.
  • autoenv : Directory-based environments, 폴더 안에 .env 파일이 있으면 해당 폴더에 들어갈 때 자동으로 가상환경이 실행된다.

autoenv 설치

$ brew install autoenv # 설치 (Using Homebrew)
$ echo "source $(brew --prefix autoenv)/activate.sh" >> ~/.zshrc
$ exec "$SHELL" # 재실행

.env 파일 작성 및 실행

# 프로젝트 폴더로 이동 후
$ touch .env
$ vim .env

# .env 파일에 아래 내용 입력   
$ pyenv activate css-3.6.0 # 원하는 가상환경 이름 (virtualenv로 생성한) 을 입력
$ cd ./ # 나갔다가 다시 들어오면 virtualenv 환경이 켜짐

4. django 프로젝트 생성

$ django-admin startproject mysite .
# 점 .은 현재 디렉토리에 장고를 설치하라고 스크립트에게 알려준다
  • setting.py 설정 수정
LANGUAGE_CODE = 'ko-kr'
TIME_ZONE = 'Asia/Seoul'
STATIC_ROOT = os.path.join(BASE_DIR, 'static')

5. django 프로젝트 app 생성

$ python manage.py startapp myapp
  • setting.py 에 생성한 app 등록
INSTALLED_APPS = [
    ...
    'myapp',
]

reference