AttackOnNunu

Once more into the fray


  • 홈

  • About

  • 태그

  • 카테고리

  • 아카이브

  • 검색

(PYTHON) Day - 16 Collections(1)

작성일 2020-03-06 In LANGUAGE 🚀 , PYTHON , HACKERRANK 댓글:

Reference

  • 문제 출처 - HackerRank
  • 파이썬 연습 - Practice - Python

개인적인 생각과 상상으로 작성한 내용들이 포함되어 있습니다
문제를 풀고 Discussion Tab을 참고하며 코드 스타일을 개선하려고 노력하고자 합니다


HackerRank

HackerRank의 Python 연습문제들은 아래와 같은 카테고리로 분류 된다

Subdomain

- ~~Introduction~~
- ~~Basic Data Types~~
- ~~Strings~~
- ~~Sets~~
- ~~Math~~
- ~~Itertools~~
- <strong style="color:blue">Collections</strong>
- Date and Time
- Errors and Exceptions
- Classes
- Built-Ins
- Python Functionals
- Regex and Parsing
- XML
- Closures and Decorators
- Numpy
- Debugging

Collections

기본개념

Collections Module
Collections 모듈은 dict, list, set, tuple과 같은 파이썬의 기본 내장 컨테이너들을 확장한 특수 컨테이너들을 가진다.

namedtuple()named fields를 가지는 서브클래스 튜플을 만드는 factory 함수
deque양끝에서 빠르게 append(추가)와 pop(삭제) 할 수 있는 list-like 컨테이너
ChainMap여러 매핑의 단일 뷰를 만드는 dict-like 클래스
Counter해시 가능한 객체의 요소 개수를 세는 데 사용하는 dict 서브클래스
OrderedDict항목이 추가된 순서를 기억하는 dict 서브클래스
defaultdict결측값에 기본 값을 자동으로 지정해주는 dict 서브클래스
UserDict더 쉬운 dict 서브 클래싱을 위해 dict 객체를 감싸는 wrapper
UserList더 쉬운 list 서브 클래싱을 위해 list 객체를 감싸는 wrapper
UserString더 쉬운 string 서브 클래싱을 위해 string 객체를 감싸는 wrapper

namedtuple()

tuple의 immutable한 성질을 띄면서 Dictionary Key로 접근할 수 있는 장점들을 가지고 있다.


> > > # 기본 예
> > >
> > > Point = namedtuple('Point', ['x', 'y'])
> > > p = Point(11, y=22) # 위치와 키워드 인자로 인스턴스를 만듭니다
> > > p[0] + p[1] # 일반 튜플 (11, 22) 처럼 인덱싱할 수 있습니다
> > > 33
> > > x, y = p # 일반 튜플처럼 언팩합니다
> > > x, y
> > > (11, 22)
> > > p.x + p.y # 필드는 이름으로도 액세스할 수 있습니다
> > > 33
> > > p # name=value 스타일의 가독성 있는 **repr**
> > > Point(x=11, y=22)
  • tuple, namedtuple, dict 비교

# runtime.py written in PyCharm

from time import time
from math import sqrt

# 일반적인 튜플 사용

pt1 = (1.0, 5.0)
pt2 = (2.5, 1.5)

start1= time()
line_leng1 = sqrt((pt2[0] - pt1[0]) ** 2 + (pt2[1] - pt1[1]) ** 2)
end1 = time()
print('tuple: '.rjust(15), round((end1-start1)\* 10\*\*3, 6))

###################################################################

# 네임드 튜플 사용

from collections import namedtuple

Point = namedtuple('Point', 'x y')
pnt1 = Point(1.0, 5.0)
pnt2 = Point(2.5, 1.5)

start2= time()
line_leng2 = sqrt((pnt2.x - pnt1.x) ** 2 + (pnt2.y - pnt1.y) ** 2)
end2 = time()
print('namedTuple: '.rjust(15), round((end2-start2)\* 10\*\*3, 6))

###################################################################

# 딕셔너리 사용

pdt1 = {'x': 1.0, 'y': 5.0}
pdt2 = {'x': 2.5, 'y': 1.5}

start3= time()
line_leng3 = sqrt((pdt2['x'] - pdt1['x']) ** 2 + (pdt2['y'] - pdt1['y']) ** 2)
end3 = time()
print('dict: '.rjust(15), round((end3-start3)\* 10\*\*3, 6))
tuple: 0.068188
namedTuple: 0.010014
dict: 0.004053

deque()

double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미한다.
더하기 : 추가(append, appendleft), 확장(extend, extendleft), 삽입(insert)
빼기 : 비우기(clear), 제거(remove), 반환 및 제거(pop)
조작 : 뒤집기(reverse), 회전(rotate), 복사(copy)
확인 : 요소 수(count), 위치(index), 최대크기(maxlen)


# runtime.py written in PyCharm

from collections import deque

deq = deque(['a', 'b', 'c'])

deq.append('d')
print('append -> d: ', deq)
deq.appendleft('z')
print('append <- z: ', deq)
deq.extend('ef')
print('extend -> ef: ', deq) # list의 extend 결과와 조금 다른 것을 주의!!
deq.extendleft('xy')
print('extend <- xy: ', deq)

deql = deq.copy()

print('deque.pop() ->', end=' ')
while True:
try:
print(deq.pop(), end=' ')
except IndexError:
break

print()
print('deque.popleft() <-', end=' ')
while True:
try:
print(deql.popleft(), end=' ')
except IndexError:
break
append -> d: deque(['a', 'b', 'c', 'd'])
append <- z: deque(['z', 'a', 'b', 'c', 'd'])
extend -> ef: deque(['z', 'a', 'b', 'c', 'd', 'e', 'f'])
extend <- xy: deque(['y', 'x', 'z', 'a', 'b', 'c', 'd', 'e', 'f'])
deque.pop() -> f e d c b a z x y
deque.popleft() <- y x z a b c d e f

ChainMap()

파이썬 3.3v 부터 기능을 지원한다.
사실 기본 내장함수에서 dict.update() 를 통해 Chain of Dictionaries를 구현할 수 있기에 굳이 사용하지 않는 함수이다.
하지만 ChainMap() 함수를 사용함으로 코드 작성의 편의성과 가독성이 높아지는 장점을 무시 할 수는 없다.

a chain of mappings


# runtime.py written in PyCharm

from collections import ChainMap
from time import time

# ChainMap 사용

start = time()
toys = {'Blocks': 30, 'Monopoly': 20}
computers = {'iMac': 1000, 'Chromebook': 800, 'PC': 400}
clothing = {'Jeans': 40, 'T-Shirt': 10}
inventory_chain = ChainMap(toys, computers, clothing)
end = time()
run = end - start

print(round(run \* 10\*\*2, 5))
##########################################################

# dict.update() 사용

start1 = time()
inventory = dict()
inventory.update(toys)
inventory.update(computers)
inventory.update(clothing)
end1 = time()
run1 = end1 - start1

print(round(run1 \* 10\*\*2, 5))
##########################################################

# 내용 확인

print(inventory_chain if inventory_chain == inventory else 'Not same!')
0.00088
0.00062
ChainMap({'Blocks': 30, 'Monopoly': 20}, {'iMac': 1000, 'Chromebook': 800, 'PC': 400}, {'Jeans': 40, 'T-Shirt': 10})

Counter()

빈도수를 확인할 때 많이 사용된다


> > > # 목록에 있는 단어의 빈도를 집계
> > >
> > > cnt = Counter()
> > > for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
> > > ... cnt[word] += 1
> > > cnt
> > > Counter({'blue': 3, 'red': 2, 'green': 1})

> > > # 햄릿에서 가장 흔한 단어를 찾음
> > >
> > > import re
> > > words = re.findall(r'\w+', open('hamlet.txt').read().lower())
> > > Counter(words).most_common(10)
> > > [('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631),
> > > ('you', 554), ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)]
> > >

OrderedDict()

딕셔너리 순서를 재배치하는데 사용된다.
popitem(last=True) : last가 참이면 LIFO 순서로, 거짓이면 FIFO 순서로 (key, value) 값을 반환한다
move_to_end(key, last=True) : key를 last가 참이면 오른쪽 끝으로, 거짓이면 왼쪽 끝으로 보낸다


> > > d.move_to_end('b')
> > > ''.join(d.keys())
> > > 'acdeb'
> > > d.move_to_end('b', last=False)
> > > ''.join(d.keys())
> > > 'bacde'
> > >


(PYTHON) Day - 15 Itertools(2)

작성일 2020-03-06 In LANGUAGE 🚀 , PYTHON , HACKERRANK 댓글:

Reference

  • 문제 출처 - HackerRank
  • 파이썬 연습 - Practice - Python

개인적인 생각과 상상으로 작성한 내용들이 포함되어 있습니다
문제를 풀고 Discussion Tab을 참고하며 코드 스타일을 개선하려고 노력하고자 합니다


HackerRank

HackerRank의 Python 연습문제들은 아래와 같은 카테고리로 분류 된다

Subdomain

- ~~Introduction~~
- ~~Basic Data Types~~
- ~~Strings~~
- ~~Sets~~
- ~~Math~~
- <strong style="color:blue">Itertools</strong>
- Collections
- Date and Time
- Errors and Exceptions
- Classes
- Built-Ins
- Python Functionals
- Regex and Parsing
- XML
- Closures and Decorators
- Numpy
- Debugging

Itertools

Problem

  • itertools.product()
  • itertools.permutations()
  • itertools.combinations()
  • itertools.combinations_with_replacement()
  • Compress the String!
  • Iterables and Iterators
  • Maximize It!

itertools.product()


문제 : A, B의 곱집합을 구하는 문제
입력 : A의 원소들; B의 원소들;
출력 : product(A, B)


> > > # Sample code
> > >
> > > from itertools import product
> > >
> > > print list(product([1,2,3],repeat = 2))
> > > [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
> > >
> > > print list(product([1,2,3],[3,4]))
> > > [(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)]
> > >
> > > A = [[1,2,3],[3,4,5]]
> > > print list(product(\*A))
> > > [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5)]
> > >
> > > B = [[1,2,3],[3,4,5],[7,8]]
> > > print list(product(\*B))
> > > [(1, 3, 7), (1, 3, 8), (1, 4, 7), (1, 4, 8), (1, 5, 7), (1, 5, 8), (2, 3, 7), (2, 3, 8), (2, 4, 7), (2, 4, 8), (2, 5, 7), (2, 5, 8), (3, 3, 7), (3, 3, 8), (3, 4, 7), (3, 4, 8), (3, 5, 7), (3, 5, 8)]
> > >
  • INPUT
  • OUTPUT

1 2
3 4

(1, 3) (1, 4) (2, 3) (2, 4)

from itertools import product

A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]

print(\*product(A, B))

itertools.permutations()


문제 : 문자열 S가 주어졌을 때 k의 크기로 뽑을 수 있는 순열(permutation)을 사전순(lexicographic order)으로 출력하는 문제
입력 : S, k; (문자열은 모두 대문자)
출력 : S로 만들 수 있는 순열을 한줄씩 출력


> > > # Sample code
> > >
> > > from itertools import permutations
> > > print permutations(['1','2','3'])
> > > <itertools.permutations object at 0x02A45210>
> > >
> > > print list(permutations(['1','2','3']))
> > > [('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]
> > >
> > > print list(permutations(['1','2','3'],2))
> > > [('1', '2'), ('1', '3'), ('2', '1'), ('2', '3'), ('3', '1'), ('3', '2')]
> > >
> > > print list(permutations('abc',3))
> > > [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
> > >
  • INPUT
  • OUTPUT

HACK 2

AC
AH
AK
CA
CH
CK
HA
HC
HK
KA
KC
KH

from itertools import permutations

S, k = input().split()
print(\*[''.join(p) for p in permutations(sorted(S), int(k))], sep='\n')

itertools.combinations()


문제 : 문자열 S가 주어졌을 때 k의 크기로 뽑을 수 있는 조합(combination)을 사전순으로 출력하는 문제
입력 : S, k; (문자열은 모두 대문자)
출력 : S로 만들 수 있는 서로 다른 조합을 한줄씩 출력


> > > # Sample code
> > >
> > > from itertools import combinations
> > >
> > > print list(combinations('12345',2))
> > > [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]
> > >
> > > A = [1,1,3,3,3]
> > > print list(combinations(A,4))
> > > [(1, 1, 3, 3), (1, 1, 3, 3), (1, 1, 3, 3), (1, 3, 3, 3), (1, 3, 3, 3)]
> > >
  • INPUT
  • OUTPUT

HACK 2

A
C
H
K
AC
AH
AK
CH
CK
HK

from itertools import combinations

S, k = input().split()
print(\*[''.join(c) for i in range(1, int(k)+1) for c in combinations(sorted(S), i)], sep='\n')

itertools.combinations_with_replacement()


문제 : 문자열 S가 주어졌을 때 k의 크기로 뽑을 수 있는 중복조합(combinations with replacement)을 사전순으로 출력하는 문제
입력 : S, k; (문자열은 모두 대문자)
출력 : S로 만들 수 있는 중복조합을 한줄씩 출력


> > > # Sample code
> > >
> > > from itertools import combinations_with_replacement
> > >
> > > print list(combinations_with_replacement('12345',2))
> > > [('1', '1'), ('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '2'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '3'), ('3', '4'), ('3', '5'), ('4', '4'), ('4', '5'), ('5', '5')]
> > >
> > > A = [1,1,3,3,3]
> > > print list(combinations(A,2))
> > > [(1, 1), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (3, 3), (3, 3), (3, 3)]
> > >
  • INPUT
  • OUTPUT

HACK 2

AA
AC
AH
AK
CC
CH
CK
HH
HK
KK

from itertools import combinations_with_replacement

S, k = input().split()

print(\*[''.join(c)for c in combinations_with_replacement(sorted(S), int(k))], sep='\n')

Compress the String!


문제 : 문자열 S가 주어졌을 때 같은 문자끼리 그룹으로 묶어서 압축된 표현을 출력하는 문제
입력 : 문자열 S (숫자 0에서 9까지로 구성됨)
출력 : 문자를 c로 연속으로 출현한 횟수를 X라고 했을 때 (X, c)로 표현

  • INPUT
  • OUTPUT

1222311

(1, 1) (3, 2) (1, 3) (2, 1)

파이썬의 goupby() 함수는 SQL의 개념과 조금 달라서 주의해야겠다.
만약 SQL의 그룹방식을 구현하고 싶다면 함수를 사용하기 전 정렬을 시켜주면 된다.

from itertools import groupby

S = input()
print(\*[(len(list(grp)), int(key)) for key, grp in groupby(S)])

Iterables and Iterators


문제 : N개의 영문자 중에서 K개로 만들 수 있는 조합들 중에 ‘a’를 포함하는 조합을 확률로 출력하는 문제
입력 : 문자수 N; (N개의) 문자들; 조합 크기 K;
출력 : 확률을 소수점 3번째 자리까지 표현

  • INPUT
  • OUTPUT

4
a a c d
2

0.8333

combinations() 함수를 사용하여 전체 경우의 수를 구하고 문자 ‘a’가 있는 조합의 수를 구함
list()와 []의 차이점을 주의 - difference btw list() and []

import itertools as it

N, letters, K = input(), input().split(), int(input())

c_letters = list(it.combinations(letters, K))
contain = [c for c in c_letters if 'a' in c]

print('{:.4f}'.format(len(contain)/len(c_letters)))

math 모듈을 사용해서 직접 수학적인 계산을 사용한 경우도 있음

from math import factorial

def C(n, k):
if n < k:
return 0
return factorial(n) // factorial(n-k)

N = int(input())
n_a = input().split().count('a')
K = int(input())

print('%.4f' % (1 - C(N - n_a, K) / C(N, K)))

수행시간을 비교해보면 그 차이가 매우 사소하기 때문에 combinations() 함수를 사용하는게 직관적으로 보기 좋은 것 같음

import itertools as it
from math import factorial
from timeit import timeit

def C(n, k):
if n < k:
return 0
return factorial(n) // factorial(n-k)

N, letters, K = int(input()), input().split(), int(input())

n_a = letters.count('a')

c_letters = list(it.combinations(letters, K))
contain = [c for c in c_letters if 'a' in c]

print(timeit('{:.4f}'.format(len(contain)/len(c_letters)))) # 0.01438812300000003
print(timeit('{:.4f}'.format(1 - C(N - n_a, K) / C(N, K)))) # 0.011570051000000081

Maximize It!


문제 : f(x) = x^2 이고, S = (f(x1) + f(x2) + …) % M 일 때, 가장 큰 S를 구하는 문제
입력 : K, M; (K번 반복) 리스트의 크기, 숫자들…;
출력(예제) : 각 리스트에서 5, 9, 10을 뽑은 경우 (5^2 + 9^2 + 10^2)%1000 = 206으로 가장 크다

  • INPUT
  • OUTPUT

3 1000
2 5 4
3 7 8 9
5 5 7 8 9 10

206

처음에 문제를 잘못 이해하고 각 리스트에서 가장 큰 수를 뽑아서 S를 구하는 문제인줄 알았다…

K, M = map(int, input().split())
N = [[int(num) for num in input().split()[1:]] for \_ in range(K)]
max_N = list(map(lambda x: max(x)\*\*2, N))

print(sum(max_N) % M)

각 리스트를 곱하여(product) 모든 조합을 만들고, 람다식을 이용해 각 조합의 S를 계산하여 최대값을 구한다.

from itertools import product

K, M = map(int, input().split())
N = [[int(num) for num in input().split()[1:]] for \_ in range(K)]
max_S = max(list(map(lambda x: sum(i\**2 for i in x) % M, product(*N))))

print(max_S)


(PYTHON) Day - 14 Itertools(1)

작성일 2020-03-04 In LANGUAGE 🚀 , PYTHON , HACKERRANK 댓글:

Reference

  • 문제 출처 - HackerRank
  • 파이썬 연습 - Practice - Python

개인적인 생각과 상상으로 작성한 내용들이 포함되어 있습니다
문제를 풀고 Discussion Tab을 참고하며 코드 스타일을 개선하려고 노력하고자 합니다


HackerRank

HackerRank의 Python 연습문제들은 아래와 같은 카테고리로 분류 된다

Subdomain

- ~~Introduction~~
- ~~Basic Data Types~~
- ~~Strings~~
- ~~Sets~~
- ~~Math~~
- <strong style="color:blue">Itertools</strong>
- Collections
- Date and Time
- Errors and Exceptions
- Classes
- Built-Ins
- Python Functionals
- Regex and Parsing
- XML
- Closures and Decorators
- Numpy
- Debugging

Itertools

기본 개념

Itertools
itertools 모듈을 사용하면 빠르고 효율적으로 메모리를 사용하는 반복자를 사용할 수 있다.
모듈의 함수들은 다음과 같이 크게 3가지 용도로 구분할 수 있다.

Infinite Iterators
무한으로 반복할수 있는 함수로 3가지가 있다.

IteratorArgumentsResultsExample
count()start, [step]start, start+step, start+2*step, …count(10) –> 10 11 12 13 14 …
cycle()pp0, p1, … plast, p0, p1, …cycle(‘ABCD’) –> A B C D A B C D …
repeat()elem [,n]elem, elem, elem, … endlessly or up to n timesrepeat(10, 3) –> 10 10 10

Iterators that Terminate
itertools 모듈 대부분의 비중을 차지하는 이 12개의 함수들은 유한번 반복하는 함수들이다.

IteratorArgumentsResultsExample
accumulate()p [,func]p0, p0+p1, p0+p1+p2, …accumulate([1,2,3,4,5]) –> 1 3 6 10 15
chain()p, q, …p0, p1, … plast, q0, q1, …chain(‘ABC’, ‘DEF’) –> A B C D E F
chain.from_iterable()iterablep0, p1, … plast, q0, q1, …chain.from_iterable([‘ABC’, ‘DEF’]) –> A B C D E F
compress()data, selectors(d[0] if s[0]), (d[1] if s[1]), …compress(‘ABCDEF’, [1,0,1,0,1,1]) –> A C E F
dropwhile()pred, seqseq[n], seq[n+1], starting when pred failsdropwhile(lambda x: x<5, [1,4,6,4,1]) –> 6 4 1
filterfalse()pred, seqelements of seq where pred(elem) is falsefilterfalse(lambda x: x%2, range(10)) –> 0 2 4 6 8
groupby()iterable[, key]sub-iterators grouped by value of key(v)
islice()seq, [start,] stop [, step]elements from seq[start:stop:step]islice(‘ABCDEFG’, 2, None) –> C D E F G
starmap()func, seqfunc(seq[0]), func(seq[1]), …starmap(pow, [(2,5), (3,2), (10,3)]) –> 32 9 1000
takewhile()pred, seqseq[0], seq[1], until pred failstakewhile(lambda x: x<5, [1,4,6,4,1]) –> 1 4
tee()it, nit1, it2, … itn splits one iterator into n
zip_longest()p, q, …(p[0], q[0]), (p[1], q[1]), …zip_longest(‘ABCD’, ‘xy’, fillvalue=’-‘) –> Ax By C- D-

Combinatoric Generators
데이터들의 순열과 조합(combination & permutation)을 만드는 함수로 4가지가 있다.

| Iterator | Arguments | Results | Example |
| ——————————- | —————— | ————————————————————- | ———————————————– | —————————————- |
| product() | p, q, … [repeat=1] | cartesian product, equivalent to a nested for-loop | AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD | product(‘ABCD’, repeat=2) |
| permutations() | p[, r] | r-length tuples, all possible orderings, no repeated elements | AB AC AD BA BC BD CA CB CD DA DB DC | permutations(‘ABCD’, 2) |
| combinations() | p, r | r-length tuples, in sorted order, no repeated elements | AB AC AD BC BD CD | combinations(‘ABCD’, 2) |
| combinations_with_replacement() | p, r | r-length tuples, in sorted order, with repeated elements | AA AB AC AD BB BC BD CC CD DD | combinations_with_replacement(‘ABCD’, 2) |


자세한 학습 (참고)

The itertools Module



1…8910…33
NUNU

NUNU

개인적으로 공부하면서 정리한 내용들을 블로그에 남기고 있습니다.
99 포스트
18 카테고리
53 태그
RSS
Creative Commons
© 2021 NUNU
Powered by Hexo v3.9.0
|
Theme – NexT.Mist v7.2.0