절취선 블로그

[LeetCode] 1641. Count Sorted Vowel Strings class Solution: def countVowelStrings(self, n: int) -> int: dp = [[i for i in range(1,6)] for _ in range(n)] for i in range(1,n): for j in range(1,5): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[n-1][4]

목표 이건 공부해도 모르겠더라 BackTracking 백트래킹 알고리즘이 모든 경우의 수 brute force와 비슷해서 이해를 못하는 듯 하다. 누가 정리한 백D브 차이 백트래킹 vs DFS 백트래킹은 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법으로, 반드시 DFS만으로 가능하지 않고 BFS등으로도 가능한 기법이다. 즉, 정리를 하자면 백트레킹은 하나의 문제 해결 방법론이고 이러한 백트레킹을 구현하는 방법론 중 하나가 DFS이다. 백트래킹 vs 브루트포스 브루트 포스는 모든 경우의 수를 탐색하는 문제 해결 방법론이다. 이와 달리, 백트래킹은 단계마다 조건을 충족하는지 검사하여 조건을 충족하는 경우에만 계속해서 탐색한다. 즉, 정리를 하자면 브루트포스 모든 가지를 탐색하는..

최대 부분 합 구하기 SSAFY 7기 CT 문제에 출제되었던 문제로 1차원 배열에서 가장 큰 값을 가질 수 있는 연속적인 부분 배열을 찾는 문제에 사용되는 알고리즘이다. 많은 문제들이 시간, 공간 복잡성이 적은 카디안 알고리즘을 적용한 문제풀이를 선호한다. 카디안 알고리즘에서는 시,공간 복잡성이 O(n) 으로 다음과 같이 구현한다. LeetCode 53. Maximum Subarray 문제 링크 public int maxSubArray(int[] nums) { int sum = 0; int max = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++){ sum+= nums[i]; max = Math.max(sum, max); if (sum < 0) sum..