분류 전체보기

✔ 문제 055 임계 경로 구하기 문제 바로가기 💨 ⬜ 핵심 아이디어 ▪️ 위상정렬, 에지 뒤집기 플래티넘 문제인 만큼 문제 의미 해석부터 어려웠던 문제이다. (그만큼 깨달은게 많아 별도 문제로 기록한다..ㅎ) 여기서 임계 경로는 최장거리를 의미한다. 이 문제에서, 모든 사람들이 만나는 시간은 도착점에 가장 오래걸리는 사람이 도착하는 시간일 것이다. 만약 1 → 3 (2초) 2 → 3 (10) 초라고 가정해보자. 그럼 모든 사람들이 만나는 시간은 2->3 인 10초일것이다. 즉, 문제에서 요구하는 '출발 도시에서 출발한 후 도착 도시에서 만나기까지 걸리는 최소시간'은 '도착점에 가장 늦게 도착했을때 걸리는 시간(최장 시간)'이다. 이는 최장 경로비용을 의미한다. 또한 문제에서는 일방통행이고 사이클이 없다..

[Spring] 스프링 핵심 원리 - 기본편 섹션 2 스프링 핵심 원리 이해1 - 예제 만들기 📄 비즈니스 요구사항과 설계 회원 관리: 회원은 가입하고 조회할 수 있어야 한다. 회원은 일반과 VIP 두 가지 등급으로 나뉜다. 회원 데이터는 자체 DB를 구축하거나 외부 시스템과 연동할 수 있다. (미확정) 주문과 할인 정책: 회원은 상품을 주문할 수 있다. 회원 등급에 따라 할인 정책을 적용할 수 있다. 할인 정책은 모든 VIP에게 1000원을 할인해주는 고정 금액 할인을 적용한다. (나중에 변경 가능) 할인 정책은 변경 가능성이 높으며, 기본 할인 정책이 아직 정해지지 않았으며 오픈 직전까지 고민을 미루고 싶다. 최악의 경우 할인을 적용하지 않을 수 있다. (미확정) 순수 자바로 개발 후 스프링을 통해 ..

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ Algorithm 예외 경우(시작점이나 끝점이 벽인경우)를 놓쳐서 어디가틀린지 해맨 문제다. 항상 문제를 볼때 조건을 꼼꼼히 보고 예외 케이스를 생각하자. Python class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: N = len(grid) if grid[0][0] == 1 or grid[N-1][N-1] == 1: # 시작점 또는 끝점이 벽인 경우 return -1 q = deque([(0, 0, 1)]) visit = set((0,0)) direct = [[0, 1], [1..

https://leetcode.com/problems/kth-largest-element-in-an-array/description Algorithm quick select에 대해 배운 문제! 단순정렬해 풀면 복잡도가 nlogn이지만 이문제는 더 효율적으로 풀길 요구한다.나는 maxHeap으로 풀었는데, 평균적경우 더 효율적일수 있는 풀이가 있어 기록을 남긴다. 먼저 나의 처음 나의 풀이는 다음과 같다.k largest문제이니 minHeap으로 k번째초과면 pop() 하는 방식으로 풀 수도 있을것 같다. 이정도면 됐지,싶었다 ㅋ근데 퀵을 활용한 다른 풀이가있다..?! 바로 quick select 방법을 이용하면 평균적으로 O(n) 만에 k 번째를 찾을 수 있다! (n + n/2 + n/4...) pivo..

✔ 문제 050 집합 표현하기 문제 바로가기 💨 ⬜ 핵심 아이디어 ▪️ 유니온 파인드 union 연산: 각 노드가 속한 집합을 1개로 합치는 연산 find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 ▪️구현 핵심 각 노드를 자신의 인덱스값으로 초기화 union은 항상 대표노드끼리 연결해 준다. find 연산은 그래프를 정돈하고 시간 복잡도를 줄인다. ▪️find 연산 index 값과 value 값이 동일한지 확인 동일하지 않으면 value 값이 가리키는 index 위치로 이동 이동 위치의 index값과 value값이 같을 때까지(대표 노드 찾을 때까지) 반복 대표 노드에 도달하면 재귀를 빠져나오며 거치는 모든 노드값을 대표 노드값으로 변경 ▪️실수 주의 😲 경로 압축은 늘 ..

✔ 문제 048 이분 그래프 판별하기 문제 바로가기 💨 ⬜ 핵심 아이디어 이분 그래프란? 집합이 두 개 있을때, 인접한 노드끼리 서로 다른 집합에 넣을 수 있다면 이분 그래프 인접한 노드끼리 서로다른 집합에 들어가게 만들 수 있으면 이분그래프 인접한 노드끼리 같은 집합이 되지 않도록 어떻게 적절히 분할할까? 생각해보면, 트리는 항상 이분 그래프이다. 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문이다! 즉, 사이클이 발생하지않으면 이분그래프이다. 단, 사이클이 발생했을때는 이런 이분 그래프가 불가능할 때가 있다. (ex _ 1 -> 2 -> 3 -> 1) 기존 탐색 노드에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불..

👩‍💻 힙 개념 힙 속성 힙은 트리 기반의 데이터 구조로, 완전 이진 트리 이는 주로 우선순위 큐를 구현하는데 사용. 힙은 큐의 선입선출 기준이 아닌, 우선순위에 따라 값을 제거. 높은 우선순위를 가진 요소가 먼저 제거된다. 힙은 배열을 사용하여 구현된다. 최대 힙과 최소 힙의 속성을 살펴본다면, 문제가 최솟값 또는 최댓값을 찾도록 요구한다면 힙이 하나의 선택지가 될 수 있다! 두 종류의 힙 최소 힙: 최소값이 루트 노드에 있으며, 삭제할 때 가장 작은 값이 가장 높은 우선순위를 갖는다. 최대 힙: 최대값이 루트 노드에 있으며, 삭제할 때 가장 큰 값이 가장 높은 우선순위를 갖는다. 힙 속성 힙으로서 이진 트리가 자격을 갖추려면 다음 속성을 충족해야 합니다: 구조 속성: 이진 힙은 완전 이진 트리여야 한..

✔ 문제 049 물의 양 구하기 문제 바로가기 💨 ⬜ 핵심 아이디어 A,B,C 의 물의 양 상태를 1개의 노드로 가정하고 줄기 노드를 모두 탐색한다. 노드에서 갈 수 있는 6개의 경우(A->B, A->C, B->A, B->C, C->A, C->B) 노드를 BFS 탐색한다 (큐 추가). 이때, a,b,c 물의양이 동일한 노드에 방문한 이력이 있을때는 큐에 추가하지않는다. 받는 물통에 보내는 물통의 모든 용량을 저장한다.보내는 물통에는 0을 저장한다. 만약 받는 물통이 넘친다면 그 초과 양만큼 보내는 물통에 남긴다. 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통(C)의 값을 정답 리스트에 추가한다. JAVA import java.util.Scanner; import java...

https://leetcode.com/problems/combination-sum/description/ Algorithm 개인적으로 많이깨달은 문제이므로 기록을 상세히 남긴다. 경우의 수....? 이진트리 백트래킹! 🧐 처음 생각한 풀이는 완전탐색이다. 아주원시적으로...아래 첫번째 트리 그림처럼 모든 경우 수를 탐색한다. 그리고 [2,2,3] [2,3,2]는 같은 것이니 정렬후 같은 리스트는 지워준다. class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(s,path): tmp = sum(path) if tmp == target: # 정답조건 answer.append(..

https://leetcode.com/problems/subsets/description/ Algorithm 로직을 완전히 이해하는데 반나절 걸린 문제이다.ㅎ... 이 문제의 핵심은 백트래킹! 모든 집합 경우의 수 탐색이므로, 이진트리를 사용한다.여기서는 백트래킹을 이용하고, 알고리즘 두가지로 풀어볼 것이다. 먼저 첫번째 방법은 위와같은 구조로 각 가능한 경우수를 세는 방법이다! 처음 떠올린 로직이다. 이건 풀이를 참조했는데, 각 숫자를 선택하는 경우 / 선택안하는경우로 케이스를 나누어 탐색하는 방법이다. *주의할점 path[:]를 사용하면 path 리스트의 현재 상태를 복사하여 추가한다. 이렇게 하면 후에 path가 변경되더라도 result 리스트에 추가된 path는 영향을 받지 않는다. 즉, 각 재귀..