코딩스토리

https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 문제 분석 문제 내용 자체는 간단하다. A의 등수는 A보다 앞에 있는 사람 중 A보다 달리기 평소 실력이 낮은 친구가 몇 명인지를 알아야 구할 수 있다. 가장 간단한 방법은 당연히 브루트포스이다. 각 인원마다 자신보다 앞에 있는 사람들의 평소 실력을 비교해보면 된다. 이때 문제의 N제한이 50만이기 때문에 당연히 1+2+3+...+50만 = O(50만*50만+1/2) = O(천억...?) 이..

# 아래 링크의 글에 보충 설명을 더한 글입니다. 먼저 아래 글을 읽고 이해가 잘 안 되신다면 보는 걸 추천드려요 https://www.acmicpc.net/blog/view/21 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X www.acmicpc.net Binary Index Tree의 정의는 wiki에 가서 찾아보는게 더 좋을 것이다. BIT의 필요성 BIT란 쉽게 말해 빠른 속도로 구간 합을 구할 수 있게 도와주는 자료구조이다. 이는 Tree를..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 일반적인 Prefix Sum으로 구하면 query로 인해 시간 초과가 발생한다. 따라서 Binary Index Tree(펜윅 트리)를 사용하여 구해야 하는 문제이다. 아래는 BIT에 대한 설명이다. https://kimtaehyun98.tistory.com/112 Binary Index Tree(BIT, Fenwick Tree) # 아래 ..

확장 유클리드 호제법 기말 기간이라 밀렸던 문제 해결 기법 강의를 듣고 있는데 확장 유클리드 호제법이 나왔다. 유클리드 호제법을 알고 있었고 가끔씩은 백준 푸는 데 사용했었기 때문에 어렵지 않게 이해하고 넘어가야지 했는데 뭐지? 이해가 안가네? 옛날 같았으면 그냥 에라이 모르겠다 하고 넘어갔을 텐데 뭔가 시험에 나올 것 같다는 강렬한 촉이 와서 정리해봤다. (개인적인 이해를 바탕으로 작성했기 때문에 완벽하진 않아요!) 확장 유클리드 호제법을 이해하려면 먼저 유클리드 호제법을 이해해야 한다. 일명 GCD 알고리즘이라고도 불리며 "수학"이란 카테고리에서는 가장 처음 접하는 알고리즘 다운 알고리즘이다. 자세하게 설명하는 건 생략하고 요약하자면 결국 유클리드 호제법을 간단히 말하면 "log 시간안에 최대공약수를..

https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 결국 정보대에서 정보대까지 d번만에 가는 경우의 수를 구해야 하는 문제였다. 이를 일반화해보면 "A 노드에서 B 노드까지 d번만에 가는 경우의 수"를 구해야 한다. 이 부분에 dp 스럽게 생각해보면 "A노드에서 B와 연결된 모든 노드까지 d-1번 만에 도착하는 경우의 수들의 합"과 같다. 즉 식으로 나타내면 다음과 같다. dp [i][j][k] = i 노드에서 j 노드까지 k번 만에 도착하는 경우의 수라고 가정해보자. 그렇다면 dp[i][j][k]는 아래와 같이 구할 수 있다. for(int a = 1; a i..