본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][1319] Number of Operations to Make Network Connected 문제 : https://leetcode.com/problems/number-of-operations-to-make-network-connected/ 컴퓨터의 총 개수와 네트워크 연결 여부를 저장한 배열이 주어졌을 때, 모든 컴퓨터들이 네트워크에 연결하기 위해 이동이 필요한 네트워크 연결 수 를 반환하는 문제. (불가능하다면 -1) 최소 신장 트리의 간선 수는 N-1개이다. 비슷하게 이 문제에서 불가능한 네트워크 개수는 컴퓨터의 총 개수 - 1 보다 작은 경우들이다. 이 경우를 만족한다면 모든 컴퓨터들이 네트워크에 연결이 가능하다. Union-Find를 이용해서 네트워크 번호를 하나의 배열에 저장한다. 즉, a, b 컴퓨터가 같은 네트워크에 있다면 배열[a], 배열[b]는 같은 값을 가진다. 네트워크 배열.. 2020. 3. 7.
[leetcode][79] Word Search 문제 : https://leetcode.com/problems/word-search/ 2차원 문자 배열, 단어가 주어지면 배열에 단어의 유무를 리턴하는 문제. 신문 단어 퍼즐 같은 문제. DFS로 풀었다. 문자열 배열을 탐색하면서 탐색중인 인덱스를 시작 위치로 하여 단어가 있는지 판단한다. // board: 2차원 문자 배열 // word : 찾는 단어 // board[x][y]를 시작 위치로 하여 word가 있는지 find(board, x, y, word): // 경계 체크 if(x, y 이미 방문) return false if(board[x][y]와 word의 첫 번째 문자가 같지 않다면) return false ans = false x, y 방문 체크 for(nx, ny = 상, 하, 좌, 우 이동.. 2020. 3. 7.
[leetcode][1329] Sort the Matrix Diagonally 문제 : https://leetcode.com/problems/sort-the-matrix-diagonally/ 입력으로 받은 배열의 대각선 요소들을 오름차순 정렬한 뒤 반환하는 문제 최소힙으로 풀었다. 대각선 요소들을 하나의 힙에 넣어야 한다. 인덱스 0 1 2 3 0 2 3 4 5 1 1 2 3 4 2 0 1 2 3 3x4 배열의 대각선 인덱스를 구하면 위와 같다. (구현에 따라 달라질 수 있음) 대각선 배열의 최대 크기는 n+m-1 이다. (m: 행, n: 열) mat[i][j]의 대각선 인덱스는 i+j-m-1 이다. 위 표를 보았을 때 열의 가장 아래부터 시작하기 때문에 m을 빼주었다. 1은 인덱스는 0부터 시작하기 때문에 뺐다. 따라서 n+m-1 개의 최소 힙을 배열에 저장한뒤, mat 배열을 .. 2020. 2. 15.
[leetcode][368] Largest Divisible Subset 문제 : https://leetcode.com/problems/largest-divisible-subset/ 중복되지 않는 양수 정수 배열이 주어질 때, (A, B) pair가 A%B = 0 이거나 B%A = 0 인 경우, 즉, 나누어떨어지는 수들로만 이루어진 subset들 중 가장 긴 subset을 하나 구하는 문제이다. dp로 풀었다. dp[i] = 부분문자열[i~]에서 i 번째 정수를 반드시 포함하면서 조건에 만족하는 subset들 중 최장 길이. (길이를 저장) nextInd[i] = dp[i]가 저장될 때, 2번째로 저장되는 정수의 인덱스. (1번째는 i번째 정수로 고정). 나중에 subset 문자열을 구할 때 추적용도로 사용한다. 초기값은 -1 [1,2,4,5]을 예로 들어보자. 인덱스 0,1.. 2020. 1. 26.
[leetcode][1267] Count Servers that Communicate 문제 : https://leetcode.com/problems/count-servers-that-communicate/ m x n grid가 주어질 때, 1은 서버, 0은 빈 셸이라고 하자. 같은 행이나 열에 서버가 있는 경우 그 서버는 다른 서버와 통신할 수 있다고 한다. 다른 서버와 통신할 수 있는 서버의 총 개수를 구하는 문제이다. 예를 들어서 확인해보자. 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 grid가 위와같이 주워졌다고 하자. 1 1 0 0 1 1 1 0 1 1 2 0 1 1 2 1 열 subsum은 위와 같이 채워진다. 위에서 아래로 채운다고 생각하면 된다. 1 2 2 2 0 0 1 1 0 0 1 1 0 0 0 1 행 subsum은 위와 같이 채워진다. 왼쪽에서 오른쪽으로 .. 2020. 1. 26.
[leetcode][1288] Remove Covered Intervals 문제 : https://leetcode.com/problems/remove-covered-intervals/ 간격배열이 주어질 때, [a,b), [c,d)가 있는 경우 c 2020. 1. 25.

티스토리툴바