목록CS (39)
소피it블로그
https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com from collections import deque class Solution: # grid, m, n은 bfs함수와 numIslands함수에서 모두 참조할 수 있도록 클래스 변수로 선언 grid: [[str]] m: int n: int def bfs(self, start_i, start_j)..
1. BFS: Breadth-First Search 너비 우선 탐색 BFS에서는 큐를 활용한다. 너비 우선 탐색이라는 개념과 FIFO의 특징을 생각해 보면 쉽게 이해할 수 있다. 큐를 사용하여 큐에 먼저 들어간 노드들을 먼저 팝해주는 것. from collections import deque def bfs(graph, node, visited): queue = deque([node]) # 첫 번째 노드로 큐를 만들어줌 visited[node] = True # 해당 노드 방문 기록 while queue: # 큐에 요소가 남아있는 동안 n = queue.popleft() # 큐의 앞에서 요소 빼줌 print(n, end = " ") # 해당 요소 출력 for i in graph[n]: # 해당 요소의 자식 ..
1. 버블 정렬 시간복잡도: O(n^2) # 기본 구현 def bubble_sort(arr): for i in range(len(arr) - 1, 0, -1): for j in range(i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] # 최적화: 스왑이 일어났는지 여부를 체크해줌으로써 정렬이 이미 완료되어있는 경우(즉 스왑이 일어나지 않은 경우) # 더 효율적으로 작동 def bubble_sort(arr): for i in range(len(arr) - 1, 0, -1): swapped = False for j in range(i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1..