하루 코딩 하루 코딩

Algorithm

• Lowest common ancestor(LCA)

  Algorithm/LCA 2020. 3. 23. 10:46

  LCA 트리에서 서로 다른 두 노드에 대해 루트노드에서 가장 멀리 있는 공통 조상을 LCA라고 합니다. 위의 그림에서 검은색 노드의 LCA는 빨간색 입니다. LCA를 찾는 방법은 1. 두 노드의 dept를 맞춘다. 2. 두 노드가 같아질때까지 계속 위로 올라간다. 2단계롤 나눌수 있습니다. 가장 쉽게 구현할수 있는 방법은 하나씩 올라가는 것입니다. 이 경우엔 최악의 경우 O(n)의 시간 복잡도를 가지게 됩니다. 더 빠르게 구현하기 위해서 '희소테이블' 이라는 테크닉을 이용할 수 있습니다. 즉 하나씩 올라가는 것이 아니라 가능한 최대한 멀리 올라가는 것이지요. 예를들어 두 노드 A, B의 LCA인 C노드의 깊이가 3이고 A의 깊이는 100, B의 깊이는 200 이라고 하면, 하나씩 올라가는것은 너무 정직하..

  Read More

• ACM Craft - 1005

  Algorithm/BOJ 2020. 3. 22. 03:07

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 //1005 - ACM Craft #include #include using namespace std; int N, K; vector adj; int cost[1001]; int S; int cache[1001]; void init() { cin >> N >> K; for(int i = 1; i cost[i]; int x, y; for(int i = 0; i> x >> y; adj[y].push_back(x); } cin >> S; } in..

  Read More

• YouTube - 3117

  Algorithm/BOJ 2020. 3. 20. 04:26

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 //3117 - youtube #include using namespace std; int N, K, M; int arr[100001][31]; int student[100001]; void init() { cin >> N >> K >> M; for (int i = 0; i > student[i]; for (int i = 1; i > arr[i][0]; for (int j = 1; j

  Read More

• 희소 테이블(Sparse Table)

  Algorithm/희소 테이블 2020. 3. 20. 03:41

  https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하시오. www.acmicpc.net 위의 문제를 풀기위해 사용되는 테크닉 입니다. 합성함수를 해결하기 위해 n번 반복하는 것이 아닌 미리 테이블을 만들어 특정원소에서 1번 갔을때, 2번갔을때, 4, 16, 32 ...... 와 같이 이진수의 자리수만큼 이동했..

  Read More

• Scoring Hack - 17234

  Algorithm/BOJ 2020. 3. 20. 01:45

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 //Scoring Hack #include using namespace std; int N, A, B; bool cache[601][501][51]; void init() { cin >> N >> A >> B; cache[0][0][0] = true; } bool dp(int score, int turn, int dturn) { if(score

  Read More

• 가운데를 말해요 - 1655

  Algorithm/BOJ 2020. 3. 19. 20:29

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 //1655 - 가운데를 말해요 #include #include using namespace std; int N; priority_queue hq, tq; void init() { hq = tq = priority_queue(); cin >> N; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(); int x; int ht, tt, hsize, tsize; c..

  Read More

• 교환 - 1039

  Algorithm/BOJ 2020. 3. 19. 17:53

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 //1039 - 교환 #include using namespace std; int N, K; int length; int cache[11][1000001]; void init() { cin >> N >> K; string s = to_string(N); length = s.size(); for(int i = 0; i

  Read More