최소 Heap

2023년 8월 2일 알고리즘 문제풀이 백준 11000 문제 링크 1차 시도 나의 생각 각 수업을 시작하는 시간을 기준으로 정렬하되, 끝나는 시간을 heap에 넣는다. 반복문으로 순회하며 지금 시작할 수업의 시간이 배열에 들어있는 수업 중 끝나는 시간이 가장 빠른 수업의 종료 시간과 비교하였다. 종료 한 후 시작되면 추가적인 강의실이 필요 없다. 하지만 수업이 끝나지 않은 채 다음 수업이 시작된다면 새로운 강의실이 필요하다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import sys from heapq import heappush, heappop, heappushpop n = int(sys.stdin.readline()) classes = [] for _ in range(n): s,t = map(int,sys.stdin.readline().split()) classes.append([s,t]) classes.sort() heap = [] cnt = 1 for i in range(n): now_class = classes[i] if not heap: heappush(heap,now_class[1]) else: while heap: end_time = heap[0] if now_class[0] >= end_time: heappop(heap) else: break heappush(heap,now_class[1]) cnt = max(cnt,len(heap)) print(cnt)

2023년 7월 30일 알고리즘 문제풀이 백준 5904번 문제 링크 1차 시도 나의 생각 재귀 함수를 통해 각 문자열을 구할 수 있었다. 또한 그 문자열의 길이도 규칙적이므로 몇번째 재귀에서 n번째 문자열이 등장하는지를 알아내어 그 문자열의 index를 통해 구하였다. 하지만 메모리 초과와 시간 초과로 인하여 오답처리 되었다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys sys.setrecursionlimit(10**6) n = int(sys.stdin.readline()) def moo(k): if k == 0: return 'moo' return moo(k-1)+'m'+'o'*(k+2)+moo(k-1) i = -1 while True: i += 1 tmp = moo(i) if len(tmp) >= n: print(tmp[n-1]) break 2차 시도 나의 생각 문자열을 구하면 안된다고 생각하였다. 다음 문자열이 이전 차례의 문자열 두개에 하나의 규칙적인 문자가 껴있는 형태라는 사실에 집중하였다. 예를 들어 S(10)의 몇번째 문자열인지는 S(9)의 문자열을 통해 알 수 있다. 원리는 다음과 같다. ...