쾌락없는 책임 (공부)/알고리즘 공부
-
뤼카의 정리 - Lucas' Theorem쾌락없는 책임 (공부)/알고리즘 공부 2023. 1. 27. 15:58
개요 알고리즘 관련 글을 오랜만에 쓰는 거 같은데 공부하고 싶은 수학 알고리즘들이 많아서 하나 잡고 정리를 했습니다. 많이 본 것들 중 하나가 바로 '뤼카의 정리'입니다. 조합에 있어서 조합을 소수 p 로 나눌 때 나머지를 빠르게 구할 수 있는 방법입니다. 간단 기본 지식 오랜만에 수식들을 봐서 그런지 용어들이 익숙하지 않아 이해하는데 시간이 좀 걸렸습니다. 일단 조합은 확률과 통계에서 많이 보이던 아래 식을 의미합니다. 다른 말로 이항계수라고도 합니다. 그리고 뤼카의 정리는 이런 합동식으로 만들어지게 됩니다. 라고 하는데 여기서 '합동식'은 이런 식들을 의미하는데 다른 식으로 이렇게 표현합니다. 말로 풀어보면 'a를 m으로 나눌 때 나머지가 b'라는 뜻입니다. 다른 이야기들이 있는데 일단 넘어가자고요...
-
최소 신장 트리(MST) 구하는 알고리즘 - 크루스칼 알고리즘, 프림 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 10. 17. 22:41
앞선 요약 - 크루스칼 알고리즘은 Union Find 자료구조(=알고리즘)을 알고 있어야 합니다. 합집합 찾기 - Union Find, 유니온 파인드 알고리즘 합집합 찾기 - Union Find 노드들이 존재하고 있을 때 같은 집합에 있는가를 판별하는 알고리즘으로 Diskoint-set 자료구조를 사용하는 알고리즘입니다. 어느 곳에서는 Union Find를 자료구조로 보는 곳 husk321.tistory.com - 간선이 많은 경우 프림 알고리즘, 간선이 적은 경우 크루스칼 알고리즘을 사용하면 효율적입니다. - 본 포스팅은 백준의 1197번 MST 문제를 바탕으로 설명하고 있습니다. 크루스칼 알고리즘 (Kruskal's Algorithm) #include #include #include using nam..
-
최장 증가 부분 수열 - Longest Increasing Subsequence 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 8. 23. 22:15
최장 증가 부분 수열 이 알고리즘을 접하게 된건 백준의 11053번으로 백준 내에서도 시리즈로 있을 정도로 유명한 알고리즘입니다. 영어로 LIS라고 줄여 말하기도 하는 이 알고리즘은 주어진 수열에서 수가 계속 증가하는 부분수열의 최대를 구하는 알고리즘으로 주의해야 할 점은 부분수열이니 순서를 지켜야 한다는 것입니다. 단순 정렬이라면 이렇게 따로 알고리즘이 나올 이유는 없겠죠. 다이나믹 프로그래밍으로 풀이하는 LIS ( 시간복잡도 O(N^2) ) cin >> n; for(int i = 0; i > arr[i]; for(int i = 0; i arr[j]){ ans..
-
합집합 찾기 - Union Find, 유니온 파인드 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 29. 20:09
합집합 찾기 - Union Find 노드들이 존재하고 있을 때 같은 집합에 있는가를 판별하는 알고리즘으로 Disjoint-set 자료구조를 사용하는 알고리즘입니다. 어느 곳에서는 Union Find를 자료구조로 보는 곳도 있지만 저는 알고리즘으로 보고 글을 작성하겠습니다. Union Find의 연산 1. 초기화 일단 트리의 개념을 사용하기 때문에 각 노드들의 부모를 자기 자신으로 초기화 해줘야 합니다. 노드 1 2 ... N 부모 1 2 ... N 초기화를 하면 부모 노드를 가리키는 배열이 위 처럼 초기화 됩니다. 2. Union (= Merge) 두 트리를 합치는 역할을 합니다. 두 트리에 있는 노드들이 가리키는 부모를 통일해 같은 집합으로 넣어주는 연산입니다. 위 표를 업데이트 해보면 아래와 같은 형..
-
CCW - Counter Clockwise, 벡터의 외적쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 28. 20:36
좌표만으로 넓이를 구해야 하는 경우가 있다 간혹 알고리즘 문제를 풀 때 주어진 좌표만으로 넓이를 구해야 하는 경우가 있습니다. 일단적인 직사각형이라고 하면 쉽게 구할 수 있으나 간혹 5각형 이상의 다각형들이 나오기 때문에 이를 위한 알고리즘이 필요하게 됩니다. 이 때 사용하게 되는 알고리즘이 CCW (Counter Clockwise)로 백터의 외적을 이용해서 넓이를 구하는 공식입니다. 외적에 대한 내용은 수학과 관련한 이야기니 코드적으로 알아볼 것만 보겠습니다. CCW CCW = { (x1 * y2) + (x2 * y3) + (x3 * y1) } - { (y1 * x2) + (y2 * x3) + (y3 * x1) } 위 공식이 두 벡터를 통해서 방향성을 구한 것입니다. CCW의 값에 따라 방향이 정해지게..
-
에라토스테네스의 채 - 소수 구하기쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 27. 13:31
에라토스테네스의 채 특정 범위의 소수를 판정하는데 유용한 알고리즘으로 만일 '1개의 수'가 소수인지를 판정하고 싶다면 다른 알고리즘을 사용하는게 더 좋습니다. 기본적인 원리는 수학 시간에 많이 봤습니다. 일단 2를 제외한 배수들을 전부 지우고 그 다음은 3의 배수들, 4는 이미 지워졌으니 5의 배수를... 이런 식으로 수를 지워나가면 됩니다. 아래 위키백과의 사진을 탐고한다면 바로 이해할 수 있을 것입니다. 알고리즘으로서 에라토스테네스의 채 백준 실버 문제부터 자주 등장하게 되며 소수를 판정하는 문제들에 자주 사용하게 됩니다. 특히 범위 내 소수를 구할 수 있다는 알고리즘에서 매력적이며 정말 간단하게 구현이 가능한 알고리즘입니다. 에라토스테네스의 채 알고리즘의 시간복잡도는 O(nlog(logn))으로 꽤..
-
유클리드 호제법 - 최대 공약수 구하기쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 25. 11:17
소스코드 #include using namespace std; int gcd(int n, int m){ int temp; while(m){ temp = n%m; n = m; m = temp; } return n; } 최대 공약수를 구하는 O(log(n+m)) 알고리즘 기본 생각으로 알고리즘을 짜게 되면 nm의 시간 복잡도가 주어지게 됩니다. 1부터 계속해서 수를 검증해야 하기 때문에 테스트 케이스가 너무 많은 경우 시간이 너무 오래 걸려 문제를 풀 수 없게 됩니다. 조금 더 풀어쓰기 위 예시를 봤을 때 나머지가 0이 되는 연산에서의 분모가 최대 공약수가 됩니다. 코딩을 하는게 목적이니 증명에 대해서는 다음에 이야기하겠습니다. 최소 공배수를 구하는 경우 유클리드 호제법으로 최대 공약수를 구한 다음 (val..