[코딩테스트] (완전탐색,시뮬레이션) & [10448] 유레카 이론 & [11005] 진법 변환2

완전탐색

• • 즉 무식하게 모든 케이스를 다 시도해보는 것
  • 문제해결의 가장 기본적인 방법
  • 정답률 100% 보장완전탐색이란 모든 경우의 수를 시도한다.

 

• 모든 경우의 수를 체계적으로 검사할 수 있도록 설계해야 함.
  • 문제가 요구하는 바를 이해하고, 정확히 구현할 수 있어야 한다.
• 가장 쉽고 간단한 접근
  • 효율을 생각하지 않기 때문에 문제의 크기가 작으면 유용하다.
  • 문제의 크기가 클수록 시간/공간복잡도가 늘어나 적용이 어려울 수 있다.
  • 완전한 정답이 되지 못하더라도 문제를 이해하거나 테스트케이스를 확인하기 위한 용도로 적용해볼 수 있다.
  • 부분점수 문제라면 전체를 풀지 못해도 작은 데이터에 대한 점수를 얻을 수 있다.
  • 선형 완전탐색, 비선형 완전탐색등이 있으나 아직은 선형탐색만

시뮬레이션

• 문제에 주어진 상황을 그대로 진행하며 해결해보는 기법
• 문제의 요구사항에 알맞은 코드 모델링, 문제의 조건만 체계적으로 수행하기 위해 구현력 필요함.

[10448] 유레카 이론

문제

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

자연수 n에 대해 n ≥ 1의 삼각수 Tn는 명백한 공식이 있다.

Tn = 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

• 4 = T1 + T2
• 5 = T1 + T1 + T2
• 6 = T2 + T2 or 6 = T3
• 10 = T1 + T2 + T3 or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

문제풀이

이 문제는 삼각수가 Tn = n(n+1)/2 이다. 최대 3개의 삼각수가 합으로 표현한 것을 EurekaNumber라고 하자.

문제는 3개의 Tn을 이용하여 EurekaNumber를 만족하는 Number를 찾으면 된다!

1. 모든 삼각수를 구한다.

• triangleNumbers의 크기를 50개로 지정한 이유는 Tn = n(n+1)/2 때문이다. 45부터 1000의 크기를 넘기 때문에 44부터 가능하다.

• 무한루플 하며 triangleNumber를 triangleNumbers배열에 저장하고 만약 triangleNumber가 1000보다 크다면 조건에 부합하지 않으므로 break를 실행

/// 시간복잡도 O(triangleNumberCount)  

public static int getTraingleNumbers(int[] triangleNumbers. int K) {
	int triangleNumberCount = 0;
	
	for (int i=0; ; i++) {
		int triangleNumber = i(i+1)/2; // Tn 공식 대입
		if (triangleNumber > 1000) break;
		triangleNumbers[triangleNumberCount++] = triangleNumber;
	}
	return triangleNubmerCount;
}

2. 주어진 숫자를 세 개의 삼각수의 합으로 표현할 수 있는지 확인.

triangleNumbers 배열에는 Tn 조건을 만족한 값들의 수열이 있음. 이것을 활용하여 3개의 값을 더하였을때 EurekaNumber를 구할 수 있음.

/// 시간복잡도 O(triangleNumberCount^3)
public static boolean isEurekaNumber(int[] triangleNubmers, int triangleNumberCount, int K) {
        for (int i = 0; i < triangleNumberCount; i++)
            for (int j = i; j < triangleNumberCount; j++)
                for (int k = j; k < triangleNumberCount; k++) {
                    int eurekaNumber = triangleNumbers[i] + triangleNumbers[j] + triangleNumbers[k];
                    if (sum == k) return true;
                }
                return false;
                }
       }

/// 시간복잡도: O(T * (triangleNumberCount + triangleNumberCount^3))
public static void main(Stringp[] args) {
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	while(T-->0) {
		int K = sc.nextInt();
		int[] triangleNumbers = new int[50]; 
		int triangleNumberCount = getTriangleNumbers(triangleNumbers, K);
		boolean ans = isEurekaNumber(triangleNumbers, triangleNumberCount, K);
		System.out.println(ans ? "1" : 0);		
	}
}

3.1 시간복잡도 개선하기

아래 코드를 테이스케이스마다 매번 구할 필요가 있을까?

생각해보면 TriangleNumber의 값은 달라지지 않는다. 사용범위만 달라질뿐 공통적으로 한번만 사용하도록 변경

/// 시간복잡도: O( T + (triangleNumberCount + triangleNumberCount^3))
	int[] triangleNumbers = new int[50]; 
	int triangleNumberCount = getTriangleNumbers(triangleNumbers, K);

모든 EurkeaNumber를 구해두는 함수를 생성하여 반복 최소화

/// 최종 시간복잡도: O(K * triangleNumberCount)
import java.util.Scanner;

class Main
{
    static boolean[] isEurekaNumber = new boolean[1001];

    public static void preprocess() {
        int[] triangleNumbers = new int[50];
        int triangleNumberCount = 0;
        for (int i = 1; ; i++) {
            int triangleNumber = i * (i + 1) / 2;
            if (triangleNumber > 1000) break;
            triangleNumbers[triangleNumberCount++] = triangleNumber;
        }

        for (int i = 0; i < triangleNumberCount; i++)
            for (int j = i; j < triangleNumberCount; j++)
                for (int k = j; k < triangleNumberCount; k++) {
                    int eurekaNumber = triangleNumbers[i] + triangleNumbers[j] + triangleNumbers[k];
                    if (eurekaNumber > 1000) break;
                    isEurekaNumber[eurekaNumber] = true;
                }
    }

    public static void main (String[] args) {
        preprocess();

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int K = sc.nextInt();
            System.out.println(isEurekaNumber[K] ? "1" : "0");
        }
    }
}

[11005] 진법 변환2

문제

10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

입력

첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) N은 10억보다 작거나 같은 자연수이다.

출력

첫째 줄에 10진법 수 N을 B진법으로 출력한다.

문제풀이

일단 숫자는 어떻게 각 진법으로 나타내는지 진법 변환을 해보자.

36진법에 적용하는 방법

• 100을 36진법으로 나타냈을때 가장 큰 자릿수의 지수 K를 찾는다. 36^1 ≤ 100 < 36^2
• 100에 들어갈 수 있는 36^1항의 자릿값 D1을 구한다. 2 * 36^1 ≤ 100 < 3 * 36^1 ( 36^1항의 자리값 D1 = 2)
• 다음에 구해야 할 자릿수의 표현범위를 넘는 값을 제외한다. 100 % 36^1 =. 8

10진법 N을 B진법으로 변환하기

• X를 B로 나눈 나머지를 구하고 B로 나눈다. 0이 될때까지 반복 가장 마지막 나머지부터 가장 앞 자릿값이 된다. N에 들어갈 수 있는 B^k항의 자릿값 Dk를 구한다.

String ans = ""; while(N>0) { int digit = N % B; if(digit < 10) ans += digit; else ans += (char)('A' + digit - 10); N /= B; }

• 마지막부터 계산을 하여 ans에 저장하기 때문에 뒤집어 출력을 해야 한 다.

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int B = sc.nextInt();

        String ans = "";
        while (N > 0) {
            int digit = N % B;
            if (digit < 10) ans += digit;
            else ans += (char)('A' + digit - 10);
            N /= B;
        }

        System.out.println(new StringBuilder(ans).reverse());
    }
}

시간복잡도

N을 B로 나눠 0보다 작아질때까지 반복하니 O(logbN)이다.