본문 바로가기

알고리즘

[Fermat's little theorem] 페르마의 소정리 페르마의 소정리는 아래와 같이 정의 된다. (전제 조건) a와 m이 서로소여야 하며, m이 소수일 경우 $$ a^{m-1} \equiv 1 \ (mod \ m)$$ 페르마의 소정리가 왜 필요할까? 보통은 modulus 연산의 나눗셈을 구하기 위한 응용으로 많이 사용된다. 다시 말하자면, 위의 수식을 아래와 같이 정리해 볼 수 있다는 말이다. $$ a^{m-2} \equiv a^{-1} \ (mod \ m)$$ modular 연산은 덧셈, 뺄셈, 곱셈에 대해서는 분배 법칙이 성립한다. $$ (a+b) \ mod \ m = a \ mod \ m + b \ mod \ m $$ $$ (a-b) \ mod \ m = a \ mod \ m - b \ mod \ m $$ $$ (a \times b) \ mod \ m.. 더보기
[오일러 Phi 함수] Euler totient function 오일러 Phi 함수 $\phi(n)$ 는 1부터 n까지 사이의 수 중에서 n과의 최대공약수가 1인 수의 갯수를 나타내는 함수이다. Phi 함수는 아래와 같은 성질을 만족한다. 1) 만약 p가 소수라면 $\phi(p)$ = p-1 를 만족한다. 2) 만약 p가 소수이고, k$\geq1$라면 1부터 $p^k$까지 정확히 $p^k/p$가 p로 나누어지기 때문에 다음을 만족한다. $\phi(p^k) = p^k - p^{k-1}$ 3) a와 b가 서로소라면 다음을 만족한다. $\phi(ab) = \phi(a) * \phi(b)$ 이를 바탕으로 수식을 정리하면, 아래와 같다. $\phi(n)$ = n * $(1- \frac{1}{p_1})$* $(1- \frac{1}{p_2})$* $(1- \frac{1}{p_3}.. 더보기
[DP 응용] BJ_1398, 동전 문제 이 문제를 Greedy하게만 풀수 있을까? 즉 큰수로 나누어 지면 계속 빼면서 숫자를 구하면 해답일까? 직관적으로 알기 어렵다면 반례를 생각해 보면 된다. 예는 31이 되겠다. 31은 Greedy하게 풀면 25, 1, 1, 1, 1, 1, 1 로 구성되어 총 6개지만, 10, 10, 10, 1로 구성하면 4개로 구성할 수 있다. 따라서 Greedy하게만은 안된다. 그렇다면 DP로만 풀수 있을까? 값의 범위가 $10^{15}$ 로 매우 크기 때문에 배열을 이용해서 단순하게 확장하는 방법으로는 해법에 다가가기 어렵다. 그럼 어떻게 해야한다? 규칙성을 발견해야 한다. 규칙성을 바탕으로 문제를 단순하게 만들 수 있어야 한다. 아래의 글이 도움이 될것 같다. 생각보다 간단하게 작성할 수 있는데, 1부터 100까지.. 더보기
[수학&그래프이론] 제1회 곰곰컵 H번, 곰곰이의 심부름 문제에서 나오는 최단경로로 힌트를 얻을 수 있다. 일단 최단 경로를 구해야 한다. 최단 경로를 구하는 방법도 여러가지지만, 일단 벨만 포드로 구해볼 수도 있을 것 같은데, 벨만포드의 시간복잡도는 O(VE)이기 때문에 현 문제에서는 사용이 불가능할 것으로 보인다. 특별히 간선에 가중치도 없는 것으로 보았을 때 그냥 BFS로 진행해도 될 것 같다. 생각해야 할 부분은 최단 거리를 시작에서 목적지 까지 구하는 것이 아니라, 시작에서 심부름까지 그리고 심부름에서 목적지 까지 따로 구해야 한다는 것이다. 이걸로 한고비 넘겼고, 다음은 경로가 구해지면 어떻게 순서쌍의 갯수를 구하느냐이다. 여기서 수학의 개념이 들어가는데, 처음으로 생각해야 할 점은 이 그래프는 N개의 정점과 N-1개의 간선으로 이루어진 그래프로써,.. 더보기
[DP] BJ_24416, 알고리즘 수업 의사코드를 보고 코드로 풀어낼 수 있으냐를 체크하는 문제. 사실 피보나치 수열의 경우는 Dynamic Programming을 설명하는데 있어서 고전이라고 부를 수 있을 정도로 많이 인용되는 문제다. 한번이라도 들어 보았다면 위의 의사코드를 작성하는 부분은 크게 어렵지 않다고 생각한다. 의사코드를 구현한다. 다만, 한가지 주의해야 할 부분은 함수 호출 부분을 코드의 어디에 위치 시키느냐 인데, 동적 프로그래밍의 경우는 for 문 안에 넣어주면 되고, recursive하게 구하는 경우는 n==1 or n==2의 경우에 리턴되는 경우를 세어주면 된다. def recur(n): global cnt1 if (n ==1) or (n==2): cnt1 += 1 return 1 else: return recur(n-1.. 더보기
[Bit Mask]BJ_14939, 불 끄기 [문제의 접근] 전구 100개가 10x10 모양으로 주어지는 input, 무엇을 떠올려야 할까? 10이하로 주어지는 모양을 보아서는 뭔가 bit mask나 DFS적인 접근이 될거라는 생각이 먼저 떠올라야 한다. 또한 기초적으로 생각해야 할 것들을 적어보자. 1) XOR 연산을 떠올려야 한다. 스위치를 누르면 불이 켜져있을 때는 꺼지게 되고, 불이 꺼져 있을 때는 켜지게 된다. 이는 곧 XOR연산을 의미한다. 0을 꺼짐, 1을 켜짐으로 명명한다고 하면 0 ^ 1 = 1, 1 ^ 1 = 0 이 되니 말이다. 2) (특징) 행렬의 제일 위에서 부터 불을 끄게 된다고 한다면 현재보다 위의 행에 불이 켜져 있다면 반드시 현재 행의 스위치를 눌러야 한다. 예를 들면 위의 예제 입력에서 좌측 상단을 (0, 0)이라고.. 더보기
[Binary Search && Two pointer]BJ_3151, 합이 0 [문제의 접근] 수학 논리적으로 생각해 보았을 때, 위의 문제는 문제의 복잡도가 $O(n^3)$ 인 문제로 N이 충분히 작다면 Bruteforce로 풀리는 문제라고 생각해 볼 수 있다. 그런데 N이 10000 으로 주어졌기 때문에 Bruteforce는 불가능하다. 그렇다면 $O(n^2 log(n)$ 이나 $O(n^2)$의 접근법을 생각해 보아야 한다. 전자의 경우는 시간 초과가 날 것 같은 우려가 있지만, 제한 시간이 4초 이기 때문에 가능성이 있어 보인다. 방법론은 Lower_bound 와 Upper bound를 이용해서 푸는 방법이다. 후자의 경우는 Two-pointer를 이용하면 될 것 같다. 세 수의 합이 0이 되는 조건을 찾는 문제인데, 합은 숫자의 크기에 의존하고 수의 크기는 정렬이 가능하므로.. 더보기
[BFS]BJ_2146, 다리 만들기 0 또는 1로 이루어진 100 x 100 배열에 대해서 0을 1로 채워가면서 연결되는 최소길이를 구하는 문제이다. 어떻게 접근해야 할까? 일단 격자 형태로 좌/우/상/하를 탐색하는 문제의 경우에는 BFS부터 검토해 보는 것이 좋다. 보통의 BFS 문제가 격자를 바탕으로 이루어지기 때문이다. 이 문제도 확장 형태를 보면 BFS로 풀리는 문제라는 것은 어렵지 않게 유추할 수 있다. 다만, 어려운 점은 시작위치와 도착 위치를 어떻게 잡느냐이다. 시작 위치를 어디로 잡아야 할까? 문제에서 시작 위치와 도착 위치가 정해지는 경우는 시작위치를 queue에 넣고 탐색을 진행하되 도착 위치에서 탐색을 종료하면 된다. 그런데 이 문제는 시작 위치와 도착 위치가 불분명하다. 어떻게 시작해야 할까? 문제에서 제시되어 있는 .. 더보기

티스토리툴바