Computer Science/Computer Algorithms18 [Computer Algorithms] KMP Algorithm https://www.youtube.com/watch?v=ynv7bbcSLKE&t=147s 영상에 소개된 것과 같이, O(m + n)에 text에서 pattern이 나타나는 인덱스를 찾는 알고리즘 import sysread = sys.stdin.readlinedef LPS(pattern): m = len(pattern) lps = [0] * m j = 0 i = 1 while i 2025. 7. 9. [Computer Algorithms] Combination (조합) N개 들어있는 배열에서 i개 고르는 경우를 모두 출력하는 알고리즘이다. mask를 이용해서 true인 자리에 있는 것을 출력한다.#include #include #include using namespace std;int main(){ int N = 5; vector arr = {1, 2, 3, 4, 5}; for (int i = 1; i mask(arr.size(), false); fill(mask.begin(), mask.begin() + i, true); // 앞의 i개를 true로 설정 do { for (int j = 0; j 10000의 이전 조합: 0100001000의 이전 조합: 0010000100의 이전 조합: 00.. 2025. 3. 30. [Computer Algorithms] Bellman-Ford Algorithm (벨만-포드 알고리즘) 벨만-포드 알고리즘 (Bellman-Ford Algorithm)벨만-포드 알고리즘은 가중 그래프에서 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 비슷하지만, 음수 가중치(edge weight)를 가진 그래프도 처리할 수 있다는 점이 큰 차이점이다. 알고리즘 개요그래프 유형: 가중치 그래프(음수 가중치 가능), 방향 그래프(Directed Graph)시간 복잡도: O(VE) (V: 정점 개수, E: 간선 개수)장점: 음수 가중치를 가진 그래프에서도 최단 경로 계산 가능단점: 다익스트라(O((V+E) log V))에 비해 느림추가 기능: 음수 사이클(Negative Cycle) 존재 여부도 확인 가능알고리즘 동작 과정모든 정점의 거리를 무한대(∞)로 초기화하고, 시작 정점은 0으로 설정.V - 1번.. 2025. 3. 5. [Computer Algorithms] Prefix Sum (누적 합과 구간 합) 1차원 누적 합과 구간 합#include #include #include #include #include #include #include #include #include #include #define endl '\n'using namespace std;int N;vector arr;vector S; // 누적 합void input(){ cin >> N; arr.resize(N + 1, 0); S.resize(N + 1, 0); for (int i = 1; i > arr[i]; }}void solution(){ for (int i = 1; i > x >> y; cout S[i]는 A[1] + ... + A[i] 이다.S[y] - S[x - 1]은 A[x] + ... .. 2025. 1. 1. [Computer Algorithms] LCS (Longest Common Subsequence, 최장 공통 부분 수열) LCS (Longest Common Subsequence) 두 수열 또는 문자열이 주어졌을 때, 가장 긴 공통 부분 수열(문자열)을 구하는 알고리즘이다. 이 알고리즘은 2차원 DP로 구현할 수 있는데, DP[i][j]는 첫 번째 수열의 i번째, 두 번째 수열의 j번째 원소까지의 LCS의 길이이다. DP 테이블은 DP[i + 1][j + 1] = max({dp[i][j + 1], dp[i + 1][j], dp[i][j] + (A[i] == B[j])})로 갱신할 수 있다.- DP[i + 1][j + 1] = DP[i][j + 1] : 첫 번째 문자열을 i + 1개로 늘려도 늘리기 전과 LCS의 길이가 차이가 나지 않을 때- DP[i + 1][j + 1] = DP[i + 1][j] : 두 번째 문자열.. 2024. 8. 11. [Computer Algorithms] LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) LIS (Longest Increasing Subsequence)말 그대로 가장 긴 증가하는 부분 수열이다. 수열에서 LIS를 구하는 방법은 두 가지가 있다.1. DP를 이용한 방법 -> 시간 복잡도 O(N^2)2. 이분 탐색을 이용한 방법 -> 시간 복잡도 O(N * logN) Finding LIS using DP- LIS의 길이 구하기 (DP)문제 링크 : https://www.acmicpc.net/problem/11053#include #include #include #include #include #include #define endl '\n'using namespace std;int N;vector A, DP;int maxVal = 0;void input(){ cin >> N; A.r.. 2024. 8. 3. 이전 1 2 3 다음
