hyunkookim 님의 블로그

AND 연산: & OR 연산: |XOR 연산: ^NOT 연산: ~Shift 연산>> : right shift: / 2 나누기 연산(버림)

m x n 의 2D 행렬(matrix) 문제에서  - Brute Force 알고리즘 (DFS 사용) => Time: O(2^(n+m)), Space: O(n+m) dfs, 재귀 사용# Brute Force - Time: O(2 ^ (n + m)), Space: O(n + m)def bruteForce(r, c, rows, cols): if r == rows or c == cols: return 0 if r == rows - 1 and c == cols - 1: return 1 return (bruteForce(r + 1, c, rows, cols) + bruteForce(r, c + 1, rows, cols))print(bruteFo..

684. Redundant Connection https://youtu.be/FXWRE67PLL0?si=09q1EDMfBhbMNpJk class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: # Union-Find 알고리즘으로 사이클을 형성하는 간선을 찾는 함수 # Use Union-Find algorithm to find the edge that creates a cycle. n = len(edges) # 간선의 개수 (Number of edges) # 부모 노드를 저장하는 배열 (Parent array to store parent ..

323. Number of Connected Components in an Undirected Graph 내 풀이class Solution: def countComponents(self, n: int, edges: List[List[int]]) -> int: # 그래프를 인접 리스트로 표현 (Represent the graph as an adjacency list) hashMap = {i: [] for i in range(n)} # 각 노드 i를 키로, 빈 리스트를 값으로 초기화 (Initialize each node with an empty list) for n1, n2 in edges: # 간선 정보를 순회하며 그래프를 채움 (Iterate over ed..

142. Linked List Cycle II 이 문제는 Linked List Cycle Detection 문제 중 하나로,**Floyd's Cycle Detection Algorithm (Tortoise and Hare)**를 활용하여 해결할 수 있습니다.아래는 단계별 풀이 방법입니다.1. Floyd’s Cycle Detection Algorithm두 포인터(Tortoise와 Hare)를 사용하여 Linked List를 순회합니다.속도 차이를 이용해 두 포인터가 같은 노드에 도달하면 사이클이 있음을 확인할 수 있습니다.사이클이 발견되면, 사이클의 시작 노드를 찾는 추가 작업을 수행합니다.2. 단계별 풀이1단계: 사이클 존재 여부 확인slow 포인터는 한 번에 한 노드씩 이동합니다.fast 포인터는 한 ..

997. Find the Town Judge class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int: # 1. 그래프를 인접 리스트로 생성 adj = {i: [] for i in range(1, n + 1)} # 신뢰 관계 for a, b in trust: adj[a].append(b) # a가 b를 신뢰 # 2. 판사 후보 선정 # 판사는 누구도 신뢰하지 않아야 하므로, 신뢰 관계가 없는 노드를 후보로 선정 candidates = [i for i in range(1, n + 1) if not adj[i]] if..

1971. Find if Path Exists in Graph class Solution: def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: # 양방향 그래프를 인접 리스트로 생성 adj = {i: [] for i in range(n)} for n1, n2 in edges: adj[n1].append(n2) adj[n2].append(n1) # 방문한 노드를 추적하기 위한 집합 visit = set() # DFS 함수 정의 def dfs(i): ..

261. Graph Valid Tree https://youtu.be/bXsUuownnoQ?si=hDkFB87rMA-fL6M4 class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: # 만약 노드의 개수가 0이라면, 빈 트리로 간주되므로 True 반환 # If there are no nodes (n == 0), it's considered a valid empty tree. if not n: return True """ 유효한 트리가 되기 위한 조건 (Valid Tree Conditions): 1. 노드 개수 - 1 == 간..

위상 정렬(Topological Sort)란?위상 정렬은**유향 비순환 그래프(DAG, Directed Acyclic Graph)**에서 노드들을 선행 관계에 따라 순서대로 정렬하는 알고리즘입니다.특징선행 관계를 보장:노드 A에서 B로 가는 간선이 있다면, 정렬 결과에서 A는 항상 B보다 먼저 나옵니다.**DAG(Directed Acyclic Graph)**에서만 수행 가능:싸이클이 있는 그래프에서는 위상 정렬이 불가능합니다.예제입력 그래프:간선: [[1, 0], [2, 0], [3, 1], [3, 2]]설명: 0은 1과 2의 선행 조건이고, 1과 2는 3의 선행 조건입니다.위상 정렬 결과:가능한 정렬: [0, 1, 2, 3] 또는 [0, 2, 1, 3]위상 정렬 알고리즘Kahn's Algorithm:진..

417. Pacific Atlantic Water Flow 이 문제는 두 개의 대양(태평양과 대서양) 모두로 물이 흐를 수 있는 위치를 찾는 것입니다. 각 셀의 물은 다음 조건을 만족할 때 이동합니다:인접한 셀의 높이가 현재 셀보다 작거나 같아야 합니다.물이 태평양과 대서양의 경계에서 시작하여 거꾸로 퍼져 나가야 효율적으로 풀 수 있습니다.문제를 해결하기 위한 접근 방식거꾸로 흐르는 관점(BFS/DFS):태평양과 대서양의 경계에서 각각 시작하여 물이 역으로 퍼져 나가는 방식으로 탐색합니다.각각의 대양에 도달할 수 있는 셀을 계산하고, 두 대양 모두에 도달 가능한 셀을 찾습니다.탐색 방향:네 방향(상, 하, 좌, 우)으로 이동하면서 물이 흐를 수 있는지 확인합니다.조건: height[다음 셀] >= hei..