[Java] 기본 문법 정리 - 비트 연산, 수학 라이브러리, 시간 복잡도 개념

✅ 14. 비트 연산 (Bitwise Operations)

비트 연산은 정수형 데이터의 이진수 표현을 직접 조작하는 연산.
빠른 연산이 필요하거나 특정 패턴을 체크할 때 유용.

---

📍 1) 비트 연산자 정리

연산자 설명 예제 (a=5, b=3)

&	비트 AND	5 & 3 = 1 (0101 & 0011 = 0001)
|	비트 OR	5 | 3 = 6 (0101 | 0011 = 0111)
^	비트 XOR	5 ^ 3 = 6 (0101 ^ 0011 = 0110)
~	비트 NOT	~5 = -6 (보수 연산)
<<	왼쪽 시프트 (2배 연산)	5 << 1 = 10 (0101 → 1010)
>>	오른쪽 시프트 (1/2 연산)	5 >> 1 = 2 (0101 → 0010)

---

📍 2) 비트 연산 예제

public class BitwiseExample {
    public static void main(String[] args) {
        int a = 5;  // 0101
        int b = 3;  // 0011

        System.out.println("AND: " + (a & b)); // 1 (0001)
        System.out.println("OR: " + (a | b));  // 7 (0111)
        System.out.println("XOR: " + (a ^ b)); // 6 (0110)
        System.out.println("NOT: " + (~a));    // -6
        System.out.println("Left Shift: " + (a << 1));  // 10 (1010)
        System.out.println("Right Shift: " + (a >> 1)); // 2 (0010)
    }
}

📌 시프트 연산 활용
✔️ n << k → n × 2^k
✔️ n >> k → n ÷ 2^k

---

📍 3) 특정 비트 확인 (& 연산)

public class BitCheck {
    public static void main(String[] args) {
        int num = 5;  // 0101
        int bitPos = 1; // 0부터 시작 (두 번째 비트)

        boolean isSet = (num & (1 << bitPos)) != 0;
        System.out.println("두 번째 비트가 1인가? " + isSet); // true
    }
}

📌 비트가 켜져 있는지 확인할 때 num & (1 << k) 사용

---

📍 4) 비트 토글 (^ 연산)

public class BitToggle {
    public static void main(String[] args) {
        int num = 5;  // 0101
        int bitPos = 1; // 두 번째 비트 변경

        num ^= (1 << bitPos);
        System.out.println(num); // 7 (0111)
    }
}

📌 특정 비트를 토글(0↔1) 하고 싶을 때 num ^= (1 << k) 사용

---

✅ 15. 수학 관련 라이브러리 (Math 클래스 활용)

자바는 기본적인 수학 연산을 Math 클래스를 통해 제공.

📍 1) 최대값, 최소값 (max(), min())

int a = 10, b = 20;
System.out.println(Math.max(a, b)); // 20
System.out.println(Math.min(a, b)); // 10

---

📍 2) 절댓값 (abs())

System.out.println(Math.abs(-10)); // 10

---

📍 3) 거듭제곱 (pow())

System.out.println(Math.pow(2, 3)); // 8.0 (2^3)

---

📍 4) 제곱근 (sqrt())

System.out.println(Math.sqrt(16)); // 4.0

---

📍 5) 반올림 (round()), 올림 (ceil()), 내림 (floor())

System.out.println(Math.round(3.6)); // 4 (반올림)
System.out.println(Math.ceil(3.2)); // 4 (올림)
System.out.println(Math.floor(3.8)); // 3 (내림)

---

✅ 16. 시간 복잡도 개념

코딩 테스트에서는 알고리즘의 실행 속도를 분석하는 것이 중요.
시간 복잡도(Time Complexity)는 입력 크기 N이 증가할 때, 연산 횟수가 얼마나 증가하는지를 나타냄.

📍 1) 주요 시간 복잡도

시간 복잡도	예시
O(1)	단순 연산 (ex: a + b)
O(log N)	이진 탐색
O(N)	단순 반복문
O(N log N)	정렬 (Merge Sort, Quick Sort)
O(N²)	이중 반복문
O(2^N)	재귀 (피보나치, 백트래킹)
O(N!)	순열, 조합

---

📍 2) 시간 제한에 따른 최대 N 크기

시간 제한	허용되는 최대 N 값 (대략적인 기준)
1초	10^7 (약 1천만)
2초	2 × 10^7
5초	5 × 10^7

📌 반복문이 O(N²)이면 N=10,000만 넘어가면 시간 초과 가능성 높음

---

📍 3) 예제: 시간 복잡도 비교

O(N) (선형 탐색)

public class LinearSearch {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 7;
        
        for (int num : arr) {
            if (num == target) {
                System.out.println("찾음!");
                break;
            }
        }
    }
}

📌 최악의 경우 N번 실행 → O(N)

---

O(log N) (이진 탐색)

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        System.out.println(Arrays.binarySearch(arr, 7)); // O(log N)
    }
}

📌 N이 커질수록 이진 탐색이 훨씬 빠름!

---

🎯 마무리: 코딩테스트 필수 자바 문법 정리

1️⃣ 기본 문법: 자료형, 연산자, 조건문, 반복문
2️⃣ 자료 구조: 배열, 리스트, 맵, 셋, 스택, 큐, 우선순위 큐
3️⃣ 정렬 & 탐색: Arrays.sort(), 이진 탐색
4️⃣ 그래프 탐색: DFS, BFS
5️⃣ 동적 프로그래밍(DP): 메모이제이션
6️⃣ 비트 연산: 비트마스크 활용
7️⃣ 수학 라이브러리: Math 클래스
8️⃣ 시간 복잡도 개념: O(1), O(logN), O(N), O(N²), O(2^N)

📌 코딩 테스트에서 가장 중요한 건 문제를 보고 "어떤 알고리즘이 필요한지" 빠르게 판단하는 것! 🚀