one Book a Day

가장 큰 정사각형 만들기와 동일하다. 장애물이 나오면 최소 길이가 0으로 끊기고 다시 1부터 하나씩 늘려가는방식. import sys input = sys.stdin.readline # 가장 큰 정사각형 문제와 같은 문제. 위 좌, 대각 안쪽 중 가장 변의 길이가 짧은 변에 하나를 추가시켜주는 방식이며 # 장애물을 만나면 다시 0부터 시작한다. M, N = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(M)] dp_length = [[0 for _ in range(N+1)] for _ in range(M+1)] max_length = 0 for i in range(1,M+1): for j in range..

카운팅하고 가장 숫자 큰 애들로만 만들어줌. import sys input = sys.stdin.readline n, m = map(int, input().split()) dnas = [input().rstrip() for _ in range(n)] nut = ['A','C','G','T'] dp_sum = [[0 for _ in range(4)] for _ in range(m)] for i in range(n): for j in range(m): for k in range(4): if dnas[i][j] == nut[k]: dp_sum[j][k] += 1 break result = '' cnt = 0 for i in range(m): tmp = max(dp_sum[i]) result += nut[dp_..

선호도 관리를 어떻게 할 것인가? 일단 힙으로 하긴했는데.. 최선일지는 모르겠다. import sys from heapq import heappop,heappush input = sys.stdin.readline # N일 K종류 맥주 무료 제공 # 하루 맥주 1병 전에 받은 종류 못받음. # 맥주 N개의 선호도 합 M이상. # 조합 K 종류 맥주 중 N개 추출 합이 M이상되는. # 도수 낮은거 순으로 먹음. N, M, K = map(int, input().split()) beers = [list(map(int, input().split())) for _ in range(K)] beers2 = sorted(beers,key=lambda x: (x[1],x[0])) heap = [] flav_p = 0 cn..

최대길이 회문 확인. 사실 while문보다 for문, slicing이 더 빠르다. import sys inmput = sys.stdin.readline def check(a,left,right): while left < right: if a[left] != a[right]: return 0 left += 1 right -= 1 return 1 s = input().rstrip() n = len(s) # 최대 길이가 회문 아니면 n if not check(s,0,n-1): print(n) # 최대길이에서 하나뺀게 회문 아니면 n-1 elif not check(s,0,n-2): print(n-1) else: print(-1)

기존 마나커 탐색에 1. 중심이 #이 아닐때(크기1짜리 펠린드롬) 2. 반지름 갱신시 #을 뺀 반지름의 크기만큼 펠린드롬수 추가 3. 범위 확장 시 확장된 범위가 #범위가 아니면 펠린드롬 추가 import sys input = sys.stdin.readline def manacher(string): n = len(string) a = [0] * n # i번째 문자를 중심으로 하는 가장 긴 팰린드롬 반지름 크기. c = 0 # 중심점(center) 초기화 r = 0 # 시작점에서 가장 먼 반경(펠린드롬 끝나는 인덱스중 가장 큰 값.) answer = 0 for now in range(n): if string[now] != '#': answer +=1 # i번째 문자가 now 아래쪽에 있는 문자를 중심으로 ..

마나커 알고리즘의 핵심은 #을 삽입해 짝수 펠린드롬에 대비하는것, 중심점과 반지름 a배열의 관리. a배열의 관리는 r과 현재 인덱스now값에 의거해 관리되며 r과c값은 펠린드롬 범위 내 외에서 출발지점 인덱스 0에서 얼마나 멀어졌냐에 따라 관리된다. import sys input = sys.stdin.readline def manacher(string): n = len(string) a = [0] * n # i번째 문자를 중심으로 하는 가장 긴 팰린드롬 반지름 크기. c = 0 # 중심점(center) 초기화 r = 0 # 시작점에서 가장 먼 반경(펠린드롬 끝나는 인덱스중 가장 큰 값.) for now in range(n): # i번째 문자가 now 아래쪽에 있는 문자를 중심으로 하는 팰린드롬 범위 밖의..

Manacher&#39;s 알고리즘 : 펠린드롬 탐색. 문자열에서 i번째 문자를 중심으로 하는 가장 긴 팰린드롬 길이를 반지름 r을 저장해 사용한다. O(N)에 다끝나버린다. ## 동작방식 i는 배열의 길이만큼 진행된다. 짝수 팰린드롬 경우 #으로 패딩을 주어 진행한다.(강제로 홀수만듬) aa -> #a#a# a 배열에는 해당 인덱스를 중심으로 한느 가장 긴 팰린드롬의 길이를 저장한다. 반지름 길이를 저장한느 것이지만 #으로 확장 시켰으므로 전체 길이가 된다. r, c변수 r : 해당 인덱스까지 가장 긴 팰린드롬의 우측 끝 c: 해당 인덱스까지 가장 긴 팰린드롬이 중심 인덱스 팰린드롬이라고 정해져 있는 인덱스에 속해 있는지 검사하며 a[i]값을 초기화한다. #b#a#n#a#n#a# -> a의 경우 이미 ..

인덱스를 지정하면 해당 위치의 배열 포인터를 얻게된다. 이를 통해 연결된 객체를 찾아 실제 값을 찾아낸다. 슬라이싱 0.499 마이크로초 1 리스트 reverse() 2.46 마이크로초 5 revsered() + join() 2.49 마이크로초 6 for 반복 5.5 마이크로초 12 while 반복 9.4 마이크로초 21 재귀 24.3 마이크로초 54 s[:]는 사본을 리턴한다. 이 방식은 문자열이나 리스트를 복사하는 파이썬다운 방식(Pythonic way) 이다. 앞으로 문자열 비교는 slicing을 이용하자.

문자열 매칭 연습하기위해 kmp사용했고 사실 그냥 패턴을 기준으로 split하거나 replace로 변경시켜주면 더 쉽다. import sys sys.stdin = open('input.txt') def make_failure_function(p): failure_function = [0] * (len(pa)) counter = 0 for idx in range(1, len(p)): while counter > 0 and p[counter] != p[idx]: counter = failure_function[counter-1] if p[counter] == p[idx]: counter += 1 failure_function[idx] = counter return failure_function def kmp..

회문 1은 1개만 찾으면 됐지만 회문2는 모든 회문중 가장 긴 문자열을 찾는다. import sys sys.stdin = open('input.txt') def find_palindrome(sentences): for k in range(100, 0, -1): for i in range(100): for j in range(100-k+1): if sentences[i][j] == sentences[i][j+k-1]: left = j right = j+k-1 while sentences[i][left] == sentences[i][right] and left