알고리즘 문제/Leetcode283 [Leetcode] 36. Valid Sudoku 문제 : https://leetcode.com/problems/valid-sudoku/ 9 x 9 스도쿠 보드가 유효한지 확인해라. 채워진 셀만으로 다음 규칙을 만족하는지 검증해야 한다. 각 행, 열은 반복 없이 숫자 1~9를 포함해야 한다. 그리드의 3x3 하위 사각형 블럭은 반복 없이 숫자 1~9를 포함해야 한다. 숫자를 포함하는지 비트 연산으로 확인한다. 변수의 이름을 visits으로 하고 초기값은 0이며 i 숫자를 포함한다면 visits or (1 2022. 3. 9. [Leetcode] 740. Delete and Earn 문제 : https://leetcode.com/problems/delete-and-earn/ DP로 풀었다. nums 배열의 최대 요소값을 구하고 이를 maxNum이라 하자. maxNum 크기만큼의 1차원 배열 cnts를 만들고 cnts[i] = nums 요소들중 i의 개수 를 nums 배열을 탐색하며 저장한다. maxNum 크기만큼의 1차원 배열 dp를 만들고 이는 아래의 점화식을 가진다. dp[i] = 0 ~ i 요소들에서 포인트를 얻을 때 얻을 수 있는 최대 포인트 = max(dp[i-1], dp[i-2] + (cnts[i] * i)) i-1 번째 포인트를 얻은경우 i번째 포인트는 지워지므로 얻을 수 없지만 i-2 번째 포인트를 얻은 경우 i번째 포인트도 얻을 수 있기 때문에 위와 같은 점화식이 된.. 2022. 3. 5. [Leetcode] 799. Champagne Tower 문제 : https://leetcode.com/problems/champagne-tower/ DP로 풀었다. dp[row][glass] = row 행의 glass 번째 그릇의 남는 샴페인 양. = (dp[row-1][glass] + dp[row-1][glass+1]) % 1 dp[0][0] = poured로 갱신 후 아래 수도코드를 진행한다. for(int row=0; row 2022. 3. 5. [Leetcode] 413. Arithmetic Slices 문제 : https://leetcode.com/problems/arithmetic-slices/ nums 배열을 탐색하면서 탐색 중인 nums[i] 를 포함하는 정답가능한 subarrays 수를 정답에 더해나간다. nums[i]를 포함하는 정답가능한 subarrays 수를 구하기 위해, nums[i], nums[i-1] 두 요소간 차이와 동일한 nums 요소 수를 cnt 변수에 저장한다. nums[i]-nums[i-1]이 nums[i-1]-nums[i-2] 와 동일하다면 cnt + 1, 동일하지 않다면 cnt를 2(i-1, i)로 갱신한다. nums[i]를 포함하는 정답가능한 subarrays 수는 cnt-2이다. 정답가능 하위배열은 앞에서부터 요소를 하나씩 삭제해가며 최소 3개이상의 요소만 있으면 정답.. 2022. 3. 3. [Leetcode] 662. Maximum Width of Binary Tree 문제 : https://leetcode.com/problems/maximum-width-of-binary-tree/ 이진 트리의 루트가 주어지면 트리의 최대 너비를 구하라. 최대 너비는 모든 레벨 중 최대 너비이며, 한 레벨의 너비는 가장 왼쪽 노드와 가장 오른쪽 노드의 길이이다. 만약 노드들 사이에 null 노드가 존재한다면 null 노드도 길이에 포함시킨다. 이진트리의 인덱스를 구해보면 위와 같다. 특정 노드의 왼쪽 자식 노드의 인덱스는 2 x 인덱스. 오른쪽 자식 노드의 인덱스는 2 x 인덱스 + 1 이다. 이를 이용하여 루트 노드부터 자식 노드들을 탐색해가며 각 레벨에서 가장 왼쪽에 존재하는 노드와 가장 오른쪽에 존재하는 노드의 인덱스 차이가 너비가 된다. 구한 너비들 중 최대값이 정답이 된다. .. 2022. 2. 27. [Leetcode] 847. Shortest Path Visiting All Nodes 문제 : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/ 우선 플로이드 워셜 알고리즘으로 모든 정점간 최단거리(dist)를 구한다. 구한 dist 배열로 플로이드 워셜 알고리즘이랑 비슷하게 정답을 구한다. 기본 알고리즘은 다음과 같다. 여기서 상태란 node들이 포함된 상태를 의미한다. (참고) 즉, 플로이드 워셜 알고리즘 처럼 3중 for문을 돌린다. 중간 지점을 중간에 거치는 상태로 두고 시작 노드에서 종료 노드로 갈 때 거치는 최소 간선의 수를 구한다. 조건문에 시작노드가 포함되고 종료노드는 포함되지 않은 상태가 중간상태가 되야 하는 이유는 중간상태에 시작노드가 있어야만 시작 상태가 될 수 있고, 중간상태에 종료.. 2022. 2. 26. 이전 1 ··· 5 6 7 8 9 10 11 ··· 48 다음
