💚 1201 NMK - 가장 긴 증가하는 부분 수열의 문제는 대부분 다이나믹 프로그래밍이나 그리디의 형식으로 문제를 푼다. - 적어도 M개의 정수는 증가 수열에 포함되어야 하고 - 적어도 K개의 정수는 감소 수열에 포함되어야 한다. - 두 수열은 최대 정수 1개를 공유할 수 있기 때문에 - N >= M + k + 1이어야 한다. - 또 N은 MK를 넘을 수 없다. - N = MK + 1인 경우에 길이가 M + 1인 증가 수열이나 길이가 K + 1인 감소 수열을 반드시 만들 수 있따. - 비둘기집 원리로 증명할 수 있음 - Erdos-Szekeres Theorem 증가하는 수열을 뒤집으면 반드시 감소하는 수열이 된다. ex) 3478 ➡️ 8743 M + K - 1 n >> m >> k; vector a(..

✔︎ 동시성 한 번에 두 가지 이상의 작업을 수행 ✔︎ 멀티스레딩 다수의 실행 스레드를 사용하는 동시성의 한 형태 ✔︎ 병렬처리 많은 작업을 여러 스레드에 나눠서 동시에 수행 ✔︎ 비동기 프로그래밍 불필요한 스레드의 사용을 피하려고 future나 callback을 사용하는 동시성의 한 형태 ✔︎ 리액티브 프로그래밍 애플리케이션이 이벤트에 대응하게 하는 선언형 프로그래밍 방식 동시성은 멋진 소프트웨어의 핵심적인 특징이다. 최종 사용자 애플리케이션은 데이터베이스에 쓰는 동안 사용자의 입력에 응답하려고 동시성을 사용한다. 서버 애플리케이션은 첫 번째 요청을 완료하는 동안 다른 작업을 수행해야 한다면 동시성이 필요하다. 대부분의 개발자들이 '동시성'이라는 단어를 들으면 즉시 '멀티 스레딩'을 떠올린다. 이 두 ..

💚 1541 잃어버린 괄호 - 식에 괄호를 적절히 쳐서 식의 값을 최소로 만드는 문제 - -가 나오면 항상 뒤의 +(더하기) 식을 모두 묶으면 가장 큰 값을 뺀다. - 어려운 부분: +와 숫자를 분리하는 부분 #include #include using namespace std; int main() { string s; cin >> s; vector num; vector sign; bool minus = false; int cur = 0; // 모든 숫자는 항상 양수이기 때문 sign.push_back(1); // 문자열에서 숫자와 부호 분리 for(auto c : s) { if(c == '+' || c == '-') { // +면 1, -면 -1 if(c == '+') { sign.push_back(1)..

다익스트라를 연습한 뒤에는 이전에 풀었던 최소 스패닝 트리 알고리즘을 복습하였다. https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 모든 섬을 최소한의 비용으로 연결한다는 점에서 MST(최소 스패닝 트리)에 관한 문제라는 점을 간파해야 한다. 최소 스패닝 트리의 경우 크루스칼 알고리즘이 편해서 적용했던 것 같다. 가중치가 적은 간선부터 정렬한 뒤, 사이클이 생기지 않는다면 그리디하게 간선을 가져오면 된다. 여기서는 벡터를 쓴 후 정렬했는데, 우선순위 큐를 써도 괜찮다. 그리고 사이클을 검사하는 것은 Union..

문제 https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net #include #include using namespace std; string p, s; vector pi((1e6) + 1); void make_pi(string p) { // i는 접두사, j는 접미사 인덱스 // pi 배열은 접두사와 접미사가 일치하는 최대 길이 long long i = 0, j = 1; long long p_len = p.length(); pi[0] = 0; while(j < p_len) {..

최소 비용을 구하는 알고리즘 중 이 문제는 출발점과 도착점 간 거리만 최소로 구하면 되므로 다익스트라 알고리즘을 쓰면 된다. 사용한 자료구조 ✔︎ vector dist 출발점으로부터의 거리 기록 ✔︎ vector weights 출발점별로 (도착점, 간선 길이) 기록 ✔︎ priority_queue pq 최소 힙에 출발점 기준 거리와 노드 기록 처음에 다익스트라를 시작할 때 start에 대한 초기화가 필요하다. dist[start] = 0 세팅한 후 (start, 0)라는 pair를 만들어서, 즉 start로부터의 거리를 start부터 삽입해야 한다. 그 후 간선이 짧은 순으로 출발점으로부터 거리가 단축되는지 확인한다. /** * https://www.acmicpc.net/problem/1916 * 출발점..