흙금이네 블로그

아이디어 동적 계획법으로 감소하는 수열 합의 최댓값을 구한다. 풀이 #1 (Python) 리스트 dp에 수열 A와 같은 값들을 저장한다. 이중 for문에서 수열의 두 요소를 비교하여 수가 감소할 때 더 큰 부분 수열의 합으로 갱신해 나간다. max(dp)로 전체 감소 부분 수열의 합 중 가장 큰 값을 찾아 출력한다. def solution(): N = int(input()) A = tuple(map(int, input().split())) dp = list(A) for i in range(N): for j in range(i+1, N): if A[j] dp[j]: dp[j] = dp[i]+A[j] print(max(dp)) solution() 풀이 #2 (Jav..

아이디어 덱을 이용하여 풍선 안 종이에 적힌 수에 따라 풍선을 회전한다. 풀이 덱을 사용하기 위해 collections 모듈의 deque를 불러온다. enumerate 함수를 이용하여 풍선의 번호와 풍선 안 종이에 적힌 수를 튜플 형태로 덱 balloon에 저장한다. for문에서 popleft로 balloon의 맨 앞 풍선을 꺼내 풍선의 번호와 종이에 적힌 수를 각각 r과 d에 할당한다. 결과값 리스트 res에 풍선의 번호를 추가하고, d에 따라 풍선을 이동한다. d가 양수이면 풍선들을 왼쪽으로 회전(-)시키는데 popleft로 풍선이 하나 줄었으므로 rotate에 -(d-1)을 인자로 넘긴다. d가 양수가 아니면(음수인 경우) 풍선들을 오른쪽으로 회전(+)시키기 위해 rotate에 -d를 인자로 넘긴다..

아이디어 동적 계획법으로 각 자릿수에서 줄어들지 않는 수의 개수를 구한다. 풀이 #1 (Python) 0으로 채운 65×10 크기의 2차원 리스트 dp를 생성한다. dp[i][j]는 줄어들지 않는 i 자릿수 중 j로 시작하는 수의 개수이고, dp[i]의 합은 줄어들지 않는 i+1 자릿수의 개수다. i 자릿수에서 0으로 시작하는 줄어들지 않는 수의 개수 dp[i][0]는 이전 자릿수에서 줄어들지 않는 수의 합 sum(dp[i-1])이고, j로 시작하는 수의 다음 숫자 값은 j 이상이므로 dp[i][j]는 j-1로 시작하는 수를 제외한 dp[i][j-1]-dp[i-1][j-1]이다. dp[65]까지 계산하면 이후 입력으로 주어지는 n 자릿수의 개수를 dp[n+1][0]으로 구할 수 있다. import sys..

아이디어 트라이를 이용하여 공통되는 먹이 정보를 저장한 후 DFS로 먹이 정보를 출력한다. 풀이 클래스로 구현한 트라이 trie를 생성하여 insert로 단어들을 트라이에 넣고, search로 개미굴의 시각화된 구조를 출력한다. 트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다. insert 메서드는 먹이들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성한다. search 메서드는 DFS로 정렬된 먹이 이름들에 차례로 깊이만큼 문자열 '--'을 더해 출력하는 함수 dfs를 호출한다. import sys input = sys.stdin.readline class Trie: def __init__(self): self.root = dict() def ..

아이디어 동적 계획법으로 고객 수에 따른 최소 비용을 계산한다. 풀이 #1 (Python) 0으로 채운 (N+1)×100 크기의 2차원 리스트 dp를 생성한다. dp[i][j]에는 i번 사람 차례에서 체력이 j일 때 얻을 수 있는 최대 기쁨을 저장한다. 이중 for문에서 체력이 0(인사를 한번도 하지 않은 경우)이거나 dp[i][j]에 저장된 값이 있을 때 현재 사람에게 인사한 후의 체력이 100 미만이면 인사한 후의 상태인 dp[i+1][j+L[i]]에 인사한 후의 기쁨을 저장하고, 인사하기 전과 비교해 인사하기 전의 기쁨이 더 크다면 dp[i+1][j]에 인사하기 전의 기쁨 dp[i][j]를 저장한다. import sys input = sys.stdin.readline N = int(input()) ..

아이디어 동적 계획법으로 중간 계산 결과가 0 이상 20 이하인 값들에 대한 경우의 수를 구해 나간다. 풀이 숫자의 개수를 N, 주어지는 숫자를 리스트 numbers에 입력 받는다. 0으로 채워진 (N-1)×21 크기의 2차원 리스트 dp를 생성하는데, dp[i][j]에는 i 번째 중간 계산 결과 j의 경우의 수를 저장한다. 처음 dp[0]의 첫 숫자의 위치에 1을 저장하고, for문에서 0 이상 20 이하의 중간 결과값의 경우의 수를 dp에 저장해 나간다. 마지막 계산 결과값이 주어진 마지막 숫자로 올바른 등식의 수 dp[-1][numbers[-1]]을 출력한다. def solution(): N = int(input()) numbers = tuple(map(int, input().split())) dp..

아이디어 세그먼트 트리로 구간 합을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다. 풀이 1275번 커피숍2 문제 풀이와 유사하다. 구간 합을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 0으로 채워진 트리 리스트 tree를 만든다. for문에서 a가 0이 아닌 경우(1인 경우) 해당 트리 리프 노드의 수를 변경한 후 함수 modify를 호출하고, a가 0인 경우 구간 합을 구하는 함수 sum_up을 호출하는데, b가 c보다 더 크다면 b와 c를 바꿔 c에 더 큰 값이 오도록 한다. 함수 update에서는 리프 노드의 부모 노드부터 루트 노드까지 다시 계산하고, 루트 노드를 벗어나면 종료한다. 함수 sum_up에서는 리프 노드에서부터 차례로 해당 노드의 부모 노드..

아이디어 동적 계획법으로 고객 수에 따른 최소 비용을 계산한다. 풀이 #1 (Python) 고객 수에 필요한 최소 비용을 저장하는 C+1 크기의 리스트 dp를 생성하고, 초기값을 비용 최댓값 100,000으로 채운다. for문에서 홍보 비용과 그 고객 수를 a와 b에 입력 받고, 고객 i명을 얻는 데 필요한 최소 비용 dp[i]를 갱신해 나간다. b의 배수 이하의 고객을 얻는 비용을 그에 맞는 a의 배수와 비교해 더 작은 값으로 갱신한다. 또 고객 수 i에서 b만큼의 고객을 홍보 비용 a로 얻었을 때의 비용인 dp[i-b]+a와 비교해 더 작은 값으로 갱신한다. import sys input = sys.stdin.readline def solution(): C, N = map(int, input().sp..

아이디어 덱을 이용하여 범위 내에서의 최솟값을 찾는다. 풀이 for문에서 현재 값이 덱 queue에서 가장 작은 값이 되도록 현재 값보다 큰 값들은 pop하여 없앤다. 범위를 벗어나는 값들은 popleft로 제거하는데, pop하여 남아 있지 않은 값이 있을 수 있으므로 A의 해당 값과 비교한다. res에 queue의 맨 앞에 있는 값을 문자열로 추가한 후, join 메서드로 공백으로 구분한 결과값을 출력한다. from collections import deque def solution(): N, L = map(int, input().split()) A = tuple(map(int, input().split())) queue = deque() res = [] for i in range(N): while q..

아이디어 동적 계획법으로 각 상담이 끝나는 시점의 최대 수익을 갱신해 나간다. 풀이 #1 (Python) N+1 크기의 0으로 채워진 리스트 dp를 생성하는데, dp[i]에는 i일째의 최대 수익을 저장한다. for문에서 T와 P를 입력 받아 어제 수익 dp[i]가 오늘 수익 dp[i+1]보다 큰 경우 오늘 수익에 어제 수익을 저장한다. 이번 상담이 끝나는 T-1일 후가 퇴사 전이고, 상담으로 얻는 수익이 T-1일 후의 예정 수익보다 더 크면 값을 갱신한다. import sys input = sys.stdin.readline def solution(): N = int(input()) dp = [0]*(N+1) for i in range(N): T, P = map(int, input().split()) if..