흙금이네 블로그

아이디어 DFS로 각 마을을 우수 마을로 선정했을 때와 선정하지 않았을 때 가능한 최댓값을 구해 나간다. 풀이 마을의 주민 수를 리스트 P에 저장하고, 마을 간의 연결을 2차원 리스트 graph에 저장한다. dp[i][j]는 i번 마을을 루트 노드로 하여 해당 마을을 방문했을 때(j = 1)와 방문하지 않았을 때(j = 0)의 최댓값을 저장한다. 함수 dfs는 DFS로 마을을 차례로 방문하여 리스트 visited에 방문 표시 후 리프 노드부터 dp 테이블을 채워 나간다. 현재 마을을 우수 마을로 선정하지 않을 때는 연결된 마을의 우수 마을 여부와 상관없이 더 큰 최댓값을 더하고, 현재 마을을 우수 마을로 선정할 때는 연결된 마을이 우수 마을이 아닐 때의 최댓값을 더한다. 1번 마을을 루트 노드로 함수 d..

아이디어 KMP 알고리즘으로 패턴의 길이를 찾아 나간다. 풀이 i+1은 인덱스 i까지 문자열의 길이를 나타내고, j는 그 문자열에서 접두사와 접미사가 일치하는 부분의 길이를 나타낸다. i+1에서 j를 빼면 패턴의 길이를 알 수 있는데, 이때 문자열 길이 i+1가 패턴의 길이 i+1-j로 나누어 떨어져야 한다. 값이 나누어 떨어지면서 그 몫(패턴의 수)이 1보다 크면 주기문이므로 해당 문자열의 길이와 패턴의 수를 출력한다. def solution(): S = input() N = len(S) lps = [0]*N j = 0 for i in range(1, N): while j > 0 and S[i] != S[j]: j = lps[j-1] if S[i] == S[j]: j += 1 lps[i] = j a, ..

아이디어 문자열 앞뒤의 문자들을 순서대로 비교하여 모든 문자가 일치하면 회문, 한 문자만 어긋나면 유사회문으로 판단한다. 풀이 #1 (Python) 문자열을 S, 문자열 길이의 절반을 N에 저장하고, for문에서 S의 앞과 뒤의 문자들을 순서대로 비교한다. 앞과 뒤의 문자가 다른 경우 앞의 문자를 가리키는 인덱스를 1 증가시킨 후 나머지 문자열을 비교하고, 이번에는 다시 뒤의 문자를 가리키는 인덱스를 1 감소시킨 후 나머지 문자열을 비교해 나간다. 이 과정에서 모든 문자가 일치하면 0, 한 문자만 어긋나 있으면 1, 나머지 경우는 2를 출력한다. import sys input = sys.stdin.readline def solution(): T = int(input()) for t in range(T):..