백엔드 개발자 취업 성공기

문제

해결 방법

계속 원하는 값이 맞게 나오는데 틀렸다고 나와서 상당히 해맸다...
n이 10,000 까지인 것에 주의해서 문제에 접근을 해야 한다. long형으로 변수를 바꿔봐도 overflow가 발생하였다.
자바에서 BigInteger를 이용하여 문제를 해결할 수 있었다.

작성 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

class Main{
    static BigInteger dp[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        dp = new BigInteger[n+2];
        dp[0] = BigInteger.ZERO;
        dp[1] = BigInteger.ONE;

        for(int i=2; i<=n; i++) {
            dp[i] = dp[i-2].add(dp[i-1]);
        }

        bw.write(String.valueOf(dp[n]));

        bw.flush();
        br.close();
        bw.close();
    }
}

문제

해결방법

소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 자연수

이점에서 착안해서 2에서 N - 1로 하는 수를 나머지 연산했을 때 0으로 나눠 떨어지는 경우는 1과 자기 자신이외의 수를 약수로 갖는 것이기 때문에 이 경우에는 소수가 아니다라는 점을 착안해서 문제를 해결하였다.

작성코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int primeCnt = 0;

        for (int i = 0; i < N; i++) {
            boolean isPrime = true;
            int num = scanner.nextInt();
	// 예외처리 1인 경우
            if (num == 1) {
                continue;
            }
			
            for (int j = 2; j <= Math.sqrt(num); j++) {
                if (num % j == 0) { // 소수가 아닌 경우
                    isPrime = false;
                    break;
                }
            }
		// 소수인 경우
            if (isPrime) {
                primeCnt++;
            }
        }
        System.out.println(primeCnt);
    }
}

집합(Set)

특정 조건에 맞는 원소들의 모임
기본적으로 집합은 중복된 원소를 추가할 수 없다.

😃집합 표현 방법

• 원소나열법
• 조건제시법
• 벤 다이어그램

원소나열법
A = {1, 2, 3, 4, 5}, B = {2, 4, 6, 8, 10}

조건제시법
A = {A | A는 정수, 1 ≤ A ≤ 5}
B = {2B | B는 정수, 1 ≤ B ≤ 5}

벤 다이어그램

집합의 종류

• 합집합
• 교집합
• 차집합
• 여집합
  
  

합집합

어느 하나에라도 속하는 원소들을 모두 모은 집합

교집합

두 집합이 공통으로 포함하는 원소로 이루어진 집합

차집합

A(or B)에만 속하는 원소들의 집합(ex A - B)

여집합

전체집합(U)에서 A의 원소가 아닌 것들의 집합

자바에서 집합 구현

import java.util.Arrays;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {

//      1. 자바에서 집합 사용 - HashSet
        System.out.println("== HashSet ==");
        HashSet set1 = new HashSet();
        set1.add(1);
        set1.add(1);
        set1.add(1);
        System.out.println("set1 = " + set1);
        set1.add(2);
        set1.add(3);
        System.out.println("set1 = " + set1);
        set1.remove(1);
        System.out.println("set1 = " + set1);
        System.out.println(set1.size());
        System.out.println(set1.contains(2));
        

//      2. 집합 연산
        System.out.println("== 집합 연산 ==");

//      2-1. 교집합
        HashSet a = new HashSet(Arrays.asList(1, 2, 3, 4, 5));
        HashSet b = new HashSet(Arrays.asList(2, 4, 6, 8, 10));
        a.retainAll(b);
        System.out.println("교집합: " + a);

//      2-2. 합집합
        a = new HashSet(Arrays.asList(1, 2, 3, 4, 5));
        b = new HashSet(Arrays.asList(2, 4, 6, 8, 10));
        a.addAll(b);
        System.out.println("합집합: " + a);

//      2-3. 차집합
        a = new HashSet(Arrays.asList(1, 2, 3, 4, 5));
        b = new HashSet(Arrays.asList(2, 4, 6, 8, 10));
        a.removeAll(b);
        System.out.println("차집합: " + a);

    }

}