one Book a Day

Cut Vertex ( 절단점 찾기 ) Cut Vertex(절단점) 그래프의 절단점이란 해당 정점을 삭제했을 때 그래프가 두 개 이상의 그래프로 나누어 지는 점을 말합니다. 이 때 그래프는 항상 undirected graph입니다. 1) 직관적으로 절단점을 찾는 방법을 생각해 봅시다. (러프한 방법. 직접 삭제해본다. 섬나누기 or 연구소 같은 방법.) 느낌상 모든 정점에 대해 그 정점을 삭제한 후의 그래프를 먼저 따로 구합니다. 그 다음 DFS 혹은 BFS 로 몇 번만에 전체 그래프를 cover할 수 있는지를 보면 될 것 같습니다. 그러나 이 방식은 각 정점마다 알고리즘을 돌려야 하니 정점이 많아 질수록 매우 불리해 집니다. 2) 무향그래프의 DFS Spanning tree를 보면 cross edge가..

강한 연결 요소(SCC) 무향 그래프에서 절단점이 존재하지 않는 그래프를 우리는 Biconnected component라고 부릅니다. 절단점이 없다면 그래프 상의 어떤 점을 삭제하더라도 임의의 두 정점은 서로로 가는 경로가 존재하게 됩니다. Biconnected Component Undirected Graph에서 절단점이 존재하지 않는 그래프 Strongly Connected Component 만약 그래프의 임의의 한 정점에 대해 다른 모든 정점으로 가는 경로가 존재한다면 그 그래프를 SCC(Strongly Connected Component)라고 한다. SCC(Strongly Connected Component)특징 같은 SCC내에서 뽑은 임의의 U, V 점에서 U->V 혹은 V->U의 경로(직/간접적..

배열에서 위치당 총합에 얼마나 기여하는지 보면 됨. 가에 있는 열, 행은 인덱스 0, end는 1번, 1~end-1까지는 2번 내부에 있는 열, 행은 인덱스 0, end는 2번, 1~end-1까지는 4번 이걸 기준으로 각 열 행 합에 대해 가에있는 값과 차이를 비교해주고 바꿔서 올라가면 바꿔주면 된다. import sys input = sys.stdin.readline N, M = map(int, input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] # 1~M-2번 인덱스, 1~N-2번 인덱스의 합이 가장 작은 배열과 가생이에 있는 합이 가장 큰 배열과 교환을 해준다. # 열검사 -> (1~N-2)*2 + 0 + N-1 ..

가장 큰 정사각형 만들기와 동일하다. 장애물이 나오면 최소 길이가 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의 경우 이미 ..