본문 바로가기

Algorithm475

[파이썬] 프로그래머스 : 석유 시추 (레벨2) [파이썬] 프로그래머스 : 석유 시추 (레벨2) https://school.programmers.co.kr/learn/courses/30/lessons/250136 풀이 방향성 생각 기본 BFS문제 각 덩어리 별로 BFS를 돌리고 덩어리에 포함된 x좌표에 그 덩어리 크기를 대응시킨다. oils[x] = [덩어리크기1, 덩어리크기2, ...] x에서 시추를 했을 때 덩어리들의 합이 가장 큰 것을 출력한다. 전체코드 from collections import deque, defaultdict as dd def solution(land): h,w = len(land),len(land[0]) dire = [(1,0),(0,1),(-1,0),(0,-1)] V = [[False]*w for _ in range(h).. 2024. 3. 2.
[파이썬] 코드트리 : 타워 부수기 (골드1) [파이썬] 코드트리 : 타워 부수기 (골드1) 포탑 부수기 | 삼성 SW 역량테스트 기출문제 (codetree.ai) 풀이 0. 방향성 생각 공격/수비 : 힙을 통해서 구현. 최대 100개의 정보에서 $logN$으로 빠르게 뽑는다. 레이저 길찾기 : 모듈러를 활용해서 경계선 이동하기. BFS로 탐색 레이저 공격 지점을 공격할 수 있을 경우, DFS로 길찾기. 지나온 경로에 모두 DMG//2만큼 빼주고, 공격 지점에는 (DMG//2 + 나머지) 한 번 더 뺀다. 폭탄 공격 공격 지점 9칸에 DMG//2만큼 빼주고, 공격 지점에는 (DMG//2 + 나머지) 한 번 더 뺀다. 건물 부수기 / 수리 맵 한 번 훑어주면서 좌표 업데이트 1. import, 전역 변수 설정 from collections import.. 2024. 2. 29.
[파이썬] 백준 2056 : 작업 (골드4) [파이썬] 백준 2056 : 작업 (골드4) https://www.acmicpc.net/problem/2056 풀이 방향성 생각 위상정렬 + DP. DP라고 하기엔 메모제이션이 크게 중요하지 않아서 위상정렬 위주 BFS를 사용해서 선행 작업들이 없는 노드에서 시작한다. 특정 노드에 필요한 선행 작업들이 모두 충족되면 해당 노드를 큐에 넣는다. 큐에 넣을 때는 최대값을 갱신해서 넣어준다. 해당 경로를 지나는 값 중 최대값을 넣어야한다. 전체코드 from collections import deque import sys input = lambda : sys.stdin.readline().rstrip() N = int(input()) T = [0]*(N+1) G = [[] for _ in range(N+1)] .. 2024. 2. 29.
[파이썬] 백준 10282 : 해킹 (골드4) [파이썬] 백준 10282 : 해킹 (골드4)) https://www.acmicpc.net/problem/10282 풀이 방향성 생각 방향 그래프 시작점이 주어지면 탐색을 통해서 각 노드에 도달하는 시간을 기록해야한다. 간선의 가중치가 다르니 다익스트라로 진행 전체코드 import sys import heapq as hq input = lambda : sys.stdin.readline().rstrip() INF = 1e9 def dijkstra(N,x): # 각 노드에 최대값 할당 visit = [1e9]*(N+1) visit[x] = 0 # 시작점 힙에 넣고 시작 heap = [] hq.heappush(heap,(0,x)) while heap: t,x = hq.heappop(heap) for nx,nt.. 2024. 2. 28.

티스토리툴바