분류 전체보기(301)
-
[중급 알고리즘] 그리디(도전)
💚 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(..
2022.05.17 -
C#을 통해 배우는 동시성 프로그래밍 Part 1.
✔︎ 동시성 한 번에 두 가지 이상의 작업을 수행 ✔︎ 멀티스레딩 다수의 실행 스레드를 사용하는 동시성의 한 형태 ✔︎ 병렬처리 많은 작업을 여러 스레드에 나눠서 동시에 수행 ✔︎ 비동기 프로그래밍 불필요한 스레드의 사용을 피하려고 future나 callback을 사용하는 동시성의 한 형태 ✔︎ 리액티브 프로그래밍 애플리케이션이 이벤트에 대응하게 하는 선언형 프로그래밍 방식 동시성은 멋진 소프트웨어의 핵심적인 특징이다. 최종 사용자 애플리케이션은 데이터베이스에 쓰는 동안 사용자의 입력에 응답하려고 동시성을 사용한다. 서버 애플리케이션은 첫 번째 요청을 완료하는 동안 다른 작업을 수행해야 한다면 동시성이 필요하다. 대부분의 개발자들이 '동시성'이라는 단어를 들으면 즉시 '멀티 스레딩'을 떠올린다. 이 두 ..
2022.05.17 -
[중급 알고리즘] 그리디 (연습)
💚 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)..
2022.05.16 -
[프로그래머스] 섬 연결하기
다익스트라를 연습한 뒤에는 이전에 풀었던 최소 스패닝 트리 알고리즘을 복습하였다. 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..
2022.05.14 -
KMP 알고리즘
문제 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) {..
2022.05.14 -
[백준] 3691: 컴퓨터 조립
https://www.acmicpc.net/problem/3691 3691번: 컴퓨터 조립 각 테스트 케이스에 대해서, 상근이의 예산으로 구매할 수 있는 가장 좋은 컴퓨터의 성능을 출력한다. www.acmicpc.net 지금 생각하면 왜 그렇게 고민을 했나 의문스러운 문제이다. 여기서는 전체 성능을 어떻게 측정하는가가 관건이다. 전체 성능은 곧 구성하는 부품들 중 가장 낮은 성능이다. 그래서 전체 성능을 높이기 위해서는 가장 낮은 성능을 최대한 높여야 한다. 그래서 구성 부품들을 낮은 성능부터 교체하기 위해 최소 힙을 사용하여 정렬한다. 그리고 부품들은 부품별로 가격 오름차순으로 정렬해놓는다. 그래야 동일한 성능이 있더라도 가격이 더 저렴한 부품에 먼저 접근하기 때문이다. 그래서 가장 낮은 성능을 가진 ..
2022.05.13