백준 11689번 문제인 GCD(n, k) = 1 문제는 정확히 오일러 피를 묻는 문제이다. 오일러 피 공식만 코드로 구현하면 끝나는데 난이도가 골드1로 꽤 높은 편이다. 주어지는 수의 범위가 10의 12승으로 매우 커서 오일러 피의 원리를 모르고 단순히 탐색으로 문제를 풀면 시간초과가 발생하기때문에 그런것 같다.  1. 오일러 피 함수란?오일러 피 함수란 자연수 n에 대해 n과 서로소(공약수가 1뿐인 수)인 n이하의 자연수 개수를 구하는 함수이다. ex) n=12 일때n 이하의 자연수중 n과 서로소인 수 : 1, 5, 7, 1112에 대한 오일러 피 함수 결과 = 4  2. 오일러 피 함수의 원리와 사용법먼저 오일러 피 함수를 구현한 코드를 보면 아래와 같다.function eulerPhi(n) { ..

소수란 1보다 큰 자연수중 1과 자기자신만을 약수로 가지는 수 이다. 즉 1과 자기 자신 외의 어떤 수로도 나누어떨어지지 않는다.소수를 구하는 가장 간단한 방법은 1부터 자기자신까지 모든 수로 나누어 보는것이다. 그때 나누어떨어지는 수가 있으면 소수가 아닌것이다.하지만 이러한 완전탐색방식을 사용하면 O(N)의 시간복잡도로 꽤 긴시간이 걸리게 된다.수학적 원리를 이용한 알고리즘을 활용하면 소수를 탐색하는 시간을 줄일 수 있다.   1. 소수 탐색의 기본 조건프로그래밍으로 소수를 탐색하면 반복문을 활용하게 된다. 반복문으로 특정 범위에서 소스를 탐색하기에 앞서 기본적으로 고려해야할 조건이 있다.1은 소수가 아니다.2는 소수이며 2의 배수는 모두 소수가 아니다. (2가 약수이므로)소수를 탐색하기에 앞서 두 조..

투 포인터를 사용해야 하는 문제는 모든 경우의 수를 확인하는 방법(브루트포스)을 사용하면 시간초과가 발생한다. 특정 범위 혹은 특정한 두 값에 대해 문제에서 주어진 조건과 매치를 하는 경우 투 포인터 기법을 활용하여 수행 시간(시간복잡도)을 단축시킬 수 있다.  1. 투포인터란?투 포인터 알고리즘은 배열 혹은 리스트를 순회하면서 두 개의 포인터를 사용해 문제를 해결하는 기법이다.주로 연속적인 구간을 찾거나, 특정 조건을 만족하는 두 요소를 탐색할때 사용된다. 두 개의 포인터 활용배열에서 두개의 포인터를 가지고 특정 조건을 탐색한다. 두 포인터를 합하는 등 단순히 활용할수도 있으며 두 포인터 사이값을 활용하여 특정 조건에 맞는지 검사할 수 도 있다.정렬된 배열에서 주로 사용투 포인터는 좌우 포인터를 이동시..