Data Structure & Algorithms/Trees and Graphs13 [Graphs] Graphs-BFS- Shortest path 한달째 Tree 랑 Graph 짬짬이 공부중인데 양도 많고 그만큼 중요하단 뜻이겟지. graph문제에서 DFS를 쓰는 BFS를 쓰든 상관없지만 확실이 Shortest path문제에서는 BFS를 쓰는것이 좋다고한다. 방대한 Grid맵에서 목적지까지 가장 단기간의 경로를 찾는 경우를 생각해봤을때에 DFS를 쓰면 모든 맵 구석구석을 먼저 뒤지게될테니 불필요하니 로봇으로 부터 가까운곳부터 경로를 뒤지는 DFS가 효과적이다. https://leetcode.com/problems/shortest-path-in-binary-matrix/ Shortest Path in Binary Matrix - LeetCode Shortest Path in Binary Matrix - Given an n x n binary matr.. 2023. 2. 14. [Graphs] DFS.3- 1466. Reorder Routes to Make All Paths Lead to the City Zero https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/ Reorder Routes to Make All Paths Lead to the City Zero - LeetCode Can you solve this real interview question? Reorder Routes to Make All Paths Lead to the City Zero - There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network .. 2023. 2. 14. [Graphs] DFS.2 -Number of Islands https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Number of Islands - Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may ass leetcode.com 이번에는 Graph문제에서 인접행렬을 이용한 풀이를 알아보자. 구하고자 하는것 : 섬의 갯.. 2023. 2. 9. [Graphs] Graphs- DFS - Number of Provinces https://leetcode.com/problems/number-of-provinces/ Number of Provinces - LeetCode Number of Provinces - There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of d leetcode.com 이번에는 Graph에서 DFS 용으로 예제 문제풀이를 볼려고하는데 만만치가않다. 일.. 2023. 2. 8. [Graphs] 개념 공부 자 오늘은 새롭지만 트리와 비슷한 개념을 가진친구 Graphs를 공부해보자. 주목해야할만한 개념으로는 그전에 배웠던 Trees 의 상위범주라는것. 트리는 그래프에 많은 제한을 걸어서 특정 룰을 만든것에 지나지 않는다고한다. Terminology Edge of a node -Direct 혹은 undirect 가 있으며 전자는 한방향(A->B)으로 이동가능한것이며 후자는 양방향(AB)으로 이동가능 (Tip binaray tree에서는 위에서 아래로 내려올수밖에없는 direct 구조) Connected component - 연결된 노드의 그룹 Neighbors - 말그래도 붙어있는 노드들을 지칭.(parent 와 child 라는 말로 많이씀) Indegree , Outdegree - 전자의 말은 한노드에 pa.. 2023. 2. 7. [Tree] Binary Search Tree (BST) not BTS 오랜만에 다시 동기부여를 받고 코딩공부 !!! 오늘할것은 Binary Search Tree (BST) ! 값들을 저장할때 큰값과 작은 값을 좌우로 나누어 변경하여 굳이 전체를 찾을 필요가없는 데이터 구조 트리이다. 루트 노드 기준으로 찾고자하는값이 작으면 왼쪽 브랜치로 크면 오른쪽 브랜치로 이동하여 검색을 한다. 평균 시간은 O(logn) time on average, Worst time : O(n) 이며 이때는 linked list처럼 찾고자하는 값이 트리의 끝단 레벨에 있는경우이다. 팁* 위 그래프에서 Inorder search(DFS) 를 한다면 정렬된 숫자가 출력된다. 예제로 차근차근 따라가 보자 대표문제1.) 938. Range Sum of BST Given the root node of a b.. 2023. 2. 6. [Trees] Traversal 개념과 DFS, BFS 개념 혼동 정리 Tree 공부를 한 1주일째하는데 조각조각 배웠던것들의 퍼즐들이 조금씩 끼워 맞춰지는중. 아직 감이 다 안잡혔으나 오늘 헷갈렷던 개념중에 DFS(Depth First Search) vs BFS(Breath First Search) vs Traversal 개념이 혼동되어 큰 구조를 다시 잡아볼려한다. 내가 처음에 배웠던 1) In-order, 2) pre-order, 3) post-order 알고리즘의 개념은 DFS로 속하고 4) level-order traversal(Queue)를 사용하는것은 BFS 개념에 속한다. 이때 1,2,3) 알고리즘은 Recursion을 사용하지만 Stack을 사용해서도 나타낼 수 있다. DFS 의 이미지! 여기서 다시한번 그림으로 Traversal들의 개념을 잡고가보자 (맨날.. 2023. 1. 27. [Trees] Binary Tree Deletion 이해 이 노드 삭제구조 를 이해하는데 3일이 걸렸다.. 드디어 오늘 코드 작동 순서를 이해했는데 와 ART 그자체. 어떻게 이런 구조와 순서를 생각해냈지 대단할뿐. 왜 직접적으로 사용이안될수있지만 Data structure를 반드시 탄탄하게 공부하라는 이유를 알것같다. 음... 코드로 어떤 형상을 머리로 그려내는것은 정말 어려운일. 그림의 순서도로 코드 전체를 쉽게 한번에 이해할 수 있는 툴은 없을까. Ex) 코드가 한줄 한줄 넘어갈때마다 매치하면서 그 코드가 표현해내는 데이터 구조모형을 나타낸다면 정말 쉬워질텐데 임펙트 있게 정리할 방도가 마땅히 떠오르지않는다. 한줄 한줄 쓴다면 정리시간이 배로 걸릴것이고 흠. 매치해주는 툴이 있다면 좋을듯. Node* deletion(struct Node* root, in.. 2023. 1. 25. 이전 1 2 다음
