[LeetCode] 743. Network Delay Time [Python(파이썬)]
'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (네트워크 딜레이 타임) k부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값 (x,y,z)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 n으로 입력받는다. 2. 풀이 다익스트라 알고리즘을 이용한 풀이 3. 코드 from collections import defaultdict import heapq class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = defaultdict(list) for x, y, w in times..
2021. 11. 24.
[LeetCode] 200. Number of Islands [Python(파이썬)]
'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (섬의 개수) 주어진 맵에서 1을 육지, 0을 물로 가정하였을 때, 섬의 개수를 구하여라. 2. 풀이 DFS를 이용한 풀이 3. 코드 class Solution: def numIslands(self, grid: List[List[str]]) -> int: dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] def dfs(i, j): if i = len(grid) or j = len(grid[0]) or grid[i][j] != '1': return grid[i][j] = '0' for x in range(4): dfs(i+dx[x], j..
2021. 11. 24.
[LeetCode] 886. Possible Bipartition [JAVA(자바)]
'기술면접 라이브코딩 - 승지니어'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 () N명의 사람을 두 그룹으로 나눈다. Dislikes[i] = [a,b] 일 때, a 와 b 는 서로 다른 그룹이어야 한다. Input: N = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: group1 [1,4], group2 [2,3] Input: N = 3, dislikes = [[1,2],[1,3],[2,3]] Output: false 2. 풀이 이분그래프 와 DFS 를 이용한 풀이 이분그래프를 통해 N명의 사람을 2개의 그룹으로 나눈다. DFS 를 통해 dislikes한 사람을 모두 다른 그룹(true/false)으로 보낸다. visi..
2021. 11. 24.
[LeetCode] 218. The Skyline Problem [JAVA(자바)]
'기술면접 라이브코딩 - 승지니어'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 빌딩의 좌표가 주어졌을 때, 모든 빌딩이 형성하는 실루엣의 바깥 쪽 윤곽점을 나타내어라. Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] 2. 풀이 Sort 와 TreeMap 을 이용한 풀이 빌딩을 2개의 Line으로 나눈다. 빌딩의 왼쪽과 오른쪽을 구분하기 위해 왼쪽은 높이에 마이너스를 붙인다. (-height) (left, -height), (right, height) List lines = new ArrayList(bui..
2021. 11. 24.
