본문 바로가기

알고리즘/알고리즘 트레이닝(초록)10

비트병렬 알고리즘 string따위의 자료구조를 사용하는 것보다 정수표현에서 비트연산이 훨씬 빠르다는게 요지인 듯 하다. 0,1로 이루어진 길이가 같은 문자열 s, t에 대해서 해밍거리 hamming(s,t) : 두 문자열이 일치하지 않는 위치의 개수라고 하자. 총 n개의 길이가 k인 문자열 중 두 문자열을 골랐을 때 최소 해밍거리를 구해라. (1) int hamming(string s, string t) { int d = 0; for (int i = 0; i < k; i++) if (s[i] != t[i]) d++; return d; } (2) int hamming(int s, int t) { return __builtin_popcount(a ^ b); } (builtin popcount는 gcc내장함수다. bit 1의 .. 2020. 1. 30.
CSES PS - investigation (다익스트라, 위상정렬) https://cses.fi/problemset/task/1202 볼륨이 크다. 사이클이 허용된 가중치가 있는 방향그래프가 주어진다. 시작점 1에서 끝점 n까지 최소 비용으로 이동할 때, (1)그 비용 (2) 가능한 경로의 수, (3) 가능한 경로 중 가장 적은 간선을 지나치는 경우 그 간선의 수, (4) 가장 많은 간선을 지나는 경우 그 간선의 수. (1),(2),(3),(4)를 모두 구하는 문제 (1)은 다익스트라로 풀 수 있고, (2),(3),(4)는 DAG일 때 dp로 풀 수 있는 내용이다. 사이클이 있는 그래프라고 해도 최소비용으로 이동하는 경로는 항상 DAG임이 분명하다. 1. 주어진 그래프에서 유효한 즉, 최소비용 경로에 해당하는 간선들만 남겨서 DAG를 만든다. dist(1~u) + w +.. 2020. 1. 29.
CSES PS - Elevator Rides (bit, dp) https://cses.fi/problemset/task/1653/ 쉬운 설명의 어려운 문제 bit쓰는 dp중엔 기본문제인 듯 하다. https://suuntree.tistory.com/124?category=797985 비슷한 유형의 더 어려운 문제 최대 20명의 사람들의 몸무게가 주어질 때, 최대 하중이 x인 엘레베이터에 사람을 채워 보내는 최소 운행 횟수를 구해라. (몸무게 2020. 1. 22.
CSES PS - Coin combinations (DP) https://cses.fi/problemset/task/1636 점화식 만들기가 쉽지 않다. https://www.youtube.com/watch?v=DJ4a7cmjZY0 영상설명.. 서로 다른 동전의 가치가 최대 100개 주어질때, 이 동전을 이용해서 정확하게 x원을 사용하는 경우의 수를 구해라. (단, 예를들어, 2 2 2 5와 5 2 2 2 는 같은 경우로 친다) 위에서 든 예시와 같은 경우가 생기지 않도록 동전의 순서를 강제해야 한다. f(k, i) = k원을 만드는데 0~i번째 동전을 순서대로 사용해서 만드는 경우의 수. = f(k-a[i], i) + f(k, i-1) ... ->마지막으로 i번째 동전을 사용하거나, 사용하지 않거나 예제로 dp 테이블을 채워보면 다음과 같다. 테이블이 채워지는.. 2020. 1. 16.

티스토리툴바