hyunkookim 님의 블로그

1. DFS 성질을 이용한 연결 요소 탐색Easy 난이도Problem 1: Number of Islands (LeetCode 200)설명: 2D 그리드에서 '1'로 표시된 섬의 개수를 찾는 문제입니다. DFS를 사용하여 연결된 '1'들을 탐색해 섬의 개수를 계산합니다.핵심 개념: DFS, 2D 그리드 탐색Problem 2: Flood Fill (LeetCode 733)설명: 시작 픽셀과 연결된 모든 픽셀을 탐색하여 색을 변경하는 문제입니다. DFS를 통해 인접한 픽셀을 처리합니다.핵심 개념: DFS, 색칠 알고리즘Problem 3: Max Area of Island (LeetCode 695)설명: 2D 그리드에서 가장 큰 섬의 면적을 계산합니다. DFS로 연결된 '1'의 크기를 탐색합니다.핵심 개념: D..

1. BFS 큐 기반 위상 정렬 (Topological Sort using BFS - Kahn's Algorithm)Problem 1: Course Schedule III (LeetCode 630)설명: 주어진 수업들을 듣기 위한 최소 시간으로 완료할 수 있는 최대 수업 수를 구하는 문제입니다. BFS 기반의 위상 정렬을 사용하여 해결할 수 있습니다.핵심 개념: 위상 정렬, 큐, 진입 차수 (in-degree), 최적화Problem 2: Reconstruct Itinerary (LeetCode 332)설명: 공항 여행 계획을 재구성하는 문제입니다. 각 공항에서의 출발지와 도착지가 주어지며, 위상 정렬을 사용하여 경로를 찾습니다.핵심 개념: 그래프, 위상 정렬, 큐, 경로 탐색Problem 3: Task ..

1. BFS 큐 기반 위상 정렬 (Topological Sort using BFS - Kahn's Algorithm)Problem 1: Course Schedule (LeetCode 207)설명: 수업들 간의 선후 관계를 바탕으로 모든 수업을 듣기 위한 가능한 순서를 찾는 문제입니다. 위상 정렬을 사용하여 해결할 수 있습니다.핵심 개념: 큐, 진입 차수 (in-degree), 위상 정렬Problem 2: Course Schedule II (LeetCode 210)설명: Course Schedule 문제와 비슷하지만, 가능한 수업 순서를 반환하는 문제입니다. BFS를 사용하여 위상 정렬을 수행하여 순서를 구합니다.핵심 개념: 큐, 진입 차수, 위상 정렬, 수업 순서Problem 3: Alien Dictio..

완벽한 해싱n개가 n개의 버킷에 하나씩 따로따로 저장된다면 완벽한(perfect) 해싱이라고 볼 수 있습니다. 입력 데이터가 뭔지를 모두 알고 있을 경우에만 가능합니다. 예를 들어서 입력 키가 "Apple", "Orange", "Kiwi" 3가지라고 고정이 되어있다면 각각 0, 1, 2에 대응시키면 메모리 낭비 없이 O(1)으로 처리할 수 있습니다.대부분의 경우에는 입력이 정확히 어떤 것들이 들어올지 미리 알 수가 없기 때문에 충돌이 최소가 되는 좋은 해시 함수를 사용할 필요가 있습니다. 유니버설 해싱유니버설 해싱이라는 이름 보다는 "랜덤 해싱"이라는 이름이 더 이해하기 쉬울 것 같습니다. 난수를 사용하는 무작위 알고리듬이 성능을 높이는 데에 도움이 된다는 것은 앞에서 퀵 정렬에서 본 적이 있습니다. 여..

생일 문제 https://ko.wikipedia.org/wiki/%EC%83%9D%EC%9D%BC_%EB%AC%B8%EC%A0%9C 생일 문제 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 모인 사람 수에 따라 생일이 같은 두 사람이 있을 확률이 얼마나 되는지를 보이는 그래프. 가로축이 사람 수,그리고 세로축이 확률을 나타낸다. 23명이 모였을ko.wikipedia.org **생일 문제 (Birthday Problem)**는 통계학에서 유명한 문제로, 적은 수의 사람들이 있을 때도 두 사람이 같은 생일을 가질 확률이 놀랍게 높다는 것을 보여줍니다.문제 정의문제:n명이 있을 때, 이들 중 최소한 두 명이 같은 생일을 가질 확률을 계산합니다.생일은 1년이 365일로 가정하며 균등하게 분..

DFS : 깊이 우선 탐색 BFS: 넓이 우선 탐색   구현 방법방문한 노드는 다시 방문 X모든 노드를 다 탐색https://youtu.be/CUTXL4NFTGE?si=AdqhxDTmJRQfyjPY

탐욕 알고리즘 (Greedy Algorithm)탐욕 알고리즘은 문제를 해결할 때 현재 단계에서 가장 최적의 선택을 반복적으로 수행하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. 이 알고리즘은 항상 **국소적 최적해(Local Optimal Solution)**를 선택하며, 이를 통해 최종적으로 **전역적 최적해(Global Optimal Solution)**를 구하려고 시도합니다.탐욕 알고리즘의 특징단계별 최적 선택:매 단계에서 그 순간 가장 최적인 선택을 합니다.이전 단계의 선택에 대해 다시 돌아가서 바꾸지 않습니다. (비가역적)문제의 구조적 특성 필요:탐욕 알고리즘이 최적해를 보장하려면 문제에 특정한 성질이 있어야 합니다:Greedy Choice Property (탐욕 선택 속성):현재 단계..

단조 스택(Monotonic Stack) **Monotonic Stack(단조 스택)**은 스택 자료구조를 활용하여 특정 조건을 만족하는 값을 효율적으로 찾는 알고리즘 기법입니다. 주로 배열이나 리스트에서 다음 큰 값(Next Greater Element), 다음 작은 값(Next Smaller Element) 등을 찾는 문제에서 사용됩니다.Monotonic의 의미"Monotonic"은 단조라는 뜻으로, 값이 항상 증가하거나 감소하는 특성을 가집니다.Monotonic Stack에서는 스택 안에 들어 있는 값들이 다음 두 가지 조건 중 하나를 만족하도록 유지합니다:단조 증가 스택 (Monotonic Increasing Stack):스택에 값이 쌓일수록 값이 커지거나 같음.즉, 스택의 위쪽에 있는 값이 아래..

Leetcode 75 질문 유형 및 유투브 솔루션 링크 정리 https://docs.google.com/spreadsheets/d/1BiY_cRfXI9yJPaU75RFcfVRN2OF1CilpiwX5cdHXRoU/edit?usp=sharing  김현구: Leetcode 75 Questions (NeetCode on yt)trick: I though use trie to store the grid, reverse thinking, instead store dictionary words, dfs on each cell, check if cell's char exists as child of root node in trie, if it does, update currNode, and check neighbors..

https://youtu.be/ZNa9-86uVEA?si=gW5g_NFuih1V9T4I