실수 연산 피하기

문제를 풀다보면 실수 연산을 해야 할 때가 있습니다. 하지만 실수 연산에는 실수 오차가 생겨 결과가 부정확 해질 수 있으며 정수 연산에 비하여 연산 횟수가 많음으로 가능하다면 피하는 것이 좋습니다.

1. double 대신 long long 쓰기
long long 는 -2^62 부터 2^62 - 1까지의 정수들을 저장 할 수 있는 타입입니다. 만약 계산과정이 모두 long long 범위 안에 있고 정수 연산만 필요한 경우 long long을 쓰는 것이 좋습니다.

2. 제곱근 비교
소수인지 판별하기 위하여 흔히 n을 2부터 sqrt(n)까지 나눠봅니다. 비교하는 양변이 모두 양수이므로 제곱하여 정수 연산만으로 i가 sqrt(n)보다 작거나 같은지 비교 할 수 있습니다.

for(int i=2; i<=sqrt(n); i++)

for(int i=2; i*i<=n; i++)

3. 분수 비교
A, B, C, D 모두 정수이고 A/B > C/D 인지를 판별하고자 한다면 다음과 같이 쓸 수 있습니다.

if(1.0*A/B > 1.0*C/D) 

if(A*D > C*B) 

4. 분수의 올림값 계산하기
A, B가 정수고 A/B의 올림값을 계산하고자 할 때 다음과 같이 쓸 수 있습니다.

int C = ceil(1.0*A/B)

int C = (A+B-1)/B

BOJ9012 괄호

문제 요약
입력된 괄호가 올바른 순서를 따르고 있는지를 알아보는 프로그램을 작성하세요.

문제 풀이
스택을 이용합니다.
우선 올바른 괄호라면, 스택이 다음과 같이 처리됩니다.
1. '('를 만나면 반드시 여기에 맞는 ')'가 나와야 하므로, 스택에 push한다.
2. ')'를 만나면 반드시 여기에 맞는 '('가 스택에 들어있어야 하므로, 스택을 pop한다.
3. 입력된 문자열을 모두 처리하고 나면, 스택은 비어 있어야 한다.

잘못된 괄호라면, 다음과 같은 상황이 일어납니다.
1. '('가 나오지 않았는데 ')'가 먼저 나온다. -> 비어 있는 스택에서 pop을 시도한다.
2. '('에 맞는 ')'가 부족하다. -> 입력된 문자열을 모두 처리했는데, 스택이 비어 있지 않다.

주의할 점
스택의 위치를 표시하는 top이 연산 과정에서 -1 -> -2 -> -1로 가는 경우가 발생할 수 있으므로, 잘못된 상황이 벌어지면 루프문에서 바로 빠져나와 잘못되었다는 판단을 한다.


C 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n = -1;
void push(int* stack)
{
 stack[++n] = 1;
}
int pop(int* stack)
{
 if (n >= 0)
  return stack[n--];

}

int empty(int* stack)
{
 return n == -1 ? 1 : 0;
}

int main(void)
{
 int num;
 scanf("%d", &num);
 for (int i = 0; i < num; i++)
 {
  int stack[60];
  char input[60];
  scanf("%s", input);
  for (int j = 0; j < strlen(input); j++)
  {
   if (input[j] == '(')
   {
    push(stack);
   }
   else if(n != -1)
   {
    pop(stack);
   }
   else
   {
    n--;
    break;
   }
  }
  if (n == -1)
  {
   puts("YES");
  }
  else
  {
   puts("NO");
   n = -1;
  }
 }


 return 0;
}

BOJ13236 Collatz Conjecture

문제 링크 : BOJ13236

문제 요약

함수 \( f(n) \)을 다음과 같이 정의하자
$${\displaystyle f(n)={\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}}\\3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$

모든 자연수 n에 대하여 \( f(f(f(...f(n)))) \) 이 항상 1이 되는 순간이 있는지가 콜라츠 추측이다. 아직 이 문제는 미해결 난제로 남아있다.

문제에선 n이 1이 되는 과정을 출력하면 된다.

문제 풀이

반복문을 통하여 변수를 계속 변화시키다가 1이 되는 시점이 오면 종료한다.

소스코드 (C++)

#include <iostream>
using namespace std;

int main()
{
    int n; cin >> n;
    
    while(n != 1)
    {
        cout << n << ' ';
        n = (n % 2 == 0) ? n/2 : 3*n+1;
    }
    
    cout << 1 << '\n';
    
    return 0;
}

소스코드 (Python2)

n = int(raw_input())

while n != 1:
    print n,
    if n % 2 == 0:
        n /= 2
    else:
        n = 3*n+1

print 1

소스코드 (아희)

삭밣밣밣붏
우더더더어　　　　해
아방빵망빵반밧나타추
　　오퍼　누번　　우
콜　　뫃　우추러번뻥
라추　뽀　우붇
츠측　포어어뚜
　　　도터벗벋