본문 바로가기

전체 글51

[LeetCode] 802. Find Eventual Safe States (파이썬/python) 🎈문제 https://leetcode.com/problems/find-eventual-safe-states/description/ 🎁어떤 알고리즘? 1. 각 node가 terminal node로 끝나는지 순환하는지를 확인해야 하므로 DFS를 이용한다. 💻코드 class Solution(object): def eventualSafeNodes(self, graph): # 2. dfs를 이용해 끝까지 타고 가서 해당 노드가 safe node인지 판별 def dfs(i): if i in safe: return safe[i] safe[i] = False for neighbor in graph[i]: if not dfs(neighbor): return False safe[i] = True return True n .. 2023. 8. 7.
[백준] 1463 1로 만들기 (파이썬/python) dp, bfs 🎈문제 https://www.acmicpc.net/problem/1463 🎁어떤 알고리즘? 1. bfs, dp 2. 사실 가장 먼저 생각난 것은 bfs이다. 1차원 리스트에서 “최소 몇번 ~를 해야하는지 구하시오”와 같은 문제가 나왔을 경우 bfs를 떠올릴 수 있도록 공부했기 때문이다. 3. 하지만 이 문제의 경우 dp를 이용하면 더 빠르게 동작한다. bfs : 852ms dp : 644ms 4. 밑에 dp와 bfs로 모두 풀어보고 자세한 설명을 첨부했다. 💻 dp 코드 # 1463 1로 만들기 (dp 사용) # 1. 입력 받기 n = int(input()) dp = [0 for _ in range(n+1)] for i in range(2,n+1): dp[i] = dp[i-1] + 1 ''' 우리는 1부.. 2023. 8. 3.
[백준] 7576 토마토 (파이썬/python) 🎈문제 https://www.acmicpc.net/problem/7569 🎁어떤 알고리즘? 1. 인접한 토마토가 익게 만드므로 bfs를 사용해야겠다고 판단함 2. 시작점이 여러개인 bfs 문제의 경우, 시작점을 모두 큐에 넣고 bfs를 돌리는 것이 핵심이다. 💻코드 # 7576 토마토 from collections import deque def bfs(): # 상하좌우 좌표 설정 dx = [0,0,-1,1] dy = [1,-1,0,0] while deq: x,y = deq.popleft() # 큐에서 익은 토마토 좌표 꺼내기 for i in range(4): # 상하좌우 탐색 시작 nx = x + dx[i] ny = y + dy[i] # graph 벗어난 좌표는 무시 if nx (n.. 2023. 8. 2.
[백준] 1992 쿼드트리 (파이썬/python) 🎈문제 https://www.acmicpc.net/problem/1992 🎁어떤 알고리즘? 1. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 총 4개의 영역을 압축한다는 부분에서 분할 정복, 재귀 알고리즘임을 깨달았다. 💻코드 # 1992 쿼드트리 # 3. 영상 압축 합수 만들기 # x: 세로, y: 가로 def compress(x,y,n): start = video[x][y] # 시작 지점의 색 저장해두기 for i in range(x,x+n): for j in range(y,y+n): if video[i][j] != start: # 다른색 나오면 start = -1 break if start == -1: print('(',end='') div_n = n//2 # 4개의 영상으로 나누기 # 4 부분.. 2023. 7. 12.

티스토리툴바