흙금이네 블로그

아이디어 #1 라그랑주에 의해 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명되었으므로 7453번 - 합이 0인 네 정수처럼 두 제곱수를 더한 값들에서 투 포인터로 합이 n이 되는 네 제곱수를 찾는다. 풀이 #1 (Python) 딕셔너리 cnt_dict에 두 제곱수 합을 키로, 0이 아닌 제곱수의 개수를 값으로 저장한다. 입력 n이 50,000 이하로 주어지므로 제곱수의 제곱근은 223 이하로 설정하고, 0은 제곱수가 아닌 것으로 본다. 세트 numbers에 두 제곱수 합들을 저장한 후 numbers를 오름차순으로 정렬한 리스트로 대체한다. 투 포인터를 이용해 numbers에서 네 제곱수 합이 n인 경우를 찾아 최소 제곱수 개수를 갱신해 나간다. n = int(input()) c..

아이디어 문자열의 접두사와 접미사가 일치하면서 문자열 중간에 등장하는 가장 긴 부분 문자열을 찾는다. 풀이 문자열 S에 대한 부분 일치 테이블 lps를 만든다. S의 접두사와 접미사가 일치하면서 가장 긴 부분 문자열 S[-j:]가 문자열 S의 중간에 등장하면 S[-j:]를 출력한다. S의 중간에 등장하지 않으면 그 다음 길이의 부분 일치 문자열을 찾아 출력하고, 없으면 -1을 출력한다. lps[-1]이 0이면 슬라이싱이 S[-0:]로 되어 문자열 S를 나타내고, S는 S[1:-1]에 포함되지 않아 if문이 실행되지 않는다. 또 lps[-1]-1은 -1이 되어 lps[-1]을 가리키게 되므로 elif문도 실행하지 않고 else문의 -1을 출력한다. def solution(): S = input() N = ..

아이디어 가능한 세 자릿수에서 각 질문에 대한 대답에 따라 불가능한 경우를 제외해 나간다. 풀이 #1 (Python) 세트 numbers에 1~9의 숫자 중 서로 다른 숫자 세 개로 구성된 세 자릿수를 문자열로 저장한다. 질문마다 질문한 숫자는 문자열로 Q에, 스트라이크 개수와 볼 개수는 정수로 strike와 ball에 저장한다. numbers에 있는 수를 구성하는 각 숫자가 Q와 자릿값까지 같으면 s를, 그렇지 않고 Q에 포함되면 b를 증가시킨다. 해당 숫자의 s와 b가 각각 strike와 ball에 같다면 temp에 추가하고, for문 종료 후에 기존의 numbers를 temp로 대체한다. import sys input = sys.stdin.readline def solution(): numbers ..

아이디어 DFS로 말단 직원에서부터 자신의 부하들에게 전화하는 데 걸리는 가장 긴 시간을 DP로 구해 나간다. 풀이 상사 번호를 리스트 P에 저장하고, 부하 직원의 번호를 상사 번호에 맞게 2차원 리스트 child에 저장한다. 함수 dfs에서는 자식 노드들을 탐색하여 구한 자식 노드에서 가장 오래 걸리는 시간을 빈 리스트 temp에 추가한다. 내림차순 정렬한 temp의 각 요소들과 그 순번을 더한 값 중 최댓값을 해당 노드에서 가장 오래 걸리는 시간으로 저장한다. 리프 노드에서는 자식 노드가 없어 temp가 빈 리스트이므로 for문과 if문 진입 없이 함수가 종료된다. 0번 직원부터 함수 dfs를 호출한 후 0번 직원의 dp 테이블에 저장된 결과값을 출력한다. def dfs(idx): temp = [] ..

아이디어 규칙을 찾아 간단하게 계산할 수 있는 부분은 계산하여 처리하고, 나머지는 브루트포스로 처리한다. 풀이 #1 (Python) 한 자릿수 앞에는 0이 붙으며, 00부터 59까지의 수에서 0~5는 15번씩, 6~9는 6번씩 등장한다. K가 등장하는 횟수를 m이라 한다면 00분 00초부터 59분 59초까지 K가 등장하는 총 횟수 x는 초와 상관없이 분에서 K가 등장하는 횟수와 분과 상관없이 초에서 K가 등장하는 횟수의 합(m×60×2)에서 분과 초에서 동시에 K가 등장하는 횟수(m^2)를 빼서 K가 0~5일 때는 1575, K가 6~9일 때는 684가 된다. 시에 대해서는 계산식을 세우는 것이 더 복잡할 것 같아 for문에서 문자열로 K의 포함 여부를 확인하도록 한다. 만약 시에서 K가 등장하면 분과 ..

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