codility 4-2. Perm Check

07 May 2017 | 알고리즘 프로그래밍

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given.
A permutation is a sequence containing each element from 1 to N once, and only once.
For example, array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2
is a permutation, but array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
is not a permutation, because value 2 is missing.
The goal is to check whether array A is a permutation.
Write a function:
def solution(A)

that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
For example, given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2
the function should return 1.
Given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
the function should return 0.
Assume that:

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

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage
(not counting the storage required for input arguments).

풀이코드

풀이코드 1

Detected time complexity: O(N) or O(N * log(N))

def solution(A):
    M = max(A)
    B = list(set(A))
    if len(B) == M and len(A) == len(B) and sum(range(M+1)) == sum(B):
        return 1
    return 0

풀이코드 2

Detected time complexity: O(N^2)
문제점 : A = [1000000000] 와 같은 인자가 주어지면, sum(range(max(A)+1)) 부분에서 많은 시간이 소요된다.

def solution(A):
    B = list(set(A))
    if len(A) == len(B) and sum(range(max(A)+1)) == sum(B):
        return 1
    return 0

풀이코드 3

Detected time complexity: O(N^2)

def solution(A):
    if len(A) == max(A):
        for idx, var in enumerate(A): # O(N)
            if var in A[idx+1:]: # O(N^2)
                return 0
        return 1
    return 0

다른사람 풀이

비트단위 연산을 활용하였다.
bitwise 연산자를 공부하자

def solution(A):
    N = len(A)

    xorSum = 0
    for i in range(1, N+1):
        xorSum ^= i ^ A[i-1]

    if xorSum == 0:
        return 1
    else:
        return 0

or 연산자 활용

def solution(A):
    if max(A) != len(A) or len(set(A)) != len(A):
        return 0
    return 1

Comment Read more

장고 모델 폼 (Model Form)

06 May 2017 | python Django form

AskDjango 수업을 듣고 중요한 내용을 정리하였습니다.

Model Form

form 클래스를 상속받은 클래스 (forms.ModelForm)
form 을 만들 때 model 클래스의 내역 그대로 form을 만든다면, (Model Form)
forms.py 에서 form 필드를 중복해서 정의할 필요가 없다
모델과 관련된 form 이라면 모델 폼을 사용하는 것이 좋다

Form vs Model Form (폼과 모델폼의 차이점)

Form (일반 폼) : 직접 필드 정의, 위젯 설정이 필요
Model Form (모델 폼) : 모델과 필드를 지정하면 모델폼이 자동으로 폼 필드를 생성

from django import forms
from .models import Post

# Form (일반 폼)
class PostForm(forms.Form):
	title = forms.CharField()
	content = forms.CharField(widget=forms.Textarea)

# Model Form (모델 폼)
class PostForm(forms.ModelForm):
	class Meta:
		model = Post
		fields = ['title', 'content'] # '__all__' 설정시 전체 필드 추가

ModelForm.save(commit=True)

Model Form 클래스에는 .save(self, commit=True) 메소드가 구현되 었음
DB 저장 여부를 commit flag를 통해서 결정
commit=False flag를 통해 함수 호출을 지연

# dojo/forms.py
from django import forms
from .models import Post


class PostForm(forms.ModelForm): # 모델 폼 정의
	class Meta:
		model = Post
		fields = ['title', 'content']

	''' 내부적으로 구현되어 있음 (멤버변수 인스턴스)
		향후 수정 기능 구현시 활용
	def save(self, commit=True):
		self.instance = Post(**self.cleaned_data)
		if commit:
			self.instance.save()
		return self.instance
	'''

사용예시

form.save(commit=False) 를 통해서 DB save 를 지연시켜 중복 save를 방지한다.

from django.shortcuts import render, redirect
from .models import Post
from .forms import PostForm

def post_new(request):
	if request.method == 'POST':
		form = PostForm(request.POST, request.FILES) # NOTE: 인자 순서주의 POST, FILES
		if form.is_valid():
			post = form.save(commit=False) # 중복 DB save를 방지
			post.ip = request.META['REMOTE_ADDR'] # ip 필드는 유저로 부터 입력 받지 않고 프로그램으로 채워 넣는다
			post.save()
			return redirect('/dojo/')
	else:
		form = PostForm()
	return render(request, 'dojo/post_form.html',{
		'form': form,
	})

ModelForm을 활용한 Model Instance 수정

수정 대상이 되는 model instance 를 Model Form 인스턴스 생성시에 instance 인자로서 지정한다

# myapp/views.py
def post_edit(request, id):
	post = get_object_or_404(Post, id=id)

	if request.method == 'POST':
		form = PostModelForm(request.POST, request.FILES, instance=post) # NOTE: instance 인자(수정대상) 지정
		if form.is_valid():
			post = form.save()
			return redirect(post) # NOTE: post 인스턴스의 get_absolute_url 메소드 호출!
	else:
		form = PostModelForm(instance=post)
	return render(request, 'myapp/post_form.html',{
		'form': form,
	})

(중요) .cleaned_data 을 끝까지 활용할 것!

cleaned_data

.is_valid() 를 통해서 검증에 통과한 값은 cleaned_data 변수명으로 사전타입 으로 제공된다.

def post_new(request):
	if request.method == 'POST':
		form = PostForm(request.POST, request.FILES) # NOTE: 인자 순서주의 POST, FILES
		if form.is_valid():
			print(form.cleaned_data) # {'title': '테스트', 'content': '내용'}
		# ... 생략 ...

request.POST[‘key’] 보다는 form.cleaned_data[‘key’] 와 같이 사용

request.POST 데이터는 form instance의 초기 데이터
따라서 form clean 함수 등을 통해 변경될 가능성이 있음

# myapp/forms.py
class CommentForm(forms.Form):
	def clean_message(self): # Form 클래스 내 clean 멤버함수를 통해 값 변경이 가능
		return self.cleaned_data.get('message', '').strip() # 좌우 공백 제거


# myapp/views.py
# BAD Case!! - request.POST를 통한 접근
form = CommentForm(request.POST)
if form.is_valid():
	# request.POST : 폼 인스턴스 초기 데이터
	message = request.POST['message']
	comment = Comment(message=message)
	comment.save()
	return redirect(post)

# GOOD Case!! - form.cleaned_data를 통한 접근
form = CommentForm(request.POST)
if form.is_valid():
	# form.cleaned_data : 폼 인스턴스 내에서 clean 함수를 통해 변환되었을 수도 있을 데이터
	message = form.cleaned_data['message']
	comment = Comment(message=message)
	comment.save()
	return redirect(post)

Comment Read more

장고 폼 (form)

06 May 2017 | python Django form

AskDjango 수업을 듣고 중요한 내용을 정리하였습니다.

form

장고의 가장 큰 Feature 중 하나
Model 클래스와 유사하게 Form 클래스를 정의

주요역할 (custom form class)

입력폼 html 생성 : as_table(), as_p(), as_ul() 기본 제공
입력폼 값 검증 (validation)
검증에 통과한 값을 사전타입으로 제공 (cleaned_data)

Form vs Model Form (폼과 모델폼의 차이점)

Form (일반 폼) : 직접 필드 정의, 위젯 설정이 필요
Model Form (모델 폼) : 모델과 필드를 지정하면 모델폼이 자동으로 폼 필드를 생성

from django import forms
from .models import Post

# Form (일반 폼)
class PostForm(forms.Form):
	title = forms.CharField()
	content = forms.CharField(widget=forms.Textarea)

# Model Form (모델 폼)
class PostForm(forms.ModelForm):
	class Meta:
		model = Post
		fields = ['title', 'content']

Form Fields

공식문서
Model Fields 와 유사
- Model Fields : DB Field 듣을 파이썬 클래스화
- Form Fields : HTML Form Field 들을 파이썬 클래스화

단계별 구현

django style

폼 처리 시에 같은 URL (같은 view) 에서 GET/POST로 나눠서 처리

def post_new(request):
	if request.method == 'POST':
		pass

	else:
		pass

GET 방식 request
- 입력폼을 보여준다
POST 방식 request
- 데이터를 입력 받아서 검증 (validation)
- 검증 성공 시 : 해당 데이터를 저장하고 success URL로 이동
- 검증 실패 시 : 오류 메시지와 함께 입력폼을 다시 보여준다

Step 0. Model class 정의

# myapp/models.py
from django.db import models
from django.urls import reverse

class Post(models.Model):
    title = models.CharField(max_length=100)
    content = models.TextField()
    created_at = models.DateTimeField(auto_now_add=True)
    updated_at = models.DateTimeField(auto_now=True)

	def get_absolute_url(self): # redirect시 활용
        return reverse('myapp:post_detail', args=[self.id])

Step 1. Form class 정의

# myapp/forms.py
from django import forms

class PostForm(forms.Form):
	title = forms.CharField()
	content = forms.CharField(widget=form.Textarea)

	# ModelForm.save 인터페이스를 흉내내어 구현
	def save(self, commit=True):
		post = Post(**self.cleaned_data)
		if commit:
			post.save()
		return post

Step 2. form 필드 별로 유효성 검사 함수 추가 적용

기본 유효성 검사는 값의 유무
form 에서는 리턴값을 따로 처리하지 않고, forms.ValidationError 예외발생 유무로 처리
validators 는 form 보다 Model 에 적용하는게 좋다.

# myapp/forms.py
from django import forms

def min_length_3_validator(value):
	if len(value) < 3:
		raise forms.ValidationError('3글자 이상 입력해주세요')


class PostForm(forms.Form):
	title = forms.CharField(validators=[min_length_3_validator]) # 한줄 문자입력창, 커스텀 validators 옵션 지정 가능

참고 (models.py)

model class 정의시에 validators 옵션 적용 가능
아래와 같이 model에 validators 를 정의하는 것을 권장 (Model Form에 그대로 적용 가능)
admin 사이트에서도 validator 동작 (admin도 Model Form을 생성하여 사용하기 때문)

from django import forms
from django.db import models


def min_length_3_validator(value):
	if len(value) < 3:
		raise forms.ValidationError('3글자 이상 입력해주세요')

class Post(models.Model):
	title = models.CharField(max_length=100, validators=[min_length_3_validator])

Step 3. view 함수 내에서 form 인스턴스 생성

# myapp/views.py
from django.shortcuts import render
from .forms import PostForm

def post_new(request):
	if request.method == 'POST':
		form = PostForm(request.POST, request.FILES) # NOTE: 인자 순서주의 POST, FILES
	else:
		form = PostForm()
	return render(request, 'dojo/post_form.html',{
		'form': form,
	})

Step 4. POST 요청에 한해 입력값 유효성 검증 및 저장처리

def post_new(request):
	if request.method == 'POST':
		form = PostForm(request.POST, request.FILES) # NOTE: 인자 순서주의 POST, FILES
		if form.is_valid(): # form의 모든 validators 호출 유효성 검증 수행
		# 검증에 성공한 값들은 사전타입으로 제공 (form.cleaned_data)
		# 검증에 실패시 form.error 에 오류 정보를 저장
		'''
		# 저장방법1) - 가장 일반적인 방법
		post = Post()
		post.title = form.cleaned_data['title']
		post.content = form.cleaned_data['content']
		post.save()

		# 저장방법2)
		post = Post(title = form.cleaned_data['title'],
					content = form.cleaned_data['content'])
		post.save()

		# 저장방법3)
		post = Post.objects.create(title = form.cleaned_data['title'],
									content = form.cleaned_data['content'])

		# 저장방법4)
		post = Post.objects.create(**form.cleaned_data) # unpack 을 통해 방법3과 같이 저장
		'''

		# 저장방법5)
		post = form.save() # PostForm 클래스에 정의된 save() 메소드 호출
		return redirect(post) # Model 클래스에 정의된 get_absolute_url() 메소드 호출
	else:
		form = PostForm()
		return render(request, 'dojo/post_form.html',{
		'form': form, 	# 검증에 실패시 form.error 에 오류 정보를 저장하여 함께 렌더링
		})

Step 5. 템플릿을 통해 HTML 폼 생성

GET 요청, POST 요청이지만 유효성 검증에 실패시, form 인스턴스를 통해 html 폼 출력
오류메시지가 있다면 함께 출력

<form action="" method="post">
	{% csrf_token %}
	<table>
		{{ form.as_table }}
	</table>
	<input type="submit">
</form>

Comment Read more

codility 3-3. TapeEquilibrium

05 May 2017 | 알고리즘 프로그래밍

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given.
Array A represents numbers on a tape.
Any integer P, such that 0 < P < N,
splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
In other words, it is the absolute difference between
the sum of the first part and the sum of the second part.

For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7

Write a function: def solution(A)
that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
For example, given:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

the function should return 1, as explained above.

Assume that:
N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).

풀이코드

Detected time complexity: O(N * N)
list slice 후, sum() 을 통해서 합계를 구하는 부분이 O(N^2)의 시간 복잡도를 가진다.

def solution(A):
    li = []
    for P in range(1,len(A)):
        sum1 = sum(A[:P]) # O(N^2)
        sum2 = sum(A[P:])
        diff = sum1 - sum2 if sum1 >= sum2 else sum2 - sum1
        li.append(diff)
    return min(li)

다른사람 풀이

Detected time complexity: O(N)
abs() 내장 함수를 통해서 숫자의 절대값을 구할 수 있다. abs(-3) » 3, abs(1,2) » 1.2
list slice를 사용하지 않는다.
min_difference 변수에 None을 담아서 시작한다.

def solution(A):
    sum_of_part_one = 0
    sum_of_part_two = sum(A)
    min_difference = None

    for i in range(1, len(A)):
        sum_of_part_one += A[i-1]
        sum_of_part_two -= A[i-1]
        difference = abs(sum_of_part_one - sum_of_part_two)

        if min_difference == None:
            min_difference = difference
        else:
            min_difference = min(min_difference, difference)

    return min_difference

Comment Read more

URL Reverse, 아는 사람은 꼭 쓴다는 get_absolute_url()

05 May 2017 | python Django url

AskDjango 수업을 듣고 중요한 내용을 정리하였습니다.

장고는 urls.py 변경을 통해 ‘각 뷰에 대한’ url이 변경되는 유연한 시스템을 갖고 있다.
url이 변경 되더라도 url reverse가 변경된 url을 추적한다. (누락의 위험이 적다)

URL Reverse를 수행하는 4가지 함수

reverse()

리턴형식 : string

from django.core.urlresolvers import reverse

reverse('blog:post_list') # '/blog/'
reverse('blog:post_detail', args=[10]) # '/blog/10/' args 인자로 리스트 지정 필요
reverse('blog:post_detail', kwargs={'id':10}) # '/blog/10/'
reverse('/hello/') # NoReverseMatch 오류 발생

resolve_url()

리턴형식 : string
내부적으로 reverse() 사용
reverse() 보다 사용이 간단하다.

from django.shortcuts import resolve_url

resolve_url('blog:post_list') # '/blog/'
resolve_url('blog:post_detail', 10) # '/blog/10/'
resolve_url('blog:post_detail', id=10) # '/blog/10/'
resolve_url('/hello/') # '/hello/' 문자열 그대로 리턴

redirect()

리턴형식 : HttpResponseRedirect
내부적으로 resolve_url() 사용
view 함수 내에서 특정 url로 이동 하고자 할 때 사용 (Http Response)

from django.shortcuts import redirect

redirect('blog:post_detail', 10)
# <HttpResponseRedirect status_code=302, "text/html; charset=utf-8", url="/blog/10/">

url template tag

내부적으로 reverse() 사용

<li><a href="{% url 'blog:post_detail' post.id %}">{{ post.title }}</a> </li>

모델 클래스 내 get_absolute_url 멤버함수

사용 강추!

특정 모델에 대한 Detail뷰를 작성할 경우, Detail뷰에 대한 URLConf설정을 하자마자,
필히 get_absolute_url설정을 해주세요. 코드가 보다 간결해집니다

어떠한 모델에 대해서 detail 뷰를 만들게 되면 get_absolute_url() 멤버 함수를 무조건 선언
resolve_url(모델 인스턴스), redirect(모델 인스턴스) 를 통해서 모델 인스턴스의 get_absolute_url() 함수를 자동으로 호출
resolve_url() 함수는 가장 먼저 get_absolute_url 함수의 존재 여부를 체크하고, 존재하면 호출하며 그 리턴값으로 URL을 사용

get_absolute_url 작성

class Post(models.Model):
    # ... (중략)
    def get_absolute_url(self):
        return reverse('blog:post_detail', args=[self.id])

get absolute url 활용

2, 3, 1 의 순서대로 많이 사용
처음부터 get_absolute_url 을 적극적으로 사용하는 연습을 하는 것이 좋음

1. url template tag로 활용

<li><a href="{{ post.get_absolute_url }}">{{ post.title }}</a> </li>

2. resolve_url, redirect를 통한 활용

from django.shortcuts import resolve_url
from django.shortcuts import redirect

resolve_url('blog:post_detail', post.id) # '/blog/105/'
resolve_url(post) # '/blog/105/' 인자의 인스턴스 메소드로 get_absolute_url 있는지 체크해서 리턴

print(redirect('blog:post_detail', post.id))
print(redirect(post))
# <HttpResponseRedirect status_code=302, "text/html; charset=utf-8", url="/blog/105/">

3. CBV 에서의 활용

CreateView, UpdateView에 success_url을 제공하지 않는 경우, 해당 model instance의 get_absolute_url 주소로 이동이 가능한지 체크
생성, 수정 뒤에 Detail 화면으로 가는 것은 일반적

Comment Read more

Older Newer

초보몽키의 개발공부로그

codility 4-2. Perm Check

문제

풀이코드

풀이코드 1

풀이코드 2

풀이코드 3

다른사람 풀이

장고 모델 폼 (Model Form)

Model Form

Form vs Model Form (폼과 모델폼의 차이점)

ModelForm.save(commit=True)

사용예시

ModelForm을 활용한 Model Instance 수정

(중요) .cleaned_data 을 끝까지 활용할 것!

cleaned_data

request.POST[‘key’] 보다는 form.cleaned_data[‘key’] 와 같이 사용

장고 폼 (form)

form

주요역할 (custom form class)

Form vs Model Form (폼과 모델폼의 차이점)

Form Fields

단계별 구현

django style

Step 0. Model class 정의

Step 1. Form class 정의

Step 2. form 필드 별로 유효성 검사 함수 추가 적용

참고 (models.py)

Step 3. view 함수 내에서 form 인스턴스 생성

Step 4. POST 요청에 한해 입력값 유효성 검증 및 저장처리

Step 5. 템플릿을 통해 HTML 폼 생성

codility 3-3. TapeEquilibrium

문제

풀이코드

다른사람 풀이

URL Reverse, 아는 사람은 꼭 쓴다는 get_absolute_url()

URL Reverse를 수행하는 4가지 함수

reverse()

resolve_url()

redirect()

url template tag

모델 클래스 내 get_absolute_url 멤버함수

get_absolute_url 작성

get absolute url 활용

1. url template tag로 활용

2. resolve_url, redirect를 통한 활용

3. CBV 에서의 활용