흙금이네 블로그

아이디어 세그먼트 트리로 특정 범위에서의 최솟값을 저장해두고 찾는 범위에 대해 빠르게 처리한다. 풀이 2357번 최솟값과 최댓값 문제에서 최솟값만 고려하여 풀 수 있다. N보다 큰 2의 거듭제곱 중 가장 작은 값의 두 배 크기로 0으로 채워진 리스트 tree를 만든다. tree의 리프 노드들에 N개의 수를 입력 받고, for문에서 tree의 부모 노드들을 두 자식 노드 중 더 작은 값으로 저장한다. 값이 0인 자식 노드가 포함되어 있는 경우 부모 노드에 0이 아닌 자식 노드의 값을 저장한다. M개의 a, b 쌍을 입력 받아 함수 find를 호출하여 반환된 최솟값을 출력한다. 함수 find에서는 리프 노드에서부터 차례로 부모 노드로 올라가며 최솟값을 res에 저장한다. s%2 == 1 또는 e%2 == 0..

아이디어 거리가 먼 두 센서는 각각 다른 집중국과 통신하도록 한다. 풀이 #1 (Python) 오름차순 정렬된 센서 좌표를 리스트 sensor에 입력 받고, 센서 간 거리를 오름차순 정렬하여 리스트 D에 저장한다. N-1개의 센서 간 거리 중 가장 큰 값을 K-1개 제외할 수 있으므로 거리가 짧은 순으로 N-K개 값의 합을 출력한다. def solution(): N = int(input()) K = int(input()) sensor = sorted(map(int, input().split())) D = sorted([sensor[i+1]-sensor[i] for i in range(N-1)]) print(sum(D[:N-K])) solution() 풀이 #2 (JavaScript) 풀이 #1과 마찬가지..

아이디어 세그먼트 트리로 특정 범위에서의 최솟값과 최댓값을 저장해두고 찾는 범위에 대해 빠르게 처리한다. 풀이 N보다 큰 2의 거듭제곱 중 가장 작은 값의 두 배 크기로 0으로 채워진 리스트 min_tree를 만든다. min_tree의 리프 노드들에 N개의 수를 입력 받고, min_tree를 복제하여 max_tree로 저장한다. for문에서 min_tree와 max_tree의 부모 노드들을 각각 두 자식 노드 중 더 작은 값과 더 큰 값으로 저장해 나간다. min_tree에서 값이 0인 자식 노드가 포함되어 있는 경우 부모 노드에 0이 아닌 자식 노드의 값을 저장한다. M개의 a, b 쌍을 입력 받아 함수 find를 호출하여 반환된 최솟값과 최댓값을 언패킹하여 출력한다. 함수 find에서는 리프 노드에서..

아이디어 각 운동기구의 근손실 정도를 정렬하여 차례로 작은 값과 큰 값의 합 중 가장 큰 값을 출력한다. 풀이 #1 (Python) 근손실 정도를 오름차순 정렬 후 T에 저장하고, N이 홀수인 경우 결과값 res에 가장 큰 값을 pop하여 저장한다. for문에서 순서대로 작은 값과 큰 값의 합을 res와 비교하여 더 큰 경우 결과값을 갱신해 나간다. N = int(input()) T = sorted(map(int, input().split())) res = 0 if N%2: res = T.pop() for i in range(N//2): if T[i]+T[-(i+1)] > res: res = T[i]+T[-(i+1)] print(res) 풀이 #2 (JavaScript) 풀이 #1과 마찬가지 방식으로 동..

아이디어 세그먼트 트리로 구간 합을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다. 풀이 구간 합을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 0으로 채워진 트리 리스트 tree를 만든다. 트리의 리프 노드들에는 순서대로 N개의 수를 입력 받고, for문에서 각 부모 노드에 두 자식 노드의 합을 저장한다. 이후 for문에서는 a가 1인 경우 해당 트리 리프 노드의 수를 변경한 후 함수 update를 호출하고, a가 2인 경우 구간 합을 구하는 함수 sum_up을 호출한다. 함수 update에서는 리프 노드의 부모 노드부터 루트 노드까지 다시 계산하고, 재귀 호출로 루트 노드를 벗어나면 종료한다. 함수 sum_up에서는 리프 노드에서부터 차례로 해당 노드의 부모 ..

아이디어 양이 가장 많은 에너지 드링크에 나머지 에너지 드링크들을 모두 붓는다. 풀이 #1 (Python) N개의 에너지 드링크 양을 리스트 drink에 저장하고, 이들 합에 그 최댓값을 더하고 2로 나눈 값을 출력한다. N = int(input()) drink = tuple(map(int, input().split())) res = (sum(drink)+max(drink))/2 print(res) 풀이 #2 (JavaScript) 풀이 #1과 마찬가지 방식으로 동작한다. Math.max로 찾은 에너지 드링크 양 최댓값의 절반을 초기값으로 두고, reduce로 에너지 드링크들의 양을 반씩 더한다. const fs = require('fs'); const input = fs.readFileSync('/de..

아이디어 동적 계획법으로 두 문자열의 최장 공통 부분 열을 찾아 나간다. 풀이 두 문자열을 각각 S1, S2에 저장하고, 그 길이를 각각 N1, N2에 저장한다. 인덱스 접근의 편리를 위해 1만큼의 여유를 둬서 빈 문자열로 채워진 N2+1 길이의 리스트 dp를 생성한다. 메모리 절약을 위해 dp를 2차원 리스트로 만들지 않고, 현재 행에 대한 처리는 lcs에 하고 dp를 대체해 나간다. lcs[i+1][j+1]에는 S1의 i 번째 문자, S2의 j 번째 문자의 최장 공통 부분 열을 저장한다. S1, S2의 문자가 같을 때 해당 문자들 이전까지의 최장 공통 부분 열에 해당 문자를 더한 문자열을 저장하고, 그렇지 않으면 현재까지 저장된 부분 열 중 더 긴 부분 열의 문자열을 저장해 나간다. def solut..

아이디어 사전 순으로 가장 앞서는 수열이 되기 위한 규칙을 찾는다. 풀이 #1 (Python) 문어들이 1번과 2번 손을 번갈아 잡는 수열이 사전 순으로 가장 앞선다. 그러나 문어의 수가 홀수인 경우 1번과 2번 손만 사용해서는 원을 만들 수 없으므로 3번 손도 사용한다. 따라서 문어 수를 2로 나눠 소수점 이하를 버린 값만큼 1과 2가 담긴 리스트를 반복하고, 홀수면 3도 추가해 언패킹한다. N = int(input()) print(*[1, 2]*(N//2)+[3]*(N%2)) 문자열로 구현할 수도 있는데, 짝수인 경우 끝에 공백이 생기므로 rstrip 메서드로 공백을 제거한다. print(('1 2 '*(N//2)+'3'*(N%2)).rstrip()) 풀이 #2 (JavaScript) 입력으로 주어지..

자바스크립트의 비교 연산자는 보다 큼(>), 작음(=), 작거나 같음( 1); // true alert(2 == 1); // false alert(2 != 1); // true let result = 3 > 4; alert(result); // false 문자열은 유니코드 순으로 비교하며, 유니코드 순으로 인덱스가 더 큰 문자열이 더 크다고 판단된다. 두 문자열의 글자들을 차례로 비교하여 글자가 더 크거나 작은 문자열이 다른 문자열보다 크거나 작다고 판단되고, 비교가 끝날 때까지 결론이 나지 않으면 길이가 더 긴 문자열이 더 큰 것으로, 길이가 같다면 두 문자열은 같다고 판단된다. alert('Z' > 'A'); // true alert('Glow' > 'Glee'); // true alert('Bee'..

아이디어 동적 계획법으로 세 문자열의 최장 공통 부분 열의 길이를 찾아 나간다. LCS는 Longest Common Subsequence의 약자이기도 하고, Longest Common Substring의 약자이기도 하다. 부분 열(Subsequence)은 어떤 열의 요소들을 원래 순서에 따라 그 일부를 나열한 것이고, 부분 문자열(Substring)은 어떤 문자열 내에 포함된 연속적인 문자열을 의미한다. 따라서 최장 공통 부분 열과 최장 공통 부분 문자열은 공통 부분 요소들의 연속성에 차이가 있다. 부분 열은 연속되지 않은 요소들로도 구성할 수 있지만, 부분 문자열은 연속된 요소들로 구성된다. 이 문제에서는 각 문자열에서 일부 문자들을 순서대로 나열한 문자열 중 가장 긴 공통 문자열의 길이를 찾아야 한다..