• Daily PS - 211003

    A. BOJ 2961 - 도영이가 만든 맛있는 음식(S1) https://www.acmicpc.net/problem/2961 $n$ 제한이 $10$이어서 각각의 요리를 포함시킬지 아닐지 $2^n$번을 다 해보면 된다. 시간 복잡도 역시 $O(2^n)$이다. 변수 $i$를 $1$부터 $2^n$까지 증가시키면서 $i$의 $j$번째 비트가 켜져 있다면 ( i & (1 << j) 로 확인할 수 있다) $j$번째 요리를 포함시키면 된다. #include using namespace std; using ll = long long; int main() {..

  • Daily PS - 211002

    A. BOJ 1174 - 줄어드는 숫자(S1) https://www.acmicpc.net/problem/1174 최적화를 곁들인 브루트포스를 이용하여 풀 수 있다. $n$자리 줄어드는 수의 개수는 ${}_{10} \mathrm{C}_{n}$개이기 때문에 마지막 줄어드는 수는 $\sum_{k=1}^{10}{_{10} \mathrm{C}_{k}} = 1\,023$번째 수로, $9\,876\,543\,210$이다. $n$자리 줄어드는 수 중 가장 작은 수는 손으로 쉽게 계산할 수 있다. 그리고 여기에서 한 가지 중요한 관찰이 더..

  • Daily PS - 210928

    실력 향상을 위해 오늘부터 BOJ에서 내가 안 푼 문제 중 200명 이상이 풀었고 난이도가 S3 ~ G5 사이인 문제들 중 3개씩 랜덤으로 뽑아서 2시간동안 풀 것이다. 물론 알고리즘 분류 태그와 난이도는 가리고... A. BOJ 14585 - 사수빈탕(S1) https://www.acmicpc.net/problem/14585 도착할 수 있는 최대 지점은 $(300,300)$이다. 또한 사탕을 먹으러 다니는 길에서는 $\rightarrow \uparrow$, 이 두 가지 방향만 사용할 수 있기..

  • 유니온 파인드(Union-Find)

    유니온 파인드(Union-Find), 또는 분리 집합(서로소 집합, Disjoint Set)은 여러 집합들을 표현하는 자료 구조다. Disjoint Set이라는 이름에서도 알 수 있듯이, 이 자료 구조가 표현하는 집합은 서로소이고, 모든 집합의 합집합은 전체집합이다. Union-Find라는 이름은 이 자료 구조가 기본적으로 두 가지 연산, 즉 union 과 find 만을 지원하기에 붙여진 이름이다. union 연산은 두 집합을 하나로 합치는 연산이고, find 연산..

  • 트리(Tree)

    트리(Tree)는 그래프의 일종이다. 이름의 tree는 나무를 뜻하는 것으로, 꼭 나뭇가지가 위로 뻗어 나가는 형상을 닮았다고 해서 이런 이름이 붙여졌다. 다음 조건을 만족하는 그래프를 트리라고 한다. 연결 그래프이다. 간선의 방향을 무시했을 때 사이클이 존재하지 않는다. 다음 그림에서 1, 2번 그래프는 트리이고, 3번은 트리가 아니다. 3번은 간선의 방향을 무시하면 사이클이 생기기 때문에 트리라고 할 수 없다. 위 두..

  • 소수 판정과 소인수분해(Primality Test/Factorization)

    소수(Prime number)는 $1$과 자기 자신을 제외한 양의 정수로는 나누어 떨어지지 않는 $1$이 아닌 양의 정수를 의미한다. 소수가 아닌 수를 합성수라고 한다. $1$은 소수도 합성수도 아니다. 소수에는 여러 흥미로운 성질이 있다. 그 중에서 소수 판정과 소인수분해에 쓰이는 중요한 성질로 어떤 합성수 $n$에 대해 $1$이 아닌 $n$의 약수 중 적어도 하나는 $\sqrt{n}$보다 작다는 성질이 있다. 소수 판정 소수 판정(Primality T..