gaki gaki

플로이드와샬 class Solution: def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int: INF = 1e9 graph = [[INF] * n for _ in range(n)] for i in range(n): graph[i][i] = 0 #node1, node2, weight for [n1,n2,w] in edges: graph[n1][n2] = w graph[n2][n1] = w for k in range(n): for i in range(n): for j in range(n): graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) ret = 0 r..

1905. Count Sub Islands class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: n = len(grid1) m = len(grid1[0]) def dfs(r,c): nonlocal flag if (r = n or c = m or grid2[r][c] == 0): return ; grid2[r][c] = 0; if (grid1[r][c] != 1): flag = False dfs(r+1,c) dfs(r-1,c) dfs(r,c+1) dfs(r,c-1) cnt = 0; for i in range(n): for k in range(m): i..

class Solution: def numEnclaves(self, grid: List[List[int]]) -> int: n = len(grid) m = len(grid[0]) def dfs(r,c): if (r = n or c = m or grid[r][c] == 0): return ; grid[r][c] = 0; dfs(r+1,c) dfs(r-1,c) dfs(r,c+1) dfs(r,c-1) for i in range(n): for k in range(m): if ((i == 0 or i == n-1 or k == 0 or k == m - 1) and grid[i][k] == 1): dfs(i,k); cnt = 0; for i in range(1, n-1): for..

class Solution: def closedIsland(self, grid: List[List[int]]) -> int: n = len(grid) m = len(grid[0]) if (n = m or grid[r][c] == 1): return ; if ((r == 0 or r == n - 1 or c == 0 or c == m - 1) and grid[r][c] == 0): res = False; grid[r][c] = 1; dfs(r+1,c) dfs(r-1,c) dfs(r,c+1) dfs(r,c-1) cnt = 0; for i in range(n): for k in range(m): if (grid[i][k] == 0): res = True; dfs(i,k); if (res): cnt += 1; ..

[LeetCode] Max Area of Island 이 문제는 dfs 를 활용해서 풀 수 있는 문제이다. dfs 는 depth first search 의 약자로서, 그래프 탐색 알고리즘의 한 종류이다. 이름에서 알 수 있듯이 노드에서 연결된 노드가 있으면 계속 연결된 부분을 통해 이동하면서 그래프를 탐색한다. dfs 는 운이 좋을 경우 해를 빠르게 구할 수 있지만, 항상 최적의 해를 보장하지는 않는다. 또한 dfs 는 스택 자료구조를 사용하며 구현할 수 있다. (재귀의 동작이 스택과 똑같음) 해가 없는 경로에 깊게 빠질 수 있다. 따라서 예외처리를 잘 해주어야한다. class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: n = ..

[LeetCode] 773. Flood Fill DFS 로 풀 수 있는 문제이다. 나의 풀이 class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]: n = len(image) m = len(image[0]) visited = [[0] * m for _ in range(n)]; dx = [1,-1,0,0] dy = [0,0,1,-1] def dfs(r,c, targetColor, newColor): for _ in range(4): newR = r + dy[_] newC = c + dx[_] if (newR = n or newC < 0 o..

팰린드롬 알고리즘 안녕하세요. gaki 입니다. 오늘은 팰린드롬 알고리즘에 대해서 알아보겠습니다. 팰린드롬이란, 어떤 문자열을 거꾸로 뒤집었을때 원래의 문자열과 동일한 문자열을 의미합니다. 1. 팰린드롬 알고르즘 설명 - Two Pointer [time: O(N)] 2. 팰린드롬 알고리즘 응용 - DP 활용 [time: O(N^2)] 3. 팰린드롬 알고리즘 응용2 - Manacher's 알고리즘 [time: O(N)] 1. 팰린드롬 알고리즘 설명 팰린드롬 알고리즘은 말그대로 문자열이 팰린드롬인지 아닌지 구분하는 알고리즘 입니다. 예를들어 "RADAR" 라는 문자열이 있다고 합시다. 이 문자열은 거꾸로 뒤집어도 "RADAR" 이므로, 팰린드롬입니다. 그럼 어떤 문자열이 팰린드롬인지 알 수 있는 방법은 무엇..

안녕하세요. gaki 입니다. 오늘은 파이썬에서 리스트 안 원소의 개수를 세주는 함수 Counter() 에 대해서 이야기 해보려 합니다. 주로 리스트에서 특정 원소의 개수를 카운팅할 때 사용하곤 하는 함수입니다. 1. Counter 함수 설명 2. Counter 함수 예제 1. 파이썬 Counter 함수 설명 Counter 함수는 collections 라이브러리에 존재하는 함수 입니다. import collections 를 통해서 collections 라이브러리를 가지고 오고 Counter(arr ? : List) => counter(dict) 이런식으로 카운팅 하고 싶은 리스트를 인자로 입력하면 각 인자를 키로 가지고, value 에는 각 인자의 키가 리스트에 몇개 존재하는지 나타내주는 딕셔너리를 반환..