one Book a Day

영역과 기능에 따라 적절한 tag를 사용해야함(웹 접근성(web accessibility)과 SEO(검색엔진 최적화)를 위해) //영역구분이 확실해지면 그렇지 않은 문서보다 더 적절한 키워드가 추출됨 HTML5에서 새로 제공하는 시맨틱 태그들 본문의 주 내용이 들어가는 공간. 사이드에 위치하는 공간 // 본문과 직접 관련 없는 내용. 카테고리, 태그목록 등. 본문에서 주석 각주 figure안에서 부가설명. 독립적인 콘텐츠 문서 또는 섹션의 바닥//회사정보, 소유자 소셜미디어정보, 약관 등 문서. 부가정보 // header과 중첩불가. 헤더 // 문서 제목, 로고, 작성자, 작성일.(메타정보) // article이나 section내 부가정보 표현에도 씀. 콘텐츠//문서에 한번만쓰임. 본문. 콘텐츠 내용(a..

순서가 있으면 위상정렬. import sys input = sys.stdin.readline from collections import deque def topological_sort(): queue=deque() for i in range(1,N+1): if not level[i]: queue.append(i) answer.append(i) while queue: cur_node=queue.popleft() for next_node in graph[cur_node]: level[next_node] -=1 if not level[next_node]: queue.append(next_node) answer.append(next_node) N,M = map(int,input().split()) graph =..

import sys input = sys.stdin.readline from math import factorial N,K = map(int,input().split()) print((factorial(N)//(factorial(K)*factorial(N-K)))%10007) 사실 모듈써서 푸는게 의도는 아닐것 같은데 귀찮아서 썼다.. 본의도는 파스칼의 삼각형의 구현이었을 것 같아 관련코드도 가져왔다. n, k = map(int, input().split()) dp = [[0] * 1 for i in range(1001)] dp[1].append(1) for i in range(2, 1001): for j in range(1, i + 1): if j == 1: dp[i].append(1) elif j =..

딱히 소수판별을 체를 사용해서 할 필요는 없을 것 같아서 더한값들 개별적으로 진행해줬다. 조합은 DFS로 구성. import sys input = sys.stdin.readline def DFS(start,depth,sum_cow): if depth==M: if isPrime(sum_cow): answer.add(sum_cow) for i in range(start,N): if not visited[i]: visited[i]=True DFS(i+1,depth+1,sum_cow+H[i]) visited[i]=False def isPrime(n): if n

리스트쓰니까 시간초과나서 딕셔너리로 고쳐서 통과 역시 갓셔너리. import sys input = sys.stdin.readline N,M = map(int,input().split()) S = {} for _ in range(N): S[input().rstrip()] = 1 cnt=0 for _ in range(M): a = input().rstrip() try: if S[a] ==1: cnt+=1 except: continue print(cnt)

dp_dists 만들어서 거리 저장하고 max값 뽑는대로 동일한 애들 숫자 다 세주고 끝냈슴니당. 가중치가 모두 1로 같아서 그냥 BFS 돌렸슴니당. import sys input = sys.stdin.readline from collections import deque def BFS(start): queue = deque() queue.append(start) dp_dists[start] = 0 while queue: cur_node = queue.popleft() for next_node in graph[cur_node]: if dp_dists[next_node]==-1: dp_dists[next_node] = dp_dists[cur_node] + 1 queue.append(next_node) # 헛..

이문제는 시간조건이 조금 까다로웠다. heap에 들어가는 간선 갯수를 N^2개가 아닌 N개수준으로 맞춰야 하는 상황. 좌표거리에 대해 각각 정렬한 뒤 가장 가까운 좌표들로 push했다. 각 노드번호를 matrix에 더해주고 좌표거리와 노드번호로 heap에 정렬. 3(N-1) 개의 간선 조사로 크루스칼을 돌렸다. import sys input = sys.stdin.readline from heapq import heappop,heappush def kruskal(): min_dists = 0 while dists: dist,a,b = heappop(dists) if find(a) != find(b): union(a,b) min_dists+=dist return min_dists def find(x): if..

마을 최소 도로로 잇기.+ 2개마을로 분리(실상 간선 갯수만 마지막 하나 안그으면 마을이 2개가 된다,) import sys input = sys.stdin.readline from heapq import heappop,heappush def find(a): if parents[a] == a: return a parents[a] = find(parents[a]) return parents[a] def union(a,b): a = find(a) b = find(b) if b>a: parents[b] = a else: parents[a] = b # N개의 집 M개의 길(쌍방향) / 마을 분리. # 나머지 길의 유지비 합 최소 / 마을 2개로 분리,길 최소로. # 1번은 분리(유니온 파인드에서 마지막 하나만 ..

대놓고 MST문제이다. 간선위주고 거리값 구해서 heappush하고 최소 거리단위부터 잇고 이어져있으면 패스 안 이어진곳에서 최소 값을 heap을 통해 union하면서 거리값을 더해주는 kruskal로 해결. prim은 아직 못한다.. import sys input = sys.stdin.readline from heapq import heappop,heappush def kruskal(): answer = 0 while dists: ab_dists,star_a,star_b = heappop(dists) if find(star_a) !=find(star_b): answer += ab_dists union(star_a,star_b) return answer def union(a,b): a = find(a) ..

LIS는 예전에는 dp를 통해 이전값들을 검사해주며 모든 count를 계산해 풀었다면 이제는 이진탐색으로 직접dp수열을 관리하며 들어가야할 자리를 찾고 나보다 큰수는 나로 교체해주는 식으로 진행된다. 물론 내가 제일 크다면 그냥 오른쪽에 append한다. 이렇게하면 최종 dp에 남는 수열은 LIS는 안되지만 그 길이는 lis의 길이이다. 알고리즘은 의외로 heap을쓰는 회의실 배정문제와 비슷한 편. from bisect import bisect_left #이진탐색 코드, 같은 수일 경우 왼쪽 index를 돌려준다 input() A = list(map(int, input().split())) dp = [] for i in A: k = bisect_left(dp, i) #자신이 들어갈 위치 k if len(..