본문 바로가기
반응형

Problem Solving232

[KMP] 백준 1786번 : 찾기 / 플래5 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net def kmp(all_string, pattern): # kmp_table table = [0 for _ in range(len(pattern))] i = 0 for j in range(1, len(pattern)): while i > 0 and pattern[i] != pattern[j]: i = table[i-1] if pattern[i] == pattern[j]: i += 1 table.. 2022. 3. 29.
[KMP] 백준 16916번 : 부분 문자열 / 골드 3 https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net KMP를 몰랐다면 시간때문에 좀 힘들었을 것 같으나, 난 KMP를 공부했기 때문에 쉽다. def kmp(all_string, pattern): # kmp_table table = [0 for _ in range(len(pattern))] i = 0 for j in range(1, len(pattern)): while i > 0 and pattern[i] != pattern[j]: i = table[i-1] if patter.. 2022. 3. 29.
[강한 연결 요소/파이썬] 백준 2150번 : Strongly Connected Component / 플래5 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net import collections import sys sys.setrecursionlimit(10**5) input = sys.stdin.readline v, e = map(int, input().split()) graph = collections.defaultdict(list) for _ in range(e): a, b =.. 2022. 3. 29.
[세그먼트 트리/파이썬] 백준 2042번 : 구간 합 구하기 / 골드 1 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net import sys input = sys.stdin.readline n, m, k = map(int, input().split()) lst = [] for _ in range(n): lst.append(int(input())) def merge(left, right): return left + right def build(stree, no.. 2022. 3. 27.
[누적합/파이썬] 백준 9527번 : 1의 개수 세기 / 골드 2 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net a, b = map(int, input().split()) psum = [0 for x in range(60)] for i in range(1, 60): psum[i] = 2**(i-1) + 2 * psum[i-1] def check(num): count = 0 bin_num = bin(num)[2:] length = len(bin_num) for i in range(le.. 2022. 3. 26.
[다이나믹 프로그래밍/파이썬] 백준 2098번 : 외판원 순회 / 골드 1 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net n = int(input()) board = [] for _ in range(n): board.append(list(map(int, input().split()))) dp = [[-1 for _ in range(1 2022. 3. 25.
반응형

티스토리툴바