컴공생 일상 블로그 컴공생 일상 블로그

문제https://www.acmicpc.net/problem/12752 풀이특별한 알고리즘은 없고, 단순 다익스트라 문제이다.많은 도시들이 있고 그 중 K(K   1. K = 1도로가 필요 없음  2. K = 2두 개의 도시를 연결하는 최소 비용을 구하면 된다. 간단하게 다익스트라 1번으로 구할 수 있다.  3. K = 3아래와 같은 경우들이 있을 수 있다. 각 점에서 출발해서 어떤 점에서 만난다고 생각하면 쉽다. K개의 도시(0, 1, 2 정점) N개의 정점에서 만나는 경우 중 비용 합의 최소 값을 구한다.A정점에서 만나는 경우: cost[0][A] + cost[1][A] + cost[2][A]B정점에서 만나는 경우: cost[0][B] + cost[1][B] + cost[2][B]...  4. K =..

문제https://www.acmicpc.net/problem/5670 풀이Trie: https://doraeul19.tistory.com/415전형적인 트라이 문제, 근데 입출력 형식이 여러개의 TC이므로 while(cin >> N)으로 입력받자Insert함수를 구현해서 트리를 잘 만들어주고, Find함수에서 자판을 눌러야하는 횟수를 더해가면 된다. 자판을 눌러야 하는 경우1. 맨 처음 글자: 첫 번째 글자는 무조건 눌러야 한다.2. 다른 문자열과 구분되지 않는 경우    - 현재 문자가 isEnd(다른 문자열의 끝인 경우)    - 다음 문자로 올 수 있는 경우가 2개 이상인 경우 코드#include #include #include #include #include #include #include #in..

어떤 문자열이 어떤 문자열들의 집합에 속하는지 알아내기 위해 단순히 모두 비교할 경우O(문자열의 길이 x 문자열의 개수) 의 시간 복잡도를 가진다. 이 때 문자열을 효율적으로 저장하고 탐색하는 자료 구조가 Trie이다. 대충 O(N) 그냥 그림을 보면 이해가 쉽다. 아래와 같이 4개의 단어가 있다고 해보자. Trie 자료 구조에 각 단어를 담아보면 아래와 같다.    트라이 자료구조는 주어진 문자열에 대해 앞 문자부터 하나씩 노드를 생성하면서 만들어진다. Insert1. 문자열에서 현재 문자를 확인2. 현재 문자로 이루어진 노드가 존재한다면 → 그 노드를 탐색존재하지 않는다면 → 새 노드를 생성 Find1. 문자열에서 현재 문자를 확인2. 자식 노드가 현재 문자인 노드가 있는지 확인, 없다면 return..

문제https://www.acmicpc.net/problem/1854 풀이방법만 알면 쉬운 문제, k 번째의 최단 거리를 구하면 된다.기본 다익스트라를 조금 변형하면 된다.우선순위 큐에 거리를 push하면서 진행하면 된다. K  코드더보기#include #include #include #include #include #include #include #include #include #include using namespace std;int N, M, K;struct Node { int n; long long c; bool operator o.c; }};vector graph[1001];priority_queue pq;priority_queue ret[1001];int main() { ios::sync_wi..

문제https://www.acmicpc.net/problem/11437  설명문제 이름부터 나 LCA 문제입니다. 라고 하고 있는 문제시간 제한도 3초라 O(N)에 대해 돌면서 조상을 구해도 문제 없다.구현자체는 트리에서 level을 구하고 서로 만날 때 까지 올라가면 된다.  parse table에 부모를 저장하면서 O(logN)으로 돌 수 있는데, 이 부분은 나중에 다시...   코드#include #include #include #include #include #include #include using namespace std;int N, M;vector graph[50001];int level[50001];int parent[50001];queue q;void lca(int a, int b) { ..

문제https://www.acmicpc.net/problem/2679Network Flow + DFS  'A에서 B로 가는 중복 비율은 A에서 B로 가는 모든 길을 동시에 이용했을 때 1시간 동안 B에 도착할 수 있는 차의 최대 개수와 길 1개를 이용했을 때 도착할 수 있는 최대 개수의 비율이다.' A. A에서 B로 가는 모든 길을 동시에 이용하는 경우B. 길 1개를 이용했을 때 도착할 수 있는 경우A / B를 구하시오. 원문이 번역된 문제라, 뭔 소리인가 몇 번 읽어봤다. A는 최대유량을 구하라는 의미이고, B는 최대유량으로 구해지는 source->sink의 경로 중 하나에 대한 최대유량을 의미한다. B의 경우에는 최대유량, 다익스트라 돌려보다 결국 DFS로 다 돌렸다.해당 길을 이루는 간선들 중 최소..

https://www.acmicpc.net/problem/18135 생각 없이 풀었다가 당황한 문제칸에 대해 저장하는 것이 아니라, 칸으로 이루어진 각 영역에 대해 도토리를 저장한다.칸을 각 영역으로 한 번 매핑해서 풀어줬다. 나머지는 Lazy-Seg..., 코드가 길어서 실수가 많음, 좀 만 안풀어도 잊혀져버릴듯.#include#include #include #include #include #include #include using namespace std;int N, M;vector tree;vector lazy;int num[2000001];long long arr[1000001];long long Make(int node, int start, int end) { if (start == end..

백트래킹, DFS, BFS, Dijkstra, 이분탐색, 슬라이딩윈도우, 투포인터, 삼분탐색 - 이거 안풀어봄 DPLCS, LIS, 냅섹nlogn 가장 긴 증가하는 부분 수열 기하CCW(Counter Clock Wise)선분교차판정Convex hull(볼록껍질)회전하는 캘리퍼스 - 이건 보다 맘 그래프최대유량(Network Flow)SPFA(Shortest Path Faster Algorithm)MCMF(최소비용최대유량) SCC(강한연결요소) 자료구조SegmentLazy-Segment