Medium174 [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][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. [Leetcode][665] Non-decreasing Array 문제 : leetcode.com/problems/non-decreasing-array/ 정수형 배열이 주어질 때 최대 한 개의 요소를 수정하여 감소하지 않는 배열을 만들 수 있는지를 구하라. 만들고자 하는 배열은 증가하는 배열이 아닌, 감소하지 않는 배열이므로 증가하는 수를 찾아 바로 앞이나 뒤에 있는 요소와 같은 수로 변경시킨다. (기본 아이디어) 앞에서부터 배열을 탐색하면서 탐색 중인 인덱스가 i일 때, nums[i] > nums[i+1] (감소하는 구간)인 경우 i를 변수를 만들어 저장해둔다. (let, ind). 만일 ind 변수가 2번 이상 세팅되려고 할 땐 두 개의 요소를 수정해야 하므로 감소하지 않는 배열을 만들 수 없다. 모든 배열을 탐색했을 때, ind 변수가 세팅된적이 없거나 (모든 요.. 2021. 5. 8. [Leetcode][970] Powerful Integers 문제 : https://leetcode.com/problems/powerful-integers/ 1이상의 양수인 x, y, 0이상의 bound가 입력으로 주어진다. i, j 가 0이상의 양수라 할때, x^i + y^i 2021. 5. 1. 이전 1 ··· 10 11 12 13 14 15 16 ··· 29 다음
