반응형 전체 글 목록571 [다이나믹 프로그래밍/파이썬] 백준 1562번 : 계단 수 / 골드 1 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net n = int(input()) dp = [[[0 for _ in range(1 2022. 3. 30. [KMP] 백준 1305번 : 광고 / 플래 4 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net size = int(input()) b = input() table = [0 for _ in range(len(b))] i = 0 for j in range(1, len(b)): while i > 0 and b[i] != b[j]: i = table[i-1] if b[i] == b[j]: i += 1 table[j] = i print(size-table[-1]) 초반엔 너무 어렵게 생각해서 감이 안잡혔는데, 파이 .. 2022. 3. 29. [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. [알고리즘/ 파이썬] KMP 알고리즘? 그림으로 쉽게 이해하기! KMP 알고리즘(Knuth-Morris-Pratt algorithm)이란 문자열 검색을 매우 빠르게 해주는 알고리즘이다. 특정 패턴이 주어졌을 때 전체 문자열을 빠르게 검색하여 그 패턴이 어디에 등장하는 지 찾아준다. KMP 알고리즘을 이해하려면 파이 배열에 대해 알아야 한다.파이 배열의 i번째 성분은, 문자열의 i번째까지의 부분 문자열에서 접두사, 접미사가 같아지는 최대 길이를 뜻한다. 파이 배열의 예시는 아래와 같다. KMP 알고리즘은 2단계에 걸쳐 실행된다.1. 주어진 패턴에 대해 파이 배열 만들어내기2. 파이 배열을 활용하여 패턴의 등장 위치를 빠르게 찾아내기 1. 파이 배열 만들기파이 배열의 0번째 값은 무조건 0이 된다. 한글자 짜리 문자열에는 접두사, 접미사가 없기 때문이다. 파이 배열을.. 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. 이전 1 ··· 19 20 21 22 23 24 25 ··· 96 다음 반응형
