본문 바로가기

Algorithm/Data Structures39

[파이썬] SWEA 5653 : 줄기세포배양(test) [파이썬] SWEA 5653 : 줄기세포배양(test)SWEA 5653 : 줄기세포배양풀이방향성 생각힙을 사용해서 매 시각마다 이벤트를 처리하지 않고, 필요한 시점에만 이벤트를 계산하기.시간에 대해서는 최소힙을 사용한다.생명력 수치에 대해서는 최대힙을 사용한다.배열의 크기는 정해지지 않았으니, set을 사용해서 방문처리를 한다. 전체코드import heapq as hqdires = [(1,0),(0,1),(-1,0),(0,-1)]TC = int(input())for tc in range(1,TC+1): H,W,T = map(int,input().split()) arr = [list(map(int,input().split())) for _ in range(H)] V = set() he.. 2025. 4. 15.
[파이썬] 백준 11000 : 강의실 배정 (골드5) [파이썬] 백준 11000 : 강의실 배정 (골드5)https://www.acmicpc.net/problem/11000풀이방향성 생각정렬 + 스위핑/힙 전체코드import sysinput = sys.stdin.readlineN = int(input())arr = []for _ in range(N): s,e = map(int,input().split()) arr.append((s,1)) arr.append((e,-1))arr.sort()answer,cur = 0,0for _,new in arr: cur += new answer = max(answer,cur)print(answer)import heapq as hqimport sysinput = sys.stdin.readlineN .. 2025. 4. 6.
[파이썬] 백준 6549 : 히스토그램에서 가장 큰 직사각형 (플레5) [파이썬] 백준 6549 : 히스토그램에서 가장 큰 직사각형 (플레5)https://www.acmicpc.net/problem/6549풀이방향성 생각사실 문제를 보면 딱 봐도 세그트리 문제임을 대충 알 수 있다.할 줄 몰라서 모노톤 스택 / 유니온 파인드로 풀이.모노톤 스택같은 경우는, 배열을 순회하면서 이전에 가지고 있던 정보들을 기억해야한다는 점에서 떠올릴 수 있다.첫 번째는 인덱스, 두 번째는 이전 높이를 기억해야한다.이를 위해서, 스택에 튜플 형태로 넣어주기유니온 파인드의 경우는 큰 막대부터 점점 병합을 진행한다.작은 막대부터 병합하는 경우, 큰 막대와 결합하는 과정에서 그룹의 최소 높이가 잘못 갱신되는 문제가 발생한다.따라서, 큰 막대순으로 나오게 정렬을 진행하고, 인접 그룹들과 유니온 파인드를.. 2025. 4. 6.
[파이썬] 백준 1863 : 스카이라인 쉬운거 (골드4) [파이썬] 백준 1863 : 스카이라인 쉬운거 (골드4)https://www.acmicpc.net/problem/1863입력이 들어오면서 낮은 높이의 경우, 이전에 있었던 건물로 생각한다.스택이 비어있을 때 y>0인 건물이 들어오면 +1스택이 비어있지 않을 때, 더 작은 건물이 들어오면 스택에서 빼준다.스택의 마지막보다 더 큰 건물이 들어오면 +1예제에 건물 높이가 0이고 스택이 비어있는 경우에 +1 하는 예외가 발생해서 y가 양수인 경우에만 정답처리 해줬다. 방향성 생각전체코드import sysinput = lambda : sys.stdin.readline().strip()N = int(input())answer = 0stack = []for _ in range(N):x,y = map(int,input.. 2025. 3. 30.

티스토리툴바