흙금이네 블로그

아이디어 회의 시간을 정렬하여 회의 시간이 겹치면 회의실 수를 증가시킨다. 풀이 #1 (Python) 회의 시작 시간과 끝나는 시간을 튜플로 오름차순 정렬하여 리스트 meeting에 저장한다. 리스트 time은 회의가 끝나는 시간들을 최소 힙의 형태로 저장하며, 처음에는 첫 회의가 끝나는 시간을 저장한다. for문에서는 두 번째 회의부터 시작 시간과 끝나는 시간을 각각 s와 e로, 가장 빨리 끝나는 이전 회의 시간을 t로 둔다. e를 우선 time에 추가한 후 s와 t를 비교해 회의 시간이 겹치면 t를 다시 추가하고, 그렇지 않으면 t는 time에서 제거한다. import sys, heapq input = sys.stdin.readline def solution(): N = int(input()) mee..

아이디어 전깃줄이 교차하지 않으려면 전깃줄들이 연결된 A의 위치 값이 증가할 때 B의 위치 값도 증가해야 한다. 따라서 전깃줄들을 A의 위치 값 기준으로 오름차순으로 정렬하고, B의 위치 값이 증가하는 가장 긴 수열의 길이를 구한다. 풀이 전깃줄이 연결된 A의 위치 값과 B의 위치 값을 튜플로 리스트 line에 저장하고, line을 오름차순 정렬한다. 1로 채워진 N 크기의 리스트 dp를 생성하고, dp에 증가하는 수열의 가장 긴 길이를 저장해 나간다. j 번째 전깃줄이 연결된 B의 위치 값이 i 번째 전깃줄이 연결된 B의 위치 값보다 크고, dp[i]+1와 비교해 dp[j]를 갱신한다. 마지막에 전체 전깃줄 개수 N에서 가장 긴 증가하는 수열의 길이 max(dp)를 뺀 값을 출력한다. import sy..

아이디어 세그먼트 트리로 특정 범위에서의 최솟값을 저장해두고 찾는 범위에 대해 빠르게 처리한다. 풀이 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) 입력으로 주어지..