https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net - 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000) 공유기의 개수 C (2 ≤ C ≤ N) 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. - 출력 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다. import sys from collect..

https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 이중 for 문을 사용해서 n^2의 시간 복잡도를 나타내지만, 문제를 푸는 것에는 문제가 없다고 생각했다. 시간제한 1초에 메모리 제한 512mb 이므로 약 데이터의 수가 10000000개여야 매모리 40mb이를 차지하기 때문이다. import sys s = sys.stdin.readline() a = [] for i in range(1,len(s)): for j in range(len(s)-i): a.append(s[j:j+i]) print(len(set(a)))..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 아마 append 의 시간 복잡도가 o(n)으로 알고 있다. import sys n = int(sys.stdin.readline()) stack = [] count = 0 answer = [] flag = True for i in range(0,n): x = int(sys.stdin.readline()) while ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 우선 이문제는 일반적인 for 문을 이용해서 풀으면 시간 초과의 문제가 나오게 된다. 아마 n^2의 시간 복잡도 때문이라고 생각한다. python이 1초에 몇 만번인지는 기억이 안나지만 그만큼 연산을 하기 때문에 import sys n, m = map(int, sys.stdin.readline().split()) num_list = [0]+list(map(int,sys.st..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 시간 복잡도는 어 음... 잘 모르겠다. 아는 건 우선 deque 라이브러리는 탐색을 수행할때 O(N)을 잡아먹는 빠른 라이브러리하는건 안다. from collections import deque n,k = map(int,input().split()) visited = [False] * 100001 dx = [-1, 1 , 2] def bfs(n,k): end = k q..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net from collections import deque n, m = map(int, input().split()) graph = [0 for _ in range(101)] visited = [False] * 101 ladder = {} snake = {} for _ in range(n): x, y = map(int,input().split()) ladd..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 잘못된 풀이 - 시간초과로 인해 문제가 발생한다. 당연히 부르드포스로 접근을 하게 되면서 문제가 풀리기는 하지만 시간 초과의 문제를 만나게 되었다. import sys from collections import deque import copy n, m = map(int, sys.stdin.readline().split()) graph = [] for i in range(n..

https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net import sys from collections import deque sys.setrecursionlimit(100000) n, m, r = map(int, sys.stdin.readline().split()) graph = [[] for i in range(n + 1)] visited = [False] * (n + 1)..