Data Structure & Algorithms47 [Greedy] 첫 그리디한 개념시작 유명한 그리디 알고리즘을 드디어 시작해보는군. 배워야 살아남느니라~ Greedy 알고리즘은 local optimal choice를 매 단계마다 선택해 나아가는것. local 의 의미는 매 반복문마다 즉각적으로 선택할 수 있는 선택을 뜻하며 optimal은 문제가 무엇을 묻느냐에따라 다르지만 만약 문제가 두 요소들의 최대합을 원한다면 가장큰 두개의 값을 선택하는것과같다. Most greedy problems will be asking for the maximum or minimum of something. 그리드 문제들 단어뜻 그대로 '욕망'이 가득한 선택이라고 볼수있다. 국소적으로 최대한 나의 이익을 최대로 할 수 있는 선택을 계속해서 해나간다는 뜻으로 해석할 수 있다. 많은 heap 관련 문제들이 그리.. 2023. 2. 22. [Heaps] Leetcode347.Top K Frequent Elements https://leetcode.com/problems/top-k-frequent-elements/ Top K Frequent Elements - LeetCode Top K Frequent Elements - Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: leetcode.com 자 다시 꾸준하게 자료구조/알고리즘의 늪으로 빠져보자. 구하고자하는것: k .. 2023. 2. 22. [Heaps] heap 개념알아보기 출처: leetcode 힙이란 데이터를 저장하는 컨테이너로 Priority queue 로도 불린다. 다음과같은 오퍼레이션이있다. Add an element in O(logn) Remove the minimum element in O(logn) Find the minimum element in O(1) *힙으로는 최대 요소값을 찾을수있으며 최대값을 찾거나 제거할때는 max heap이라불리면 최소값을 찾거나 제거할때는 min heap이라 불린다. Implementation 해쉬맵과 같이 힙도 대부분의 프로그램 언어에서 기본적 라이브러리가 제공되기 때문에 굳이 작동 코드를 알아야할 필요는 없지만 인터페이스를 이해해야한다. 허나 인터뷰에서는 해쉬맵과는다르게 heap의 implementation을 알아야한다. .. 2023. 2. 15. [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. 이전 1 2 3 4 5 6 다음
