본문 바로가기

Algorithm475

[파이썬] 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.
[파이썬] 백준 17472 : 다리 만들기 2 (골드1) [파이썬] 백준 17472 : 다리 만들기 2 (골드1)https://www.acmicpc.net/problem/17472풀이방향성 생각맵이 작고 섬의 수가 적어서 완탐가능MST로 풀이 시, 크루스칼로 그리디 하게 고르면 전부 탐색하지 않고 풀이 가능. 전체코드from collections import dequedires = [(1,0),(0,1),(-1,0),(0,-1)]inside = lambda x,y : 0 3: G.append([len(locs)-2,table[locs[0]],table[locs[-1]]])G.sort()P = [i for i in range(number)]def find(x): if x != P[x]: P[x] = find(P[x]).. 2025. 4. 12.
[파이썬] SWEA 5648 : 원자 소멸 시뮬레이션 (TEST) [파이썬] SWEA 5648 : 원자 소멸 시뮬레이션 (TEST)SWEA 5648 : 원자 소멸 시뮬레이션풀이방향성 생각각 공이 충돌할 좌표를 계산하는 방식으로 효율적으로 풀 수 있다.시뮬레이션으로 풀이.각 공의 좌표를 *2를 해준다.(0,0)에서 오는 공이랑 (1,0)에서 오는 공이 서로 충돌한다 했을 떄, 충돌 지점은 0.5인데 이런 부분을 int로 관리해주기(0,0)과 (2,0)에서 오는 공이 (1,0)에서 충돌각 시점에서 공의 좌표 -> 공의 정보를 리스트에 모두 저장하고, 리스트의 길이가 몇인지 관리해준다.각 공을 이동시킨 후, 특정 좌표에 2개 이상의 공이 있으면 그 공의 에너지를 전부 더해주고 정보를 제거한다.info가 없어질 때 까지 반복하기좌표를 벗어나면 각 공들은 다른 공과 충돌하지 않.. 2025. 4. 12.
[파이썬] 백준 12738 : 가장 긴 증가하는 부분 수열3 (골드2) [파이썬] 백준 12738 : 가장 긴 증가하는 부분 수열3 (골드2)https://www.acmicpc.net/problem/12738풀이방향성 생각배열 크기가 10^6이라 N^2 DP풀이로는 불가능.LIS의 길이를 구하는 NlogN으로 풀이 전체코드import sysinput = sys.stdin.readlineN = int(input())LIS = []for val in map(int,input().split()): if not LIS or val > LIS[-1]: LIS.append(val) continue l,r = -1,len(LIS) while l+1코멘트bisect 쓰는 코드가 확실히 더 빠른듯. 2025. 4. 10.

티스토리툴바