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. [Computer Algorithms] DFS & BFS (DFS와 BFS) DFS (Depth-First-Search, 깊이 우선 탐색)루트 노드 혹은 임의 노드에서 다음 브렌치로 넘어가기 전에, 해당 브렌치를 모두 탐색하는 방법이다. 스택 또는 재귀호출로 구현할 수 있다. - 스택을 사용한 DFS#include #include #include #include #include #include #define endl '\n'using namespace std;int N, M, S;vector graph[100];vector visited;vector result;void input(){ cin >> N >> M >> S; visited.resize(N); fill(visited.begin(), visited.end(), 0); for (int i = 0; i.. 2024. 7. 29. [Computer Algorithms] Binary Search (이진 탐색) Binary Search (이진 탐색)이진탐색은 정렬된 배열에서 특정 값을 효율적으로 찾기 위한 알고리즘이다. 이진탐색의 기본 원리는 다음과 같다.1. 배열의 중간 값을 찾는다.2. 찾고자 하는 값과 중간 값을 비교한다.- 찾고자 하는 값이 중간 값보다 크면, 배열의 오른쪽 절반에서 검색을 계속한다.- 찾고자 하는 값이 중간 값보다 작으면, 배열의 왼쪽 절반에서 검색을 계속한다.3. 과정을 반복한다.- 배열의 크기가 0이 되거나 찾고자 하는 값을 찾을 때 까지 이 과정을 반복한다. 이진탐색의 시간 복잡도는 O(log N)으로, 매우 빠르게 검색할 수 있는 장점이 있지만, 배열이 정렬되어 있어야만 이 알고리즘을 사용할 수 있다.Recursive Binary Search (재귀적 이진 탐색)#include .. 2024. 7. 19. [Computer Algorithms] Heap Sort (힙 정렬) Heap 힙의 대한 설명은 다음 글을 참고하자.https://junstory314.tistory.com/entry/Data-Structures-Heap-%ED%9E%99 [Data Structures] Heap (힙)Priority Queue (우선순위 큐) 우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료 구조이다. 우선 순위 큐는 배열이나 연결 리스트로 구현할 수 있지만 데이터의junstory314.tistory.com Heap Sort 힙 자료구조를 활용한 정렬이다.1. 정렬하고자 하는 배열을 힙 구조로 변경한다. -> 시간 복잡도 : O(N)2. 우선순위가 가장 높은 힙의 루트를 힙의 맨 끝으로 보내며, 이를 힙에서 제외한다. -> 시간 복잡도 : O(logN.. 2024. 7. 18. [Computer Algorithms] Sorting in Linear Time : Counting Sort and Radix Sort (계수 정렬과 기수 정렬) Counting Sort (계수 정렬) counting 배열에 정렬하고자 하는 배열의 있는 원소들의 개수를 저장한다. counting 배열의 누적합을 구하면, 누적합의 i번째 값은 i가 정렬된 배열에서 끝나는 인덱스에 1을 더한 값을 의미한다. 따라서 counting[v[i]] - 1이 v[i]가 정렬되었을 때 위치해야 할 인덱스가 된다.#include #include using namespace std;int N;vector v;void input(){ cin >> N; for (int i = 0; i > num; v.push_back(num); }}void countingSort(){ int max_val = *max_element(v.begin(), v.end.. 2024. 7. 13. [Computer Algorithms] Sorting Using Divide and Conquer : Merge Sort and Quick Sort (합병 정렬과 퀵 정렬) Divide and Conquer (분할 정복)큰 문제를 작은 문제 단위로 분할하여 해결해나가는 방식, 이 방식을 통해 구현한 정렬 알고리즘은 대표적으로 Merge Sort와 Quick Sort가 있다. Merge Sort (합병 정렬)배열을 반으로 쪼갠 후, 다시 합병시키면서 정렬해 나가는 방식이다. 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수 있다.#include #include using namespace std;int N;vector v;vector sorted;void input(){ cin >> N; v.resize(N); sorted.resize(N); for (int i = 0; i > v[i.. 2024. 7. 8. [Computer Algorithms] Basic Sorting Algorithms : Bubble Sort, Selection Sort, and Insertion Sort (거품 정렬, 선택 정렬, 삽입 정렬) 1. Bubble Sort (거품 정렬)서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 매 회전마다 회전 구간에서의 최댓값이 최우측으로 간다.void bubbleSort(){ for (int i = 0; i v[j]) { int temp = v[j - 1]; v[j - 1] = v[j]; v[j] = temp; } } }}Best case : O(N^2) (이미 정렬 되어 있어도 버블이 이동하며 대소 비교는 계속 함)Average Case : O(N^2)Worst case : O(N^2) - 장점1. 구현이 매우 .. 2024. 7. 2. [Computer Algorithms] DP : Knapsack Algorithm (냅색 알고리즘) 냅색 알고리즘최대 용량이 K인 가방이 있을 때, 그 가방에 담긴 물건들의 가치의 합이 최대가 되게 하는 알고리즘.#include #include #include #include #include using namespace std;int N, K;vector W, V, dp;void input(){ cin >> N >> K; for (int i = 0; i > w >> v; W.push_back(w); V.push_back(v); }}void solve(){ dp.resize(K + 1, 0); for (int i = 0; i = 0; w--) { dp[w] = max(dp[w], dp[w - W[i]] + V[i]); .. 2024. 7. 1. [Computer Algorithms] Topological Sort (위상 정렬) 위상 정렬 : 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 1. 진입차수가 0인 노드를 큐에 넣는다.2. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.3. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.4. 큐가 빌 때까지 2~3 을 반복한다.#include #include #include using namespace std;int V, E;int indegree[101];vector graph[101];vector result;void topological_sort(){ queue q; for (int i = 1; i > V >> E; fill(&indegree[1], &indegree[V + 1], 0); for (int i .. 2024. 6. 28. [Computer Algorithms] Kruskal's Algorithm (크러스컬의 알고리즘, 최소신장트리) 1. {{노드 x, 노드 y}, 노드 사이 간선의 가중치 w} 를 배열에 저장하고, w를 기준으로 오름차순 정렬한다.2. w가 작은 간선 부터 간선에 연결되어 있는 노드들의 disjoint-set을 구한다.3. 사이클이 존재하지 않는 최소 신장 트리(트리이기 때문에 사이클이 존재하지 않는 것은 당연하다.)의 간선의 합을 구할 수 있다.#include #include #include using namespace std;int V, E;int parent[101];int result = 0;vector, int>> edges;bool compare(const pair, int> &a, const pair, int> &b){ return a.second > V >> E; for (int i = 1;.. 2024. 6. 28. 이전 1 2 다음
