python

문제 https://www.acmicpc.net/problem/9372 문제 풀이 import collections import sys T = int(sys.stdin.readline()) def bfs(graph, i, visited, count): # visited[i] = 1 queue = collections.deque([i]) while queue: node = queue.popleft() if visited[node] == 0: visited[node] = 1 count += 1 queue.extend(graph[node]) return count for _ in range(T): N, M = map(int, sys.stdin.readline().split()) graph = [[] for _..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 풀이 import collections import sys M, N, H = map(int, sys.stdin.readline().split()) tomato = [[] for _ in range(H)] queue = collections.deque([]) for h in range(H): for y in range(N): temp = list(map(int, s..

slots 기본적으로 파이썬에서는 객체의 인스턴스 속성을 저장하기 위해서 dict 를 사용 하는데 이를 통해 런타임 중 속성을 변경할 수 있다. 하지만 dict 는 메모리를 낭비하는 경향이 있다. slots를 사용하는 경우 두가지 효과가 있다. 속성에 대한 빠른 접근 class Normal(object): pass class UsingSlots(object): __slots__ = ['name'] normal = Normal() use_slots = UsingSlots() def fn_set_get_delete(cls): def set_get_delete(): setattr(cls, 'name', 'foo var') getattr(cls, 'name&#3..

파이썬 Magic Method https://docs.python.org/ko/3.7/reference/datamodel.html#special-method-names new 인스턴스 생성시 호출되며 Static method 이다. 일반적인 구현은 super().new(cls) 로 인스턴스 생성후 Return 전에 필요한 작업을 함 만약 인스턴스를 Return 하지 않는다면 init 은 호출되지 않는다. class Sample(object): def __new__(cls, *args, **kwargs): print('new', args, kwargs) this = super().__new__(cls) cls.args = args cls.kwargs = kwargs return this def __init..

multiprocessing 파이썬은 기본적으로 여러 CPU를 사용하지 않는다. 단일 코어 시대에 설계 되었고 병렬 처리를 효율적으로 실행하기가 어렵기도 하다. 로직을 병렬화하면 N배의 속도를 기대하지만 실제로는 프로세스간 통신 비용이 발생 등 N배 만큼에 성능 향상이 이루어지지는 않는다. 또는 어떻게 설계하냐에 따라서 오히려 더 느려지는 경우도 있기 때문에 설계를 잘 해야한다. multiprocessing 모듈은 프로세스와 스레드 기반의 병렬 처리를 사용해 작업 대기열을 분산시키고 프로세스 간에 데이터를 공유할 수 있도록 한다. 작업을 병렬화 하려면 순차적으로 작성하는 방식과는 달리 다른 관점으로 작성을 해야하며 일반적으로 디버깅이 어렵다. 따라서 성능도 중요하지만 유지보수 측면에서 단순하게 작성을 해..

비동기 I/O 개발 업무를 하면서 실제 코드 자체보다는 코드에 필요한 데이터를 얻어오는 작업이 병목이 생기는 것을 많이 겪었을 것이다. 이런경우 프로그램 I/O 위주라 하고 I/O 효율이 속도를 제한 한다는 것을 의미한다. I/O는 프로그램 흐름에 큰 영향을 미친다. 파일이나 네트워크 소켓 연결을 통해 데이터를 읽을 때까지 실행을 멈추고 커널에 연산을 요청한 후 끝날때 까지 기다려야 하기 때문이다. 비동기 I/O를 활용하면 I/O 연산을 기다리는 동안 다른 연산을 수행하여 유휴 시간을 활용할 수 있다. 작업1,2,3 을 순차적으로 실행한다면 지연을 세번 감수해야 하지만 세 작업을 동시에 실행한다면 시간을 감소할 수 있을 것이다. 파이썬에서는 제너레이터 기반의 Coroutine과 async 함수로 Nati..

사전(dict)과 셋(set) dict와 set은 미리 정해진 순서로 정렬 되지 않는다. dict와 set의 차이점은 set은 key만 가지고 있다는 것이다. 리스트와 튜플은 경우에 따라 검색을 O(logN) 시간 복잡도로 구현할 수 있다. 반면, dict와 set은 O(1)이다. dict와 set은 보통 많은 메모리를 사용한다. 또 해시 함수에 의존 함으로 해시 함수가 느리다면 연산속도도 느릴 것이다. 리스트와 사전 검색 성능 차이 리스트 or 튜플로 구현시 O(N) dict로 구현시 O(1) phonebook_list = [ ("홍길동", "010-1111-1111"), ("김철수", "010-1111-1234"), ("국영수", "010-1234-1234"), ] def find_phonebook_..

튜플 튜플은 한번 생성되면 내용이나 크기를 변경할 수 없지만 두 튜플을 합칠 수는 있다. >>> t1 = (1,2,3) >>> t2 = (4,5,6) >>> t1 + t2 # (1,2,3,4,5,6) 튜플은 합치면 항상 메모리에 새로운 튜플을 새로 할당 한다. 또 튜플은 여유공간을 할당하지 않기 때문에 자원을 더 적게 사용한다. l = [i for i in range(100000)] t = tuple(l) print('list', sys.getsizeof(l)) print('tuple', sys.getsizeof(t)) list 824464 tuple 800048이 때문에 정적인 데이터를 다룰때는 리스트보다는 튜플이 좋다. 또한 튜플은 정적이기에 리소스 캐싱을 하는데 크기가 ..

리스트 리스트는 동적 배열로 크기를 자유자재로 조절할 수 있는데 이러한 변경 가능한 특성 때문에 리스트는 메모리와 추가 연산을 필요로 한다. 리스트에 object 추가 시 기존에 object들과 추가되는 object를 새로운 리스트를 추가하여 생성한다. 새로 추가된 리스트의 크기는 기존 N개와 추가되는 1개 더하여 N+1이 아니라 M개 (M > N+1) 의 크기를 가진다. 크기에 여유를 두는 이유는 메모리 할당과 복사 요청 횟수를 줄이기 위하여다. 리스트의 크기 1을 할당한 이후 크기는 동일하다가 5를 할당하니 크기가 커진다. 이는 새로 리스트를 생성한 것. a = [] print('0', sys.getsizeof(a)) a.append(1) print('1', sys.getsizeof(a)) a.app..

프로파일링으로 병목지점 찾기 cProfile 감으로 코드를 작성하는 습관을 버리고 가설을 세우고 프로파일링을 통한 검증으로 코드를 작성해라. 이는 시간을 투자 할만한 가치가 충분하고 코드 작성의 근거가 될 수 있다. cProfile 테스트 테스트 코드 피보나치 수열을 dp와 recursion 으로 구현한 함수 def fibonacci_dp(n): dp = [0, 1] for i in range(2, n + 1): dp.append(dp[i - 1] + dp[i - 2]) return dp[n] def fibonacci_recursion(n): if n python -m cProfile -s cumulative High-Performance-Python\2-프로파일링으로-병목지점-찾기\2-1-cProfil..

이해하기 어느 search 가 빠르고 느린지 확인 하는 방법 import csv def search_fast(haystack, needle): for item in haystack: if item == needle: return True return False def search_slow(haystack, needle): is_exist = False for item in haystack: if item == needle: is_exist = True return is_exist def search_unknown_1(haystack, needle): return any((item == needle for item in haystack)) def search_unknown_2(haystack, needle..

Example from colorful_print import color color.black('Print Black') color.red('Print Red') color.green('Print Green') color.yellow('Print Yellow') color.blue('Print Blue') color.magenta('Print Magenta') color.cyan('Print Cyan') color.white('Print White') print() color.red('Print Red') color.green('Print Bold Green', bold = True) color.yellow('Print Bold Italic Yellow', bold = True, italic = True..

[Python] builtin dir() 함수 dir()함수는 입력된 parameter 의 attributes를 list 형태로 return 해주는 함수. def dir(p_object=None): # real signature unknown; restored from __doc__ dir([object]) -> list of strings If called without an argument, return the names in the current scope. Else, return an alphabetized list of names comprising (some of) the attributes of the given object, and of attributes reachable from it...