[분할정복] LeetCode 14 - Longest Common Prefix
class Solution: def merge(self, left, right): result = "" min_len = min(len(left), len(right)) for i in range(min_len): if left[i] == right[i]: result += left[i] else: return result return result def divideConquer(self, arr, low, high): if low >= high: return arr[low] m = (low + high) // 2 leftStr = self.divideConquer(arr, low, m) rightStr = self.divideConquer(arr, m + 1, high) return self.merge..
2021. 3. 16.
[BOJ 1012 유기농배추] BFS와 DFS로 풀기 (python)
문제조건 연결요소(덩어리)의 개수를 찾는다. 가로, 세로와 행열 인덱스 주의하자. 핵심개념 pypy는 최대 재귀깊이가 10만으로 설정되어 있다. 이걸 넘으면 런타임에러가 발생한다. sys.setrecursionlimit(10**6) 100만으로 늘려준다. (참ㅋㅋㅋㅋㅋ) DFS가 BFS보다 메모리를 적게 쓰긴 하는구나. 코드 DFS (메모리 30276 KB) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] import sys sys.setrecursionlimit(10**6) #재귀 깊이 설정 (10만 -> 100만) def dfs(x, y, _cnt): dist[x][y] = _cnt for k in range(4): nx, ny = x+dx[k], y+dy[k] if 0
2019. 10. 14.
[SWEA] 구슬탈출 2
문제조건 빨간구슬, 파란구슬 두 개가 동시에 위치 이동을 한다. (정점의 위치가 변한다!) 빨간구슬, 파란구슬은 같은 위치에 있을 수 없다. (장애물정점의 위치도 변한다!) 한 번 이동 시, 갈 수 있을 때까지 쭈욱 간다. 핵심개념 BFS에서 queue에는 x,y 좌표 한 개만 담으라는 법은 없다. 빨간구슬의 (x,y), 파란구슬의 (x,y)를 같이 담는다. 종료조건을 먼저 생각하자. 1) 움직인 횟수 10번 넘었거나 (실패) 2) 10번 안 넘었지만 탈출할 수 없거나 (실패) 3) 빨간구슬이 탈출에 성공했거나 코드 from collections import deque n, m = map(int, input().split()) a = [list(map(str, input())) for _ in range..
2019. 10. 9.
