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 +arr[i], arr[i]);} ✅ dp[i-1] + 현재 방문한 원소 or 현재 방문한 원소 대소 비교를 통해 dp[i]를 갱신해감 출처Wi..

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]; ..

3. 모듈러컴퓨팅에서 한 숫자를 다른 숫자로 나눈 후, 나머지를 반환한 값 a mod n(유클리드 나눗셈의) 나머지a: 피제수n: 제수a mod b = a - b * (a/b) 성질덧셈 법칙뺄셈 법칙곱셈 법칙분배 법칙 응용큰 수 연산암호학해시 함수: 데이터를 고정된 크기의 값으로 매핑할 떄 사용됨주기성 확인: 반복되는 패턴을 찾는 데 사용됨 고급페르마의 소정리소수로 모듈러 연산하였을 때 결과를 구하는 공식소수 p와 p에 나누어 떨어지지 않는 정수 a가 있을 때a^(p) = a (mod p)a^(p-1) = 1  (mod p)a^(p-2) = 1/a  (mod p)a^(p-2)는 a의 모듈러 역원a * a^(p-2) = 1 (mod p) 이므로 a^-1 (mod p) = a^(p-2) (mod p) 확장 ..

1. 약수어떤 수를 나누어 떨어지게 하는 수 입니다.약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다. 2. 소인수주어진 자연수를 나누어 떨어뜨리는 약수중에서 소수인 약수​ 소인수분해합성수를 소인수들만의 곱으로 나타내는 것\[n = p_1^{a_1} \,\cdot\, p_2^{a_2} \,\cdot\, \cdots \,\cdot\, p_k^{a_k}\] 약수의 합n의 모든 양의 약수를 더한 값✅ 소인수분해 형태로 표현\[1 + p + p^2 + \cdots + p^a = \frac{p^{a+1} - 1}{p - 1}\]\[\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{\,a_i + 1} - 1}{p_i - 1}\] 3. 최대공약수 (GCD)두 개 이상의 정수의 공통된 약수 중에서..

1. Floyd-Warshall모든 정점 쌍 간의 최단 경로를 찾는 알고리즘 입니다. 가중치가 양수 혹은 음수인 그래프에서 사용됩니다. (단, 음의 사이클에는 사용 불가) Dynamic Programming인접행렬을 사용하여 각 정점 쌍 간의 최단 거리를 반복적으로 갱신합니다. 2. 동작 원리모든 정점을 경유지로 설정하고, 최단 경로가 경유지를 거쳐 더 짧아질 수 있는지 확인하며 최단 경로 갱신 초기화모든 정점 쌍에 대해, 직접 연결된 경로의 거리 초기화자기 자신으로 가는 경로 = 0연결되지 않은 경로 = infinit 경유지 검사i->j 로 가는 최단 경로가 i -> k -> j로 가는 경로를 통해 더 짧아질 수 있는지 검사 (정점 k를 경유지로 설정)모든 정점에 대하여 반복 3. 구현int[][] d..

1. Activity Selection Problem (활동 선택 문제)한 사람이 참여할 수 있는 최대 활동 수를 구하는 문제입니다.한 사람이 동시에 두 가지 활동을 참여할 수 없습니다. 해결 방법가장 먼저 끝나는 활동부터 선택합니다. 탐욕적 선택 속성현재 선택이 다음 선택의 기준에 영향을 미치지 않습니다.선택할 수 있는 가능 시간을 최대화하여, 남은 활동들을 선택할 수 있는 여지를 최대화합니다. 최적 부분 구조먼저 끝나는 활동을 선택하고, 남은 시간에 대해서도 동일한 방식을 적용할 수 있습니다.

1. Sliding Window선형 자료구조에서 특정 크기의 연속된 구간을 찾는 알고리즘 입니다.일정한 크기의 구간을 움직여 찾습니다. 동작 원리윈도우 설정: 초기 윈도우 구간을 설정함윈도우 이동: 한 번에 한 요소씩 이동시킴 (왼쪽 끝 제거 + 오른쪽으로 이동)조건 확인: 각 윈도우가 특정 조건을 만족하는지 확인 최대 구간 합) 고정 크기 더보기public int maxSumK(int k) { int sum = 0; for (int i = 0; i 최대 구간 합) 가변 크기 + 부분 합 제한더보기public int longestLenSumLt(int S) { int n = arr.length; int l = 0, sum = 0, ans = 0; for (int r = 0; ..

1. Travelling salesman problem 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 떄, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는데 드는 최소 거리 구하기 그래프 이론 각 변에 가중치가 주어진 완전 그래프에서 가장 작은 가중치를 가진 해밀턴 순환 구하기 2. brute-force (permutation. NP) time complexity $O(n!)$ 3. dynamic programming (Held-Karp algorithm) 동작 원리 초기화 모든 도시를 1부터 n까지 번호 매기기 임의의 도시를 시작점으로 선택 상태 정의 $g(S, e)$ : 출발지에서 S에 포함된 모든 도시를 거쳐 e에 도달하는 최단 경로의 길이 최솟값 계산 (재..

1. Longest Common Subsequence (LCS. 최장 공통 수열)두 수열의 공통 부분 수열 중, 가장 긴 수열을 찾는 문제입니다. 부분 수열주어진 수열에서 몇 개의 원소를 선택해 만든 수열✅ 원소의 순서는 원래 수열에서의 순서를 유지해야 함 점화식${\displaystyle LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)+1&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}..