임시) 정수론

소수 구하기

 

개념은 쉽게 이해되고, 시간 복잡도가 nlog(logn)이라는 게 신기하네 정도.

 

37번, 소수 구하기

에라토스테네스를 이해해가지고 코딩으로 구현하는 코테 문제가 많이 나와요. 

 

• n의 제곱근까지만 탐색하는 이유
  • 즉 예로 16은 (1,16), (2,8), (4,4) 이렇게 약수가 있지. 
  • 이 때 우린 1, 2, 4 즉 괄호의 왼쪽 부분만 탐색하고 싶은 거야
  • 왜 굳이 오른쪽 부분, 즉 16, 8, 4 이런 부분까지 일일이 루프 돌면서 해당 수와 짝지어 지는 약수 있는지 탐색해야 함?
  • 이미 n의 제곱근 이하인 수로만 탐색해서 소수 아닌 거 다 판별하면, 그럼 n의 제곱근 이상의 수들을 가지고 다시 할 필요 없지. 이미 다 했는데. 이미 n 제곱근 이상의 수들을 가지고 해당 수로 나눠지는 걸 판별하는 짓을 할 필요 없는거지
• for (int j = i + i; j <= N; j = j + i)
  • 소수의 배수를 지우는 부분

38번, 거의 소수 구하기

• 입력에서 주어진 범위의 최댓값 10의 14제곱의 제곱근인 10의 7제곱까지 소수 탐색해야 함
  • 10의 7제곱까지 탐색하면 되니까, 정답 코드에서 배열의 크기를 10000001으로 잡아놓은 거임

• (double)A[i] <= (double)Max/(double)temp
  • 무슨 뜻? 그러니까 거의 소수는 어떤 소수의 n제곱한 값이니까
  • 원래는 a[i](소수) x temp(즉 소수의 n제곱) <= max인지를 따지는 건데 
  • 소수의 n제곱을 해주면 long 범위를 초과하니 이 조건식에서 넘겨준 것(교재에선 아마 이 부분을 이항정리라고 표현한 것 같음 => 이항정리라는 표현이 여기에 쓰이는 건가? (a+b)의 n제곱 이런 형태가 이항정리 아니였나, 굳이 이 표현 신경쓰지 마

39번, 소수&팰린드롬 수 중에서 최솟값 찾기

• 팰린드롬 수 판별법
  • 수를 char 배열로 형 변환 -> 배열의 처음과 끝을 가리키는 포인터를 부여해 두 값을 비교 => 두 값이 같으면 s++, e--로 포인터 이동 => s<e일 때까지 반복해 모든 값이 같으면 판별 완료
• 왜 소수를 10000000, 즉 천만까지 구하는가? => 굳이 이렇게 해야 할 필요는 없다.
  • N은 최대 100만 => 문제에서 요구하는 것은 N 보다 '크거나 같은 수'중 소수이면서 팰린드롬인 수 => 100만까지만 소수를 구해서는 안된다.
  • 약간 범위를 늘려봐서 확인해보면 되는데 => 1,003,001는 n이 최대 범위인 백만일 경우 소수이면서 팰린드롬인 수 중 가장 작은 수(최초)이기 때문이다. 어차피 문제가 요구하는 게 이거니까.

40번, 제곱이 아닌 수 찾기

• 언뜻 보면 min의 최댓값이 1,000,000,000,000라서 매우 큰 것 같지?
  • 하지만 min ≤ max ≤ min + 1,000,000잖아?
  • 그러니까 min이 1,000,000,000,000(10의 12제곱)이라도, max는 10의 12제곱 + 백만이짆아. 
  • 그리고 우리는 min과 max 사이의 수들 안에서 정답을 구하면 되는 거고. 그러니 백만의 데이터만 확인하면 됨
• 제곱수 판별을 일반적인 반복문으로 구하면 시간 초과 => 에라토스테네스의 체 알고리즘 방식을 응용해서 => 제곱수 판별 로직에 적용해 문제 해결
  • 즉 데이터 순차적으로 탐색하는 것이 아니라, 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색해 시간 복잡도를 최소화하는 것이 핵심
• 제곱으로 나눠떨어지는 건 check 배열에 true로 체크하는 식으로(즉 제외하는 식으로) 코드 짰네

 

long start_index = Min / pow;

if (Min % pow != 0) start_index++;

• 역할
  • 이 부분의 코드는 배열의 시작 인덱스를 계산하는 데 사용됩니다.
  • 이를 통해 Min 값보다 크거나 같은 가장 작은 제곱수의 배수를 찾습니다.
• 자세한 설명
  1. 기본 계산:
     • Min / pow는 Min을 pow로 나눈 몫을 계산합니다. 이 몫은 Min보다 작거나 같은 pow의 배수를 나타냅니다.
  2. 예제:
     • 예를 들어, Min = 10이고, pow = 9라고 가정합시다.
     • start_index = 10 / 9 = 1입니다. 이는 9의 배수 중 Min보다 작거나 같은 값입니다. 즉, 9 * 1 = 9는 Min보다 작거나 같은 제곱수의 배수입니다.
  3. 나머지 처리:
     • 이제 Min % pow != 0 부분을 살펴봅니다.
     • 10 % 9 = 1이므로 나머지가 1입니다. 이 경우 start_index에 1을 더해야 합니다. 왜냐하면, 9는 Min보다 작기 때문에 우리는 Min보다 큰 다음 제곱수의 배수를 찾아야 합니다.
     • start_index++는 start_index를 2로 만듭니다. 이는 9 * 2 = 18을 나타냅니다. 이는 Min보다 큰 가장 작은 제곱수의 배수입니다.
• 요약
  • start_index = Min / pow는 Min보다 작거나 같은 제곱수의 배수를 찾습니다.
  • Min % pow != 0이면 나머지가 있으므로 start_index를 1 증가시켜 Min보다 큰 가장 작은 제곱수의 배수를 찾습니다.

 

(j * pow) - Min 이 부분이 이해 안 돼. 특히 Min 값을 왜 빼주는 거야?

• 목적
  • Check 배열은 Min부터 Max 사이의 값을 인덱스로 사용하는 배열입니다. Check 배열의 크기는 (Max - Min + 1)입니다. 이 배열에서 true로 표시된 위치는 해당 위치에 있는 숫자가 제곱수의 배수임을 나타냅니다.
• 계산 예제
  1. Min과 Max의 예제:
     • Min = 10
     • Max = 20
  2. Check 배열:
     • 크기는 Max - Min + 1 = 20 - 10 + 1 = 11
     • Check 배열의 인덱스는 0부터 10까지입니다.
  3. 제곱수와 시작 인덱스:
     • 예를 들어, i = 2일 때, pow = 2 * 2 = 4
     • start_index는 10 / 4 = 2 (그리고 10 % 4 != 0이므로 start_index++하여 start_index = 3)
• for (long j = start_index; pow * j <= Max; j++) { Check[(int) ((j * pow) - Min)] = true; }
  1. start_index로 시작:
     • j = start_index에서 시작합니다.
     • 예제에서는 start_index = 3입니다.
  2. 제곱수의 배수를 확인:
     • pow * j가 Max보다 작거나 같은 동안 반복합니다.
     • pow * j = 4 * 3 = 12입니다.
  3. 인덱스 계산:
     • Check[(int) ((j * pow) - Min)]에서 Min을 빼는 이유는 Check 배열의 인덱스를 정확히 맞추기 위해서입니다.
     • j = 3일 때, Check[(int) ((3 * 4) - 10)] = Check[2]입니다.
  4. 값 설정:
     • Check[2] = true로 설정됩니다.
     • 이는 12가 제곱수의 배수임을 나타냅니다.
• 구체적인 예제
  • 주어진 값
    • Min = 10
    • Max = 20
    • pow = 4
  • 반복문 실행
    1. 첫 번째 반복:
       • j = 3
       • j * pow = 3 * 4 = 12
       • 인덱스: (3 * 4) - 10 = 12 - 10 = 2
       • Check[2] = true (즉, 12는 제곱수의 배수)
    2. 두 번째 반복:
       • j = 4
       • j * pow = 4 * 4 = 16
       • 인덱스: (4 * 4) - 10 = 16 - 10 = 6
       • Check[6] = true (즉, 16은 제곱수의 배수)
    3. 세 번째 반복:
       • j = 5
       • j * pow = 5 * 4 = 20
       • 인덱스: (5 * 4) - 10 = 20 - 10 = 10
    • Check[10] = true (즉, 20은 제곱수의 배수)
• 이유
  • Check 배열은 Min부터 시작하는 인덱스를 가지므로, 실제 값과 배열 인덱스를 맞추기 위해 Min을 빼줍니다.
  • 이렇게 하면 배열의 인덱스가 0부터 시작하게 되며, Min값을 포함하는 범위에서 정확한 위치를 가리킵니다.

오일러 피

 

• 코테에서 자주 나오진 않는다. 그러나 알면 풀 수 있지만 모르면 접근하기 힘들다.
  • ⇒ 가벼운 마음으로 오일러 피가 뭔지 알고 가면 좋을 듯하다
  • 단 출제되었을 때 원리를 알지 못하면 문제 자체에 접근하기 어려움

 

문제 41, 오일러 피 함수 구현하기

• 내가 예전에 교재에 메모해 놓은 거 참고하면 이해됨.

 

유클리드 호제법

 

• 유클리드 호제법은 두 수의 최대 공약수 구할 때 씀
• 정리하면 gcd(큰 수, 작은 수)인데
  • 큰 수 % 작은 수 = 나머지 ⇒ 각각을 일종의 자리로 보자.
  • 100 % 30 = 10이면 다시 ⇒ 30 % 10 = 0이 되지
  • 즉 어떤 작은 수 30으로 나누면 나머지는 무조건 30보다 작을 수밖에 없음 ⇒ 즉 30을 큰 수 자리로, 나머지 10을 작은 수 자리로 옮기고 다시 같은 모듈러 연산을 반복하기 위해 계속 반복한다는 소리
• 재귀 형태로 구현하면 됨

 

문제 42, 최소공배수 구하기

• 최소공배수는 수 A, B가 주어졌을 때 => A*B / 최대 공약수로 계산해서 구할 수 있음
  • 즉 이 문제는 유클리드 호제법으로 최대 공약수 구한 후
  • 두 수의 곱에서 최대 공약수를 나눠 주는 것으로 해결 가능

 

if (b == 0) return a;  => 예로 a가 3이고 b가 0이라고 쳐. 그럼 gcd의 반환값이 3이 되는데, 애초에 gcd의 반환값은 두 수의 최대공약수잖아. 그런데 3, 0일 땐 최대공약수가 없는데 왜 3을 반환해?

• 유클리드 호제법은 두 수의 최대공약수를 찾는 효율적인 알고리즘입니다. 이 알고리즘은 다음과 같은 원리에 기반합니다:
  • GCD(a,b)=GCD(b,a%b)
  • 이 과정을 반복하여 b가 0이 될 때, 그 시점의 a가 최대공약수입니다.
• b=0인 경우의 특별한 처리
  • 어떤 수 a에 대해, GCD(a,0)=a입니다. 이는 수학적으로 정의된 사실입니다. 즉, 어떤 수와 0의 최대공약수는 그 수 자신입니다.
  • 이 정의는 유클리드 호제법의 종료 조건을 의미합니다. b=0일 때 재귀 호출을 멈추고 현재의 a를 반환하는 것입니다.
• 왜 GCD(a,0)=a인가?
  • 수학적으로, 0은 모든 수의 배수로 간주됩니다. 따라서 0과 다른 수 a의 공통 약수는 a 자체입니다.
  • 예를 들어:
    • a=3일 때, 3의 약수는 1, 3입니다. 0의 약수는 모든 수입니다. 따라서 3과 0의 공통 약수는 1, 3이고, 최대공약수는 3입니다.
    • a=15일 때, 15의 약수는 1, 3, 5, 15입니다. 0의 약수는 모든 수입니다. 따라서 15와 0의 공통 약수는 1, 3, 5, 15이고, 최대공약수는 15입니다.

 

문제 43, 최대 공약수 구하기

• 일반적인 출력 수행하면 시간 초과가 발생할 수 있으므로 => BufferedWriter를 사용함
  • 아, 즉 출력 횟수가 많을 땐 BufferedWriter를 쓰면 되구나
• 이 문제는 유클리드 호제법이 메인이 아님
  • 그냥 사소한 아이디어 사용해야 풀 수 있는 문제

 

문제 44, 칵테일 만들기

• 이 문제도 유클리드 호제법은 그냥 떨거지고 
• 핵심은 DFS네
  • 문제에서 N-1개의 비율로 N개의 재료 전체 비율을 알아낼 수 있다고 했다 
  • => 이를 그래프 관점으로 생각하면 사이클 없는 트리 구조로 이해할 수 있음
  • DFS 과정에서 유클리드 호제법 사용해 => 비율들의 최소 공배수와 최대 공약수를 구하고, 재료의 최소 질량을 구하는 데 사용
• 사이클 없는 트리 구조?
  • 트리의 정의와 속성
    • 연결 그래프: 트리는 모든 노드가 서로 연결된 연결 그래프입니다. 즉, 어떤 두 노드도 경로를 통해 연결되어 있습니다.
    • 사이클 없음: 트리는 사이클이 없는 비순환 그래프입니다. 이는 트리에서 한 노드에서 시작하여 다시 그 노드로 돌아오는 경로가 존재하지 않음을 의미합니다.
    • 노드와 간선의 관계: 트리의 간선 수는 노드 수 - 1입니다. 예를 들어, n개의 노드를 가진 트리는 항상 n−1개의 간선을 가집니다.
  • 트리와 일반 그래프의 차이
    • 트리: 연결성(모든 노드가 연결됨)과 비순환성(사이클이 없음)을 가지며, 노드 수가 n일 때 간선 수는 n−1입니다.
    • 일반 그래프: 연결되지 않을 수 있으며, 사이클이 존재할 수 있습니다. 간선 수는 노드 수와 특정 관계가 없을 수 있습니다.

 

• D[next] = D[node] * i.getQ() / i.getP();  이 부분이 이해 안 돼 왜 이런 계산식이 나오는 거야?
  
   
  • cNode 구성은 다음 노드, 비율 p, 비율 q임.
  • 이 때 p는 앞의 비율, q가 다음 노드의 비율임
  • 위 식을 풀면 D[next] * p=D[node] * q임 => 즉 원랜 현재 노드: 다음 노드 = p:q => 즉 현재 노드 질량이 p일 때, 다음 노드 질량이 q라는 소리
  • 극단적으로 현재 노드 = p, 다음 노드는 q로 대체해서 보면 이해 쉬움 => 그럼 q*p=p*q임

 

확장 유클리드 호제법

45번, Ax + By = C

• 일단 이해가 안 됨. 일단 넘어가. 확장 유클리드 호제법 훑어봤지만 나중에 수준 높아지면 그 때 보지 

 

  public static long gcd(long a, long b) {
    if (b == 0)
      return a;
    else
      return gcd(b, a % b);
  }

    private static long gcd(long a, long b) {
        while(b!= 0) {
            long temp = a%b;
            a=b;
            b=temp;
        }
        return Math.abs(a);
    }

 

• 두 gcd 함수는 어떤 점이 다른거지?
  • 코드 구조:
    • 코드1: while 반복문과 임시 변수를 사용하여 값을 반복적으로 업데이트합니다.
    • 코드2: 조건문과 재귀 호출을 사용하여 문제를 작게 나누어 해결합니다.
  • 성능 차이:
    • 일반적으로 두 방법의 시간 복잡도는 동일하지만, 반복문을 사용한 구현이 재귀를 사용한 구현보다 호출 스택 오버헤드가 적어 약간 더 효율적일 수 있습니다. 특히 큰 입력 값에 대해서는 스택 오버플로우의 위험이 없으므로 반복문이 더 안전할 수 있습니다.
    • 재귀를 사용한 구현은 코드가 간결하고 이해하기 쉬운 장점이 있습니다. 다만, 재귀 깊이가 깊어지면 스택 오버플로우의 위험이 있습니다.
  • 그럼 왜 밑의 함수에선 a를 반환하지 않고 Math.abs(a);를 반환해?
    • 최대공약수는 항상 양수로 정의되기 때문에, 어떤 경우에도 양수를 반환하도록 보장하는 것입니다. 코드2에서는 이러한 처리가 포함되어 있지 않지만, 일반적인 경우 양수의 GCD를 구할 때는 문제가 되지 않습니다.
  • 이유: 절대값 반환의 필요성
    • GCD의 정의:
      • GCD는 항상 양수입니다. 따라서 gcd(a, b)의 결과는 양수여야 합니다.
    • 부호의 가능성:
      • 두 숫자 중 하나가 음수일 경우, 반복 계산 중 a 또는 b가 음수가 될 수 있습니다. 이는 최대공약수의 정의에 어긋나므로, 최종 결과를 절대값으로 변환하여 양수로 만듭니다.
    • 재귀의 특성:
      • 재귀 함수에서는 b가 0이 되는 경우를 기저 조건으로 처리하고, 그 시점의 a를 반환합니다.
      • 일반적으로 GCD 계산에서 a와 b가 음수가 되지 않기 때문에 절대값을 반환할 필요가 없다고 간주할 수 있습니다.
      • 하지만 일관성을 위해, 코드2에서도 절대값을 반환하도록 수정하는 것이 좋습니다.
    • 반복문으로 구현한 함수는은 항상 양수를 반환하기 위해 Math.abs(a)를 사용합니다. 이는 GCD가 음수가 되지 않도록 보장합니다.
    • 재귀로 구현한 함수는 재귀적으로 GCD를 계산하며, 일반적으로 양수 결과가 나오지만, 특정 입력에서 음수가 나올 수 있습니다. 따라서 일관성을 위해 Math.abs(a)를 반환하는 것이 좋습니다.