📝 Computer Science

[C++] 문자열

문자열 1. KMP 알고리즘 문자열 검색을 빠르게 구하기 위한 알고리즘이다. 1) 기본 원리 접두사(prefix)와 접미사(suffix)를 이용해 pi[i] 배열을 구한 뒤 활용한다. pi[i] 배열은 0~i까지의 부분 문자열에서 prefix=suffix가 될 수 있는 부분 문자열 중 가장 긴 것의 길이이다. 이때, prefix가 0~i까지의 부분 문자열과 같으면 안 된다. 예를 들어 문자열 ABAABAB로 pi[i] 배열을 구해보자. i 부분 문자열 (0~i) pi[i] 0 A 0 1 AB 0 2 ABA 1 3 ABAA 1 4 ABAAB 2 5 ABAABA 3 6 ABAABAB 2 그렇다면 이 pi[i] 배열을 어떻게 활용하여 문자열 검색을 효율적으로 할 것인가? 문자열 ABCDABCDABEE에서 문자..

클라우드 컴퓨팅(Cloud Computing)과 AWS

1. 클라우드 컴퓨팅(Cloud Computing) 인터넷을 통해 전산 자원(서버, 데이터베이스, 네트워킹 등)을 공유하는 기술과 도구의 집합이다. 어디서든 하늘을 봤을 때 구름(Cloud)을 볼 수 있는 것처럼, 어디서든 자원에 접근 가능하다. 1) 왜 클라우드 컴퓨팅을 사용할까? 1. 비용 사용한 만큼만 지불한다. 하드웨어 및 소프트웨어를 구입하거나 온사이트 데이터 센터를 설치 및 운영하는 비용을 줄일 수 있다. 즉, 초기 투자 비용 및 운영 비용을 절감할 수 있다. 2. 속도 대부분 클라우드 컴퓨팅 서비스는 주문형 셀프서비스로 제공된다. 따라서 기업에 많은 유연성이 제공되며 기업은 용량 계획 부담을 덜 수 있다. 3. 뛰어난 확장성 필요한 때에 적절한 지리적 위치에서 대략적인 컴퓨터 성능, 스토리지..

[C++] 네트워크 유량(Network Flow)

네트워크 유량(Network Flow) 그래프 개념 중 하나로 네트워크 유량을 이해하기 위해선 먼저 새로운 용어와 유량 그래프의 특징부터 알아야 한다. 유량 그래프는 보통 방향 그래프인 경우가 많다. 그래프의 간선 거리, 시간이나 가중치 대신 용량(Capacity)이라 한다. 두 정점 u, v를 있는 간선 (u, v)가 있을 때, u에서 v로 간선의 용량 이하만큼의 유량(flow)을 흘려보낼 수 있다. 그래프 내 서로 다른 소스(S, Source) 정점과 싱크(T, Sink) 정점이 있는데, 소스 정점은 유량을 발생시킨다. 소스 정점 외 정점들은 자신이 받은 유량만큼만 다시 흘려보낸다. 각 간선에 흐르는 유량은 그 간선의 용량을 넘을 수 없다. 간선 (u, v)로 유량이 흐르고 있다면 역방향인 간선(v,..

[C++] 희소 테이블(Sparse Table)

희소 테이블(Sparse Table) 배열이 정적이어야 한다. 즉, 배열 내용이 수정되면 안 된다. 배열의 아이디어는 분할 정복과 비슷하지만 더 빠르다. 기본 원리 모든 정점의 간선이 1개인 유향 그래프가 존재할 때 어떤 정점에서 시작해 k번 이동을 하면 도착하는 점은 유일하다. 이때 k번을 일일이 매번 따라가며 도착점을 계산할 수도 있겠지만 k값이 커질수록 시간도 오래 걸릴 것이다. 만약 어떤 정점의 n번 이동했을 때 도착점, 또 그 도착점을 정점마다 다 기억하는 배열이 있다면 도착점을 매우 효율적으로 구할 수 있을 것이다. 그렇다면 이 배열은 어떻게 가져야 할까? 1칸, 2칸, 4칸, 8칸, 16칸,... 등 2진수를 이용해 2진수에 해당하는 이동 값을 모두 배열로 만든다. 그리고 이동 횟수 k를 2..

[C++] 위상 정렬(Topological Sort)

위상 정렬(Topological Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위한 알고리즘이다. 여러 개의 답이 존재할 수 있다. DAG(Directed Acyclic Graph)에만 적용이 가능하다. 스택과 큐로 구현된다. 기본 원리 진입 차수가 0인 정점을 큐에 삽입한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거 후 진입 차수가 0이 된 정점을 큐에 삽입한다. 큐가 빌 때까지 2번 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다. 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ..

[C++] 펜윅 트리(Fenwick Tree)

펜윅 트리(Fenwick Tree) 펜윅 트리는 바이너리 인덱스 트리(Binary Indexed Tree)라고도 부른다. 순서를 갖는 데이터가 주어졌을 때, 구간의 대표 값이나 연산 결과를 빠르게 얻을 수 있는 트리 형태의 자료구조이다. 기본 원리 https://www.acmicpc.net/blog/view/21 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X www.acmicpc.net 펜윅 트리를 구현하기 위해선 어떤 수를 이진수로 나타냈을 때 마..