IT LAB

1. Prefix Sum0~i까지 구간의 합 2. Suffix Sumn~i까지 구간의 합 3. Target SubtotalKadane's Algorithm최대 부분 배열 합을 효율적으로 찾기 위한 알고리즘 동적 프로그래밍i번째 까지 원소의 최대 배열 부분 합을 관리dp[i-1] + 현재 방문한 원소 or 현재 방문한 원소 대소 비교를 통해 dp[i]를 갱신해감 시간복잡도O(n)최대값을 선형으로 찾을 수 있음  출처Wiki - Prefix SumWiki - Maximum subarray problem

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시간 복잡도: O(n^2)공간 복잡도: O(n^2)더보기public static void main(String... args) throws IOException { br = new BufferedReader(new InputStreamReader(System.in)); bw = new BufferedWriter(new OutputStreamWriter(System.out)); input = br.readLine().toCharArray(); size = input.length; isPalindrome = new..

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) 확장 ..

약수어떤 수를 나누어 떨어지게 하는 수 입니다.약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다. 최대공약수 (GCD)두 개 이상의 정수의 공통된 약수 중에서 가장 큰 수를 뜻합니다. 구현유클리드 알고리즘 (구현)두 수의 최대공약수는 작은수와 두 수를 나눈 나머지의 최대공약수와 같음더보기더보기더보기int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b);} 재귀적 구현이 가능합니다.가장 효율적입니다. 고급베주 항등식ax + by = gcd(a, b)위 식을 만족하는 x, y쌍이 항상 존재 (1개 이상)

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

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

1. Sliding Window선형 자료구조에서 특정 크기의 subarray를 찾는 알고리즘 입니다.일정한 크기의 구간을 움직여 찾습니다. 동작 원리윈도우 설정초기 윈도우 구간을 설정함 윈도우 이동한 번에 한 요소씩 이동시킴 (왼쪽 끝 제거 + 오른쪽으로 이동) 조건 확인각 윈도우가 특정 조건을 만족하는지 확인 장점성능슬라이딩 윈도우를 사용하면 O(n)브루트 포스일 경우, O(n^2) 메모리 효율성in-place 알고리즘 (새로운 배열 생성 X)  2. 문제subarrayMinimum Size Subarray Sum (문제) (해설)Longest Substring Without Repeating Characters (문제) (해설)

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}\r..