one Book a Day

파이썬 입출력 속도 비교. 입력속도 1 PyPy int(sys.stdin.readline()) 0.9229 2 PyPy map(int,os.read(0, 100000000).split('\n')) 1.1169 3 PyPy3 map(int,os.read(0, 100000000).decode('utf-8').split('\n')) 1.5408 4 PyPy int(raw_input()) 1.925 5 Python 3 map(int,os.read(0, 100000000).decode('utf-8').split('\n')) 4.4033 6 Python 3 int(sys.stdin.readline()) 4.4394 7 PyPy3 int(sys.stdin.readline()) 6.6291 8 Python 3 int(..

Cut Vertex ( 절단점 찾기 ) Cut Vertex(절단점) 그래프의 절단점이란 해당 정점을 삭제했을 때 그래프가 두 개 이상의 그래프로 나누어 지는 점을 말합니다. 이 때 그래프는 항상 undirected graph입니다. 1) 직관적으로 절단점을 찾는 방법을 생각해 봅시다. (러프한 방법. 직접 삭제해본다. 섬나누기 or 연구소 같은 방법.) 느낌상 모든 정점에 대해 그 정점을 삭제한 후의 그래프를 먼저 따로 구합니다. 그 다음 DFS 혹은 BFS 로 몇 번만에 전체 그래프를 cover할 수 있는지를 보면 될 것 같습니다. 그러나 이 방식은 각 정점마다 알고리즘을 돌려야 하니 정점이 많아 질수록 매우 불리해 집니다. 2) 무향그래프의 DFS Spanning tree를 보면 cross edge가..

인덱스를 지정하면 해당 위치의 배열 포인터를 얻게된다. 이를 통해 연결된 객체를 찾아 실제 값을 찾아낸다. 슬라이싱 0.499 마이크로초 1 리스트 reverse() 2.46 마이크로초 5 revsered() + join() 2.49 마이크로초 6 for 반복 5.5 마이크로초 12 while 반복 9.4 마이크로초 21 재귀 24.3 마이크로초 54 s[:]는 사본을 리턴한다. 이 방식은 문자열이나 리스트를 복사하는 파이썬다운 방식(Pythonic way) 이다. 앞으로 문자열 비교는 slicing을 이용하자.

DFS하니까 재귀에러나고 시간초과 메모리초과 가관이어서 BFS로 다시 풀었다. 구조는 똑같이 queue에 1을 넣고 1부터 위에서 아래로 탐색하며 parent값을 자식들에게 할당하는 방식. import sys input = sys.stdin.readline from collections import defaultdict,deque N = int(input()) graph = defaultdict(list) for _ in range(N-1): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a) queue = deque([1]) ans = {} check = [False for _ in range(N+1)] while queue: pa..

처음에 그냥 matrix에 넣었다가 시간초과나고 합연산은 한번에 하는걸로 코드 수정. 통과 import sys input = sys.stdin.readline for test in range(int(input())): N,M = map(int,input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] ans = [[] for _ in range(2)] for i in range(N): ans[0].append(sum(matrix[i])) for i in range(N): ans[1].append(sum(matrix[m][i] for m in range(N))) for _ in range(M): r1,c1,r2,c2,v = ma..

처음에 6으로 나눠떨어져야 한다는 조건 못봐서 실패. 그리고 한참 디버깅코드 안빼고 왜 실패하지?? 고민하다 결국 ans디버깅 코드 넣어논거 발견하고 해결. 코드 더 줄일 수 있을 것 같지만 그냥 제출. matrix = [input() for _ in range(5)] N = (len(matrix[0])//4)+1 zero = ['***','* *','* *','* *','***'] one = [' *',' *',' *',' *',' *'] two = ['***',' *','***','* ','***'] three = ['***',' *','***',' *','***'] four = ['* *','* *','***',' *',' *'] five = ['***','* ','***',' *','***'] s..

itertools라이브러리 combinations모듈과 permutations모듈을 통해 손쉽게 순열과 조합을 구할 수 있다. 이때 만들어진 순열,조합은 튜플형태로 리스트에 담겨서 반환된다. [(0,1,2),...] 조합 from itertools import combinations arr = [0, 1, 2, 3, 4, 5] print(list(combinations(arr, 3))) 순열 from itertools import permutations arr = [0, 1, 2, 3, 4, 5] print(list(permutations(arr, 3))) 재귀 기본적인 아이디어는 DFS,백트래킹과 유사하다. combination([0,1,2,3],2) = ([0],combination([1,2,3],1..