패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 강의 2주차

패스트캠퍼스 알고리즘 강의 2주차!

이번주는 ch4.완전탐색에 대해 배웠다.

 

 

 

완전탐색 이란?

- 모든 경우의 수를 시도한다. (brute force)

- 즉, 별도의 최적화 없이 효율성을 고려하지 않는 풀이 방법

- 효율을 생각하지 않기 때문에 문제의 크기가 작으면 유용하다.

- 문제의 크기가 클수록 시간/공간복잡도가 늘어나 적용이 어려울 수 있다.

- 완전한 정답이 아니라도 문제를 이해하거나, 테스트케이스를 확인하기 위한 용도로 적용해볼 수 있다.

- 부분점수 문제라면 전체를 풀지 못해도 작은 데이터에 대한 점수를 얻을 수 있다.

 

---

10448 유레카 이론

https://www.acmicpc.net/problem/10448

10448번: 유레카 이론

** preprocess()로 공통 함수 빼기

package 그리디;

import java.util.Scanner;

public class gd1 {

    static boolean[] isEurekaNumber = new boolean[1001];
    public static void preprocess(){
        //1. K보다 작은 삼각수를 모두 구한다.
        int[] triangleNumbers = new int[50];
        int triangleNumberCount = 0;
        int cnt = 0;
        for(int i=1;;i++){
            int triangleNumber = i * (i+1) / 2;
            if(triangleNumber >= 1000) break;
            triangleNumbers[triangleNumberCount++] = triangleNumber;
        }
        //2. 구해진 삼각수 세개의 합으로 K를 나타낼 수 있는지 확인한다.
        for(int i=0; i< triangleNumberCount; i++)
            for(int j=0; j<triangleNumberCount; j++)
                for(int k=0; k<triangleNumberCount; k++) {
                    int sum = triangleNumbers[i] + triangleNumbers[j] + triangleNumbers[k];
                    if (sum <= 1000) isEurekaNumber[sum] = 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

https://www.acmicpc.net/problem/11005

11005번: 진법 변환 2

** 아스키 잊지 말기

package 그리디;

import java.util.Scanner;

public class gd2 {

    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 D = N%B;
            if(D<10) ans += D;
            else ans += (char)(D - 10 + 'A');
            N = N/B;
        }

        for(int i=ans.length() - 1; i>=0; i--)
            System.out.print(ans.charAt(i));
    }
}

 

---

11068 회문인 수

https://www.acmicpc.net/problem/11068

11068번: 회문인 수

 

* 두 단어 같은 지 비교 시 /2로 비교하기~~

package 그리디;

import java.util.Scanner;

public class Main {
    private static int[] convertBase(int x, int B) {
        int len = 0, copyX = x;
        while (copyX>0){
            copyX/=B;
            len++;
        }
        int[] digit = new int[len];
        len = 0;
        while(x>0){
            digit[len++] = x % B;
            x = x/B;
        }
        return digit;
    }
    public static boolean isPalindrome(int[] digit){
        for(int i=0;i<digit.length/2;i++)
            if(digit[i] != digit[digit.length - i - 1])
                return false;
            return true;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while ( T --> 0 ) {
            int x = sc.nextInt();
            boolean ans = false;
            for(int i=2;i<=64;i++){
                int[] digit = convertBase(x,i);
                if (isPalindrome(digit)) {
                    ans = true;
                    break;
                }
            }
            System.out.println(ans ? "1" : "0");
        }
    }

}

 

 

회문인 수 문제!

 

 

 

 

강의 링크 :  https://fastcampus.co.kr/dev_online_codingtest

 

 

 

 "본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다."