공부, 기록

문제링크 : www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net import sys def solution(lines,N): lines.sort(key = lambda x:(x[0],-x[1])) answer = lines[0][1]-lines[0][0] tempstart=lines[0][0]; tempend=lines[0][1] for i in range(1,N): start = lines[i][0] end = lines[i][1] if..

문제링크 : www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net #pypy3로 실행 def solution(N): answer = list() stack = list() stack.append(2) stack.append(3) stack.append(5) stack.append(7) while stack: num = stack.pop() if 10**(N-1)

문제링크 : www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net import copy Eratos = [0]*10000 Eratos[0] = 0 Eratos[1] = 1 for i in range(2,100): if Eratos[i]==0: temp = i+i while temp

문제링크 : www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net #PYPY3로 실행 import math import heapq as hq def solution(graph,start,end,N): dists = [math.inf]*N dists[start] = 0 queue = list() hq.heappush(queue,[dists[start],start]) while queue: nowdist, nownode = hq.he..

문제링크 : www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net def solution(N,M,MAPS): answer = 1 for i in range(1,N): for j in range(1,M): if MAPS[i][j] == 1: MAPS[i][j] = min(MAPS[i-1][j-1],MAPS[i][j-1],MAPS[i-1][j])+1 answer = max(MAPS[i][j], answer) return answer**2 def main(): N, M = map(int,input().split()) MAPS = list(..

문제링크 : www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net from itertools import combinations L, C = map(int, input().split()) word_list = set(input().split()) A = set(['a', 'e', 'i', 'o', 'u']) B = set(['b','c','d','f','g','h','j','k','l','m','n','p','q','r','s','t','v','w','x','y','z..

문제링크 : www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net #PYPY3로 실행 import heapq def solution(graph, K, V, E): s=[False]*V valuelist=[999999]*V valuelist[K-1] = 0 queue = list() heapq.heappush(queue, [valuelist[K-1],K-1]) while queue: now_value, now_node = heapq.hea..

문제링크 : www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net from collections import deque def solution(Maps, K, W, H): stack = deque() dx=[0,0,-1,1] dy=[1,-1,0,0] hx=[1,1,-1,-1,2,2,-2,2] hy=[2,-2,2,-2,1,-1,1,-1] stack.append((0,0,K,0)) visitied=set() visitied.add((0,0,K)) mi..

문제링크 : www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net def solution(N,M,booklist): booklist.sort() leftlist=list() rightlist=list() sumlen=0 highlen = max(max(booklist),min(booklist)*-1) for i in booklist: if i < 0: leftlist.append(i*-1) else: rightlist.append(i) leftli..

문제링크 : www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net N, goal = map(int,input().split()) maps = list() for i in range(N): s, e, p = map(int,input().split()) if e