❒ Description프로그래머스 Lv3. 순위 문제를 풀면서 알게된 Floyd Warshall 알고리즘에 대해서 학습하자. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr      ❒ Floyd Warshall 알고리즘Floyd warshall 알고리즘은 모든 노드간의 최단 경로 탐색이 필요한 경우에 사용한다.음의 가중치가 있어도 사용할 수 있으며, O(v³)의 시간 복잡도를 갖는 알고리즘이다.  Floyd warshall 알고리즘의 핵심 아이디어는 거쳐가는 정점을 기준으로 최단거리를 구하는 것이다. 거쳐가는 정점을 A로 하게 경로는 `C → A → B`,..

❒ Description제목게임 맵 최단거리링크https://school.programmers.co.kr/learn/courses/30/lessons/1844자료구조/알고리즘Map, Queue / 넓이 우선 탐색(BFS)시간 복잡도 O(row수 * col수)  BFS를 사용해서 해결 할 수 있는 문제이다. 문제의 핵심 포인트는 maps[row][col] 값을 업데이트 해주는 부분이다.시간 복잡도의 경우는 모든 노드를 한 번씩 방문하기 때문에 O(N*M)의 시간 복잡도를 갖는다.     ❒ Solution더보기import java.util.LinkedList;import java.util.Queue;class Solution { private final int[][] dirs = {{-1, 0}, {..

❒ Description제목Cheapest Flights Within K Stops링크https://leetcode.com/problems/cheapest-flights-within-k-stops/description/자료구조비선형 (그래프) - 최단거리시간 복잡도O(ElogV)다익스트라 알고리즘을 사용해서 풀 수 있는 문제이며, Comparable 인터페이스도 활용할 수 있다.이 문제는 경유 횟수가 제한되어 있어서 굉장히 까다로웠다.     ❒ Solution1.  단순 solvepublic int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { //1. filghts 배열을 통해 graph 생성 List> graph..

❒ Description743. Network Delay Time 문제를 풀면서 Dijkstra 알고리즘을 복습했다. 이 알고리즘은 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.  풀이방법은 총 3가지 였다.배열 내에서 선형탐색 + 배열 내에 중복 정점 허용하지 않음우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용하지 않음우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용  ※ 참고나무위키(다익스트라 알고리즘)을 보면 잘 정리되어 있어서 별도로 정리하지 않음. 소스 코드 : 링크  관련 문제743. Network Delay Time787. Cheapest Flights Within K Stops778. Swim in Rising Water815. Bus Rou..

❒ DescriptionCourse Schedule 문제를 풀면서 위상 정렬을 사용하는 풀이 방법을 알게 됐다. [ 같이 참고하면 좋은 문제들 ]※ 2024.09.24 추가 : [LeetCode#310] Minimum Height Trees   ❒ DAG (Directed Acyclic Graph)위상 정렬에 대해 공부하기 전 DAG에 대해서 알아보자. 1. 정의유향 비순환 그래프 또는 방향 비순환 그래프는 컴퓨터 과학 분야의 용어로 하나로서, 방향 순환이 없는무한 유향 그래프이다. 이해하기 쉽게 표현하면, 모든 간선들은 방향을 가지고, 어떠한 노드에서 출발해도다시 그 노드로 돌아오는 순환이 존재하지 않는 그래프다. DAG의 특성은 다음과 같다. Directed (유향성)그래프의 각 간선이 방향을 가진다..

❒ Description제목Course Schedule링크https://leetcode.com/problems/course-schedule/description/자료구조비선형 (그래프)시간복잡도위상정렬 : O(v+e) 이번 문제는 재귀로도 풀수 있지만, Topological Sorting 알고리즘을 사용해서도 풀수 있는 문제다.   ❒ Solution1. 재귀 구조public boolean canFinish(int numCourses, int[][] prerequisites) { Map> finishToTakeMap = new HashMap(); for (int[] prerequisite : prerequisites) { finishToTakeMap.putIfAbsent(prere..

❒ Description제목Permutation링크https://leetcode.com/problems/permutations/description/자료구조비선형 (그래프)시간복잡도 O(n!)Permutation(순열)이란, 모든 가능한 경우를 그래프 형태로 나열한 결과라고 할 수 있다.이 문제는 BackTraking을 통해서 해결하는 문제인데, 모든 가능한 순열을 생성하기 때문에nums의 크기가 커질수록 시간이 급격히 증가한다. ❒ Solution1. Solution1public class Solution { public List> permute(int[] nums) { List> results = new ArrayList(); List elements = Arrays.s..

❒ Description제목완주하지 못한 선수링크https://school.programmers.co.kr/learn/courses/30/lessons/42576자료구조선형 (해시)시간복잡도O(n + k)이번 문제는 해시맵을 사용하여 간단하게 해결 할 수 있는 문제인데 다른 풀이에서 HashMap을 생성할 때 Stream을 이용한 풀이가 있어서 메모.   ❒ Map 생성Code 1다음과 같은 배열 `"A", "B", "C", "A", "C", "A"`에서 각 요소가 몇 번 나왔는지를 Map 자료구조로 표현할 때나는 주로 아래와 같이 코드를 작성했다.Map counter = new HashMap();for (String name : students) { counter.put(name, counter.get..

❒ Description제목K Closest Points to Origin링크https://leetcode.com/problems/k-closest-points-to-origin/description/자료구조선형 (우선순위 큐)시간복잡도O(nlogn) 이번 문제는 우선순위 큐를 사용하여 해결하는 문제이다. Sort, Heap, Quick Select를 사용하는구현도 있는데 이것에 대해서는 해당 섹션 공부할 때 같이 볼 예정이다. 이 문제는 Comparator와 Comparable 중 하나를 사용해서 우선순위를 결정해줘야 한다.Comparator를 통해서 우선순위를 정해줄 경우 main method에서 `Comparator#compare`메서드를제정의 해줘야해서 DDD에 어긋난다. 반면에 Comparabl..

❒ Description제목Merge K sorted Lists링크https://leetcode.com/problems/merge-k-sorted-lists/description/자료구조선형 (우선순위 큐)시간복잡도O(nlogk) 이번 문제에서도 가상의 노드 Root를 사용되었다. 이쯤 느껴지는 것은 뭔가 정렬이 들어가는경우에는 가상의 노드 접근을 생각해보는 것도 좋은 거 같다. 아무튼 문제의 핵심은 자료구조 Priority Queue를 사용해서 해결하는 문제였다.Priory Queue에 대한 정리는 이곳에 할 것이다.    ❒ Solution전체 코드더보기public ListNode mergeKLists(ListNode[] lists) { PriorityQueue pq = new PriorityQ..