흙금이네 블로그

아이디어 1949번 우수 마을처럼 DFS와 DP로 가중치의 최댓값을 구하고, 추가로 그 정점 번호들을 저장한다. 풀이 가중치를 리스트 w에 저장하고, 정점 간의 연결을 2차원 리스트 graph에 저장한다. dp[i][j]는 정점 i를 루트 노드로 하여 해당 정점을 방문했을 때(j = 1)와 방문하지 않았을 때(j = 0)의 최댓값을 저장한다. S[j]는 해당 정점을 방문했을 때(j = 1)와 방문하지 않았을 때(j = 0)의 최대 독립 집합을 저장한다. 함수 dfs는 DFS로 정점을 차례로 방문하여 리스트 visited에 방문 표시 후 리프 노드부터 dp와 최대 독립 집합을 구한다. 우수 마을과 달리 함수 종료 시 현재 정점을 방문했을 때와 방문하지 않았을 때의 최대 독립 집합을 반환한다. 현재 정점을 ..

아이디어 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):..

아이디어 동적 계획법으로 어떤 객차까지의 객차들 중에서 최대로 운송할 수 있는 손님 수를 구해 나간다. 풀이 전체 객차 수를 N, 소형 기관차 한 대가 끌 수 있는 최대 객차 수를 M에 저장한다. 객차 손님 수는 앞에 0을 추가하여 리스트 acc에 저장하고, acc를 누적합 리스트로 만든다. 0으로 채워진 4*(N+1) 크기의 2차원 리스트 dp를 만들고, for문으로 진입한다. dp[i][j]는 i 번째 소형 기관차가 j 번째 객차까지의 손님들 중 운송할 수 있는 최대 손님 수를 나타낸다. 그 다음 순번의 소형 기관차는 이전 순번의 소형 기관차가 운송하는 손님과 겹치지 않도록 M만큼씩 차이를 둔다. def solution(): N = int(input()) acc = [0]+list(map(int, i..

아이디어 W을 구성하는 문자들의 인덱스를 문자별로 저장해 인덱스 값의 차이로 문자열 길이를 구한다. 풀이 #1 (Python) W를 구성하는 알파벳 소문자의 인덱스를 저장하기 위한 2차원 리스트 alpha를 만든다. for문에서 함수 ord를 사용하여 W의 a부터 z를 0부터 25에 매칭해 alpha에 문자별로 W에서의 인덱스를 저장한다. 이후 alpha에서 문자별로 K개의 문자를 포함하는 문자열의 길이를 리스트 res에 추가해 나간다. res에 값이 존재하면 res에서의 최솟값과 최댓값을 출력하고, 존재하지 않으면 -1을 출력한다. import sys input = sys.stdin.readline def solution(): T = int(input()) for t in range(T): alpha ..

아이디어 위쪽, 왼쪽, 오른쪽의 가능한 지역 중 최대 가치를 더해 나간다. 풀이 입력 받은 N, M을 저장하고, 첫 행을 입력 받아 리스트 dp에 저장한다. 첫 행의 지역들은 시작 지점을 제외하고는 왼쪽 지역을 탐사해야 이동할 수 있으므로, dp를 오른쪽으로 누적하여 더한다. 첫 행과 마지막 행의 지역들을 제외한 지역들을 처리하기 위해 N-2의 크기로 for문을 실행한다(N > 2일 때 실행). 우선 현재 행을 arr에 입력 받고, arr과 같은 크기로 0이 채워진 리스트 temp를 생성한다. temp에는 왼쪽에서 오른쪽으로 탐사해 나갈 때의 최대 가치를 저장한다. temp의 첫 번째 값은 arr의 첫 번째 값(현재 지역 가치)과 dp의 첫 번째 값(위쪽 지역 최대 누적 가치)의 합으로 저장하고, 나머지..

아이디어 시간에 맞게 입장과 퇴장이 모두 확인된 학회원들을 찾는다. 풀이 #1 (Python) 개강총회 시작 시간 S, 개강총회 종료 시간 E, 스트리밍 종료 시간 Q를 모두 문자열로 입력 받는다. 테스트 케이스 수가 따로 주어지지 않으므로 try except문으로 입력이 주어지는 동안 while문을 반복한다. 시간은 T, 이름은 name에 문자열로 저장하고, T가 S 이하이면 딕셔너리 names에 name을 1로 저장한다. T가 E 이상 Q 이하이면서 names에 값이 있으면 중복 계산 방지를 위해 해당 값을 0으로 바꾸고 결과값 res를 증가시킨다. 문자열의 대소 비교에서는 순서대로 각 문자열 문자들의 아스키 코드 값으로 대소 비교가 된다. import sys input = sys.stdin.read..

아이디어 DFS로 각 지역에서 이동할 수 있는 최대 경로 길이를 저장해 나간 후, 숲에서의 최대 경로 길이를 구한다. 풀이 함수를 이용한 DFS를 위해 sys.setrecursionlimit으로 최대 재귀 깊이를 최대 대나무 숲의 크기인 500*500로 설정한다. 상하좌우로 이동하는 행열 변화 값을 리스트 delta에 저장하고, 숲의 크기를 n, 숲 정보를 2차원 리스트 forest에 저장한다. 방문 표시 및 최대 경로 길이를 저장하는 2차원 리스트 visited와 결과값을 저장하는 res를 만든다. 이중 for문을 돌며 각 칸에 대해 함수 dfs를 호출하는데, 해당 칸을 방문한 적이 있으면 함수를 바로 종료한다. 방문한 적이 없으면 해당 칸 방문 표시 이후, 현재 칸보다 대나무가 더 많은 근처 칸에 대..

아이디어 순서대로 T에서 S의 문자들을 찾아 나간다. 풀이 #1 (Python) 테스트 케이스 수가 따로 주어지지 않으므로 sys.stdin.readlines으로 입력 값을 모두 읽는다. 각 테스트 케이스에서 find 메서드로 T에서 찾은 문자열 S의 문자들 인덱스를 차례로 idx에 저장하고, 그 다음 문자는 그 이후 인덱스부터 찾아 나가는 식으로 for문을 반복한다. 도중에 S의 문자가 T에 존재하지 않아 idx가 -1이 되면 No를 출력하고, S의 문자들을 모두 찾는 경우 Yes를 출력한다. import sys input = sys.stdin.readlines for case in input(): S, T = case.split() idx = -1 for c in S: idx = T.find(c, i..