❒ Desciption날짜2024.09.18 (수)레벨Medium제목Gas Station링크https://leetcode.com/problems/gas-station/description/자료구조배열알고리즘그리디시간 복잡도O(N) 문제를 풀이할 때 PriorityQueue와 이중 while 문을 통해 풀이를 하였다.하지만 이는 굉장히 메모리 측면에서 비효율적인 풀이였다.     ❒ 문제 분석문제에서는 gas 배열과 cost 배열을 input으로 준다.int[] gas : 현재 위치에 있는 주요소가 보관하고 있는 gas량int[] cost : 해당 위치의 주유소로 이동하기 위해 필요한 gas량그리고 모든 주유소를 원형으로 연결되어 있다.문제의 목적은 주어진 gas와 cost 배열을 가지고, 어디서 출발해야..

❒ Description알고리즘 문제를 풀면서 Dijkstra 알고리즘과 Floyd-Warshall 알고리즘을 학습했다.이제 이 두 알고리즘의 차이를 정리해보자.     ❒ 차이점다익스트라(Dijkstra) 알고리즘과 플로이드-워샬(Floyd-Warshall) 알고리즘은 모두 최단 경로를 찾는알고리즘이지만, 두 알고리즘 간에는 여러 차이가 있다.  1. 적용 대상 및 문제 유형다익스트라 알고리즘은 하나의 시작점에서 모든 정점으로의 최단 경로를 찾는데 사용된다.단일 출발점 최단 경로 문제에 적합하다.주로 가중치가 양수인 그래프에 사용된다.그래프가 희소(Sparse)할 때 효율적이다. (간선의 수가 적을 때) 반면에 플로이드-워샬 알고리즘은모든 정점 간의 최단 경로를 찾는데 사용된다.모든 정점엥서 다른 모든..

❒ Description날짜2024.09.17 (화)제목Task Scheduler링크https://leetcode.com/problems/task-scheduler/description/자료구조배열 & 우선순위 큐알고리즘그리디시간 복잡도O(NlongN) 아이디어도 생각나지 않았던 문제였다.     ❒ 문제 분석이번 문제는 주어진 task를 모두 수행하기 위한 최소 횟수를 출력하는 것이다. 그리고 동일한 task를 수행하기 위해선주어진 interval을 신경써줘야 한다. 문제에서 변수 `n`을 interval로 제시해준다. 예를 들어 interval이 3이라면 동일한 `A` 작업을 마무리하기 위해서는 `A _ _ _ A` 와 같이 3번의 interval이 필요하다. 여기서 한 가지 규칙을 발견할 수 있다...

❒ Description날짜2024.09.17 (화)제목Queue reconstruction by height링크https://leetcode.com/problems/queue-reconstruction-by-height/description/자료구조ArrayList, PriorityQueue알고리즘그리디시간 복잡도O(n) 이번 문제는 Priority Queue의 순서 설정, ArrayList의 성질 그리고 index 활용이 필요한 문제이다.     ❒ 문제 분석우선 먼저 우선순위 큐의 정렬 기준을 세워야 한다.h가 같은 경우k 기준으로 오름차순 정렬h가 같지 않을 경우h 기준으로 내림차순 정렬 그리고 k를 index로 활용하여 person을 정렬한다.     ❒ Solutionpublic int[][]..

❒ Description날짜2024.09.16 (월)제목Best Time to Buy ans Sell II링크https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/자료구조배열 & 스택 알고리즘그리디시간 복잡도O(n) 이번 문제는 배열 또는 스택을 사용하여 풀이할 수 있는 문제이다.물론 스택을 사용하면 메모리를 더 사용한다는 단점은 존재한다.그리고 이 문제는 [LeetCode#739] Daily Temperature 풀이에서 아이디어 하나만 추가하면 된다.      ❒ Solution1. Stackpublic int maxProfit(int[] prices) { Deque stack = new ArrayDeque();..

❒ Description날짜2024.09.15 (일)난이도Medium제목Jump Game링크https://leetcode.com/problems/jump-game/description/자료구조 / 알고리즘배열 / 그리디시간 복잡도O(n) 이번 문제는 Greedy 알고리즘을 사용해서 해결하는 문제다. 처음에 재귀를 통해 접근을 했지만 풀지 못했고,풀었다고 하더라도 Time Limie Exceeded 에러를 만나게 된다.       ❒ Greedy(탐욕적) 알고리즘Greedy 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용 했을 때 만족시킬 수있으므로 그리디 알고리즘 ..

❒ Description제목Network Delay Time링크https://leetcode.com/problems/network-delay-time/description/자료구조/알고리즘그래프 / 다익스트라 알고리즘시간 복잡도O(ElogV) 다익스트라 알고리즘을 사용해서 해결할 수 있는 문제이다.이번 문제는 중복을 허용하지 않기 위해서 visited boolean 배열을 사용하였다.  문제 해결 순서주어진 input, times를 배열을 사용해서 표현해준다.List> : index는 source를 표현한다.각 노드까지 걸리는 소요시간을 나타내는 배열을 생성한다.배열 생성 후 최초에는 무한대 값을 의미하는 1e9로 초기화 한다.방문 여부를 확인할 배열을 생성한다.소요 시간이 짧은 순서가 우선이 되는 Pr..

❒ Description레벨3제목순위링크https://school.programmers.co.kr/learn/courses/30/lessons/49191자료구조그래프시간복잡도O(V³) 이번 문제는 처음에는 Map과 PriorityQueue로 접근해서 풀어보려고 했다.하지만 이 문제는 Floyd-Warshall 알고리즘을 응용해서 풀이하는 문제였다.     ❒ 문제 분석이번 문제의 목적은 선수의 순위를 매기는 것인데, 어떤 선수의 경우에는 정확하게 순위를 매길 수 없다.그리고 [A, B], [B, C] 이렇게 되어있을 때 A는 B를 이길 수 있고, B는 C를 이길 수 있다. 이것을 바탕으로A가 C를 이길 수 있다는 해석을 할 수 있다. 예시로 주어진 input 값을 그래프화 했다. 4번이 5번을 이길 수 ..

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

❒ Description트랜잭션은 하나의 논리적 기능을 수행하기 위한 작업의 단위를 말한다. 오늘은 DB 면접 단골 질문인 트랜잭션에 대해서 기초와 깊이 있는 학습을 해보자!!     ❒ ACIDACID는 트랜잭션의 핵심이다. Atomicity, Consistency, Isolation, Durability의 첫 글자를 따온 것으로각 단어는 트랜잭션이 어떤 속성을 지녀야 하는지 나타낸다.  1. 원자성 (Atomicity)원자성은 트랜잭션과 관련되 일이 모두 수행되었거나 되지 않았거나를 보장하는 것이다. 예를 들어 트랜잭션을커밋했는데, 문제가 발생하여 롤백하는 경우 그 이후에 모두 수행되지 않음을 보장하는 것을 말한다. 원자성을 지키기 위해 DB에서는 commit과 rollback이 있다.commit은 ..