[코딩테스트 대비]알고리즘 기본문제 (덧셈, 나머지연산, 유클리드)

Fundamental

코딩테스트를 처음 준비하거나 알고리즘 문제를 풀기 전에 간단히 풀어보면 좋은 유형들을 모아보았다.
처음에는 간단한 입 출력부터 연습을 하고 사칙연산을 통해 기본을 마무리 한 후에 나중에 나올 유형들을 풀 때 유용하게 쓰이는 것들을 연습해 볼 수 있도록 모아두었다.

 

입 출력

• 2557번 Hello World

• 11718번 그대로 출력하기

덧셈 연산

• 1000번 A+B
• 2558번 A+B -2
• 10950번 A+B -3
• 10951번 A+B -4
• 10952번 A+B -5
• 10953번 A+B -6
• 11021번 A+B -7
• 11022번 A+B -8
• 15552번 빠른 A+B

 

나머지 연산

참고 : A+B % N = (A % N) + (B % N), (A-B) % N = ((A % N) - (B % N) + N)

• 10430번 나머지

 

자료형

BigInteger

• 10757번 큰 수 A+B

  참고 : Java Scanner와 BigInteger 사용하기

Buffer

• 15552번 빠른 A+B

 

최대공약수, 최소공배수

유클리드 호제법활용 GCD: 재귀함수, LCM = g(a/g)(b/g)

재귀함수를 이용한 GCD 계산

int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    gcd(b, a % b);
}

• 2609번 최대공약수와 최소공배수
• 1934번 최소공배수
• 9613번 GCD 합

 

확장 유클리드 알고리즘

기존 유클리드 호재법이 A, B의 최대공약수를 구할 때 O(max(logA, logB))만의 시간이 걸린다.

확장 유클리드 알고리즘은 최대공약수 뿐만 아니라, 정수해를 가지는 부정방적식 Ax+Bx=C가 있다고 했을때 A, B의 최대공약수를 구함과 동시에 이 방식식을 만족하는 x, y값들을 찾는다.

해가 존재하려면 C가 GCD(A, B)의 배수여야 한다.

 

소수, 에라토스테네스의 체

소수 : 약수가 1과 자기자신밖에 없는 수

N이 소수가 되려면, 2보다 크거나 같고, root N보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

bool prime(int n) {
  if (n < 2)
    return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0)
      return flase;
  }
  return true;
}

시간복잡도 : O(root N)

• 1978번 소수 찾기

에라토스테네스의 체 : 1부터 N까지 범위 안에 들어있는 모든 소수를 구하려면 에라토스테네스의 체를 쓰면된다.

/* 100까지의 소수*/
void eratos() {
  boolean[] chk = new boolean[101];
  chk[0] = chk[1] = true;
  for (int i = 2; i * i <= n; i++) {
    if (chk[i])
      continue;
    for (int j = i * 2; j <= n; j += i)
      chk[j] = true;
  }
}

• 1929번 소수 구하기

안쪽 for문의 j값은 N 범위에 따라 i*i or i+i로 바꿔준면 된다. (int 범위)