IT LAB

1. Prefix Sum0~i까지 구간의 합 코드더보기for (int i = 0; i =0 ? ps[i-1] : 0 + arr[i];} 2. Suffix Sumi~n까지 구간의 합코드더보기for (int i = n-1; i >= 0; i--) ps[i] = i+1 3. Target SubtotalKadane's Algorithmi번째 원소를 끝으로 하는 최대 연속 부분합✅ 최대 부분 배열 합을 효율적으로 찾기 위한 알고리즘➡️ O(n): 연속된 부분배열의 최대값을 선형으로 찾을 수 있음 코드더보기for (int i = 0; i =0 ? dp[i-1] : 0)); max = Math.max(max, dp[i]);} ✅ dp[i-1] + 현재 방문한 원소 or 현재 방문한 원소 대소 비교를 통해 dp[i..

1. Edit Distance두 문자열 간의 최소 편집 거리를 계산하는 문제입니다.한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 연산의 수를 의미합니다. 연산삽입: 문자 삽입삭제: 문자 삭제교체: 한 문자를 다른 문자로 교체DP 테이블 정의dp[i][j]i~j까지 최소 편집 연산 수 점화식A[i-1] == B[j-1]dp[i][j] = dp[i-1][j-1]문자가 같으므로 편집 필요 없음 A[i-1] != B[j-1]삽입, 삭제, 교체 중, 최소값을 선택삽입A에 문자를 삽입하여 B와 같아지게 함 dp[i][j-1] + 1삭제A에 문자를 삭제하여 B와 같아지게 함 dp[i-1][j] + 1교체A의 문자를 다른 문자로 교체하여 B와 같아지게 함dp[i-1][j-1] + 1 출처Wiki -..

1. Longest Palindrome Substring (LPS)문자열 안에서 가장 긴 팰린드롬 부분 문자열 Dynamic Programming더보기public int solve(char[] input) throws IOException { int size = input.length; boolean[][] isPalindrome = new boolean[size][size]; int max = 0; for (int i = 0; i = size) break; if (input[start] != input[end]) continue; isPalindrome[start][end] = isPalindrome[start+1][end-1]; ..