알고리즘 문제/Leetcode283 [leetcode] 684. Redundant Connection 문제 : https://leetcode.com/problems/redundant-connection/ n개의 노드와 n개의 간선으로 이루어진 무방향 그래프가 주어질 때, n개의 노드로 이루어진 트리가 될 수 있도록 제거해야 하는 간선을 구하여라. 조건에 그래프들은 연결되어 있고 노드가 n개인데 간선도 n개라고 하니, 트리의 특징 중 하나인 간선의 개수는 정점 개수 - 1 이다.를 생각하면 정답이 되는 간선은 1개가 나올 수 있고. 이 간선은 사이클을 만듬을 알아낼 수 있다. 크루스칼 알고리즘 구현에서 사이클이 생성됨을 알아내기 위해 유니온 파인드를 사용했었다. 이를 응용하여, 입력으로 주어지는 간선들을 Union-Find 의 Union 연산으로 하나의 집합으로 합치면서 이미 같은 집합인데 Union 연산.. 2021. 6. 26. [Leetcode][576] Out of Boundary Paths 문제 : https://leetcode.com/problems/out-of-boundary-paths/ DP. 메모이제이션이 필요하다. 남은 maxCount 횟수, 현재 좌표가 같다면 정답 횟수는 같아진다. 즉, dp[maxCount][row][column] = 경계를 벗어나는 경로 횟수 를 저장한다. dp[maxCount][row][column] = dp[maxCount-1][row][column+1] + dp[maxCount-1][row][column-1] + dp[maxCount-1][row+1][column] + dp[maxCount-1][row-1][column] 이동은 상하좌우로 할 수 있기 때문에 점화식은 다음과 같다. 더한 값에 1000000007을 나눈 나머지값을 저장해줘야한다. 만일 r.. 2021. 6. 25. [leetcode][118] Pascal's Triangle 문제 : https://leetcode.com/problems/pascals-triangle/ numRows가 주어질 때, numRows 크기의 파스칼의 삼각형을 구하여라. 파스칼의 삼각형의 원소는 바로 위에 있는 두 원소의 합이다. answer[i][j] = answer[i-1][j-1] + answer[i-1][j] 위 연산을 모든 원소에 적용하면 답을 수할 수 있다. 시간복잡도는 1+2+ ... + numRows = 대략 O(numRows^2 /2). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/118.%20Pascal's%20Triangle.cpp 2021. 6. 22. [leetcode][778] Swim in Rising Water] 문제 : https://leetcode.com/problems/swim-in-rising-water/ N x N 배열 grid가 입력으로 주어진다. grid[i][j] = (i,j) 위치의 높이. 시간 t에서 모든 grid 위치의 수심은 t이고, 인접한 위치의 고도가 t 이하인 경우에만 이동가능하다. 이동하는데 드는 시간은 고려하지 않는다. grid의 (0,0)에서 (N-1, N-1)로 이동할 때 도달할 수 있는 최소시간은 얼마인가 이동하는데 드는 시간은 고려하지 않으므로 결국 (0, 0) -> (N-1, N-1)로 이동하는 경로의 고도값들의 최대값의 최소값을 구하는 문제이다. 다익스트라로 풀었다. 간선의 가중치는 u -> v로 이동한다고 했을 때, v 위치의 높이가 된다. 즉, 높이가 낮은 인접한 위치.. 2021. 6. 21. [leetcode][795] Number of Subarrays with Bounded Maximum 문제 : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/ 양수 배열 nums, 두 개의 양수 left, right 가 입력으로 주어진다. nums 배열의 하위배열(연속적인 부분배열. 비어있지 않음)의 최대 원소가 left 이상, right 이하인 하위배열들의 수를 구해라. 재미있는 투포인터문제~ nums를 처음부터 탐색하면서 정답이 될 수 있는 범위를 l, r 변수에 저장한다. (l = 왼쪽, r = 오른쪽 인덱스) l 변수는 nums[i]가 부분배열에 포함될 때 정답이 절대 불가능할 때 갱신한다. 최대값만 left, right를 비교하기 때문에 정답이 절대 불가능한 경우는 nums[i]가 right보다 큰 경우이다. r 변.. 2021. 6. 19. [Leetcode][583] Delete Operation for Two Strings 문제 : leetcode.com/problems/delete-operation-for-two-strings/ 문자열 word1, word2 가 주어질 때, 두 문자열을 같게 만들게하기 위해 최소 몇 개의 문자를 삭제해야하는지 구해라. 최장공통부분수열(LCS; Longest Common Subsequence)로 풀었다. word1, word2 문자열의 문자들을 모두 탐색하면서 dp[i][j] (word1[0~i-1], word2[0~j-1]의 최장 공통부분수열 길이)를 세팅한다. for(int i=1; i 2021. 5. 8. 이전 1 ··· 19 20 21 22 23 24 25 ··· 48 다음
