알고리즘 문제408 [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. [Codejam][2021][Round 1A] 1. Append Sort 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007549e5 이전 숫자를 prev, 현재 탐색 중인 숫자를 now라 하자. now > prev가 되도록 숫자를 now뒤에 추가해야 한다. 만약 prev가 now보다 작다면 추가 digit 없이 조건을 만족하므로 다음 숫자를 탐색한다. prev의 자리수가 now 자리수보다 작다면 반드시 prev가 now보다 작으므로 이 경우에 속한다. ex) prev = 10, now = 8 prev와 now의 자리수가 동일하다면 now 뒤에 숫자 0을 추가한다. ex) prev = 10, now = 10 => 100 이 외의 경우는 prev의 자리수가 now 자리수.. 2022. 3. 1. [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. 이전 1 ··· 5 6 7 8 9 10 11 ··· 68 다음
