작은 지식주머니

링크 : https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net bfs로도 풀 수 있을것 같은데?? 에서 시간 초과가 날 것 같아서 그냥 바로 다익스트라로 직행했다. 적당히 다익스트라 를 적용했다. 노드에서 노드로 가는 가중치가 전부 1 이므로 어렵지 않았다. import sys import heapq n,m,k,start = map(int,input().split()) INF ..

링크 : https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 10진법으로 바꿀려면 int를 사용하면 됨. a, b = map(str,input().split()) print(int(a,int(b)))

백준 링크: https://www.acmicpc.net/problem/5692 5692번: 팩토리얼 진법 상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. www.acmicpc.net input을 쓰면 그대로 시간초과가 나는데 sys.stdin.readline() 를 사용 import math import sys input = sys.stdin.readline while True: n = input().split() length = len(n[0]) if n[0] =='0': break sum = 0 for i in range(length): sum += int(n[0..

백준 링크:https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net -에 괄호를 만들고 아니라면 전부 더하면 최소값 a = input().split('-') num = [] for i in a: cnt = 0 s = i.split('+') for j in s: cnt += int(j) num.append(cnt) n=num[0] for i in range(1,len(num)): n -= num[i] print(n)

백준 링크:https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 1차원문제 다익스트라 알고리즘은 https://brownbears.tistory.com/554 [Python] 최단 경로 알고리즘 - 다익스트라 알고리즘 (Dijkstra Algorithm) 최단 경로 알고리즘이란 주어진 노드와 간선(edge)들 중, 가장 짧은 경로를 찾는 알고리즘입니다. 즉, 서울에서 인천, 대전, 광주, 부산을 갈 수 있..

백준 링크: https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net n = 100.000 m = 100.000 이므로 이중 for in문돌리면 시간 초과가 나온다. 하지만 딕셔너리를 사용하면 최대 20만에 끝날 수 있다. 또한 입력과 출력이 빠른 sys 사용을 했다. import sys input = sys.stdin.readline n,m=map(int,input().split()) user={} for i in ran..

백준 링크:https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net dfs로 풀어도 되고 bfs로 풀어도 되는 문제이다. 1로 시작하는 트리가 몇개인지 파악하는 문제 dfs의 경우 n=int(input()) nums=int(input()) matrix=[[0]*(n+1) for _ in range(n+1)] for i in range(nums): a,b = map(int,input().split()) matrix[a][b] = 1 matrix[b][a] = ..

백준 링크:https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS의 튜토리얼 문제쯤 되는 느낌의 문제였다. 간선의 개수만큼 입력할때 쌍방통행이므로 matrix [a][b] , matrix[b][a] 전부 체크표시하고 dfs,bfs를 순서대로 작동하면 끝 from collections import deque n,m,k = map(int,input().split()) matrix = [[0]*(n+1)..