코테 대비 패턴 모음

자바 long 타입 사용시 주의점

• 자바는 숫자 리터럴에 L 접미사를 붙여주지 않으면 int취급!!!

long wrong = 1_000_000_000 * 1_000_000_000;
// 이러면 int*int라 오버플로우 발생!!! (wrong == -1486618624)

long right = 1_000_000_000L * 1_000_000_000;
// 한쪽에 `L`을 붙여서 long 리터럴로 만들어줘야 오버플로우 안 생김

long error = 2_147_483_648;
// int범위를 넘어서는 리터럴을 L 접미사 없이 사용하면 컴파일 에러가 발생한다!!
// error: integer number too large

• 배열 크기, Collection의 인덱스, 크기관련 메서드는 모두 파라미터로 int를 받고 int를 리턴!!

Queue.size()                    // 컬렉션의 size()는 항상 int형을 리턴함
String.length()                 // String의 length()도 마찬가지

long[] arr = new long[(int)3L]  // 배열의 크기는 int형만 가능
// long[] err = new long[3L]

List.get(3)                     // 인덱스는 int형이어야 함
String.charAt(7)                // 인덱스는 int형이어야 함
String.substring(2, 3);         // 인덱스는 int형이어야 함

오버플로우 없는 평균

int a = 2_147_483_647;
int b = 3;

int avg = a + (b-a)/2;

나눗셈 결과 올림 처리

int dividend = 7;
int divisor = 3;

int ceil = (dividend + divisor - 1) / divisor;

에라토스테네스의 체

• 소수 판정이 필요할 때, 범위가 넓다면 거의 무조건 이거 쓰는거

boolean[] sieve = new boolean[N+1]; // 1-based 인덱스 쓰기 위해 크기+1
Arrays.fill(sieve, true);

sieve[1] = false;
for (int i = 2; i*i <= N; i++) {
    if (sieve[i]) { // 현재 수가 소수라면
        for (int j = i*i; j <= N; j+=i) {
            sieve[j] = false; // 그 수의 배수는 모두 소수가 아니다
        }
    }
}

반복문 불변식을 활용한 파라메트릭 서치

int search() {
    int fr = -1; // 조건을 항상 만족하는 지점에서 시작
    int rr = N+1; // 조건을 항상 만족하지 `않는` 지점에서 시작

    while (fr+1 < rr) {
        int mid = fr + (rr-fr)/2;

        if (check(mid)) { // 조건을 만족하는지 확인
            fr = mid;
        } else {
            rr = mid;
        }
    }

    return fr; // 조건을 만족하는 최댓값
    // return rr; // 조건을 만족하지 않기 시작하는 지점
}

이분탐색

int search(int[] arr, int target) {
    int fr = -1;
    int rr = arr.length; // 범위설정 주의! `0`이랑 `length-1`이 아니다

    while (fr+1 < rr) {
        int mid = fr + (rr-fr)/2;

        if (arr[mid] < target) {
            fr = mid;
        } else {
            rr = mid;
        }
    }
    // 반복이 끝나면 rr에 `조건을 만족하지 않기 시작하는 지점`이 담긴다
    // rr == `arr[mid] >= target` 시작되는 지점 == Lower Bound

    if (rr < arr.length && arr[rr] == target) {
        return rr;
    } else {
        return -1; // // rr이 갱신된 적 없거나 타겟과 다르다면 찾지 못한것
    }
}

유니온 파인드 (DSU 구현체)

class DSU {

    int[] parent;
    int[] size;

    DSU(int n) {
        parent = new int[n+1];
        size = new int[n+1];

        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]]; // path halving 기법
            x = parent[x];
        }

        return x; // `x == parent[x]` 의 의미? `루트까지 올라왔다`
    }

    boolean union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) return false;

        if (size[pa] < size[pb]) {
            // size[pa]가 size[pb]보다 작다면 pa와 pb의 순서를 바꿔주고 시작
            int tmp = pa;
            pa = pb;
            pb = tmp;
        }
        
        parent[pb] = pa;
        // 작은놈의 부모를 큰 놈으로 바꾼다 == 큰 놈을 작은놈의 부모로 만든다
        size[pa] += size[pb];
        // 부모의 크기를 자식 크기만큼 키운다
        return true;
    }
}