흙금이네 블로그

아이디어 회의 시간을 정렬하여 회의 시간이 겹치면 회의실 수를 증가시킨다. 풀이 #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..