[java] 코딩테스트 벼락치기

코딩테스트/알고리즘

[java] 코딩테스트 벼락치기

k9yuw 2024. 8. 9. 21:56

dfs, bfs

- 탐색이 동시성을 가지는 경우 (ex 한 칸 움직일 때 값이 변하는 경우), 최소거리를 찾아야하는 경우는 bfs가 낫다.

dfs
1. 체크인
2. 목적지인가?
3. 연결된 곳을 순회
4. 갈 수 있는가?
5. 간다
6. 체크아웃

bfs
1. 큐에서 꺼내오기
2. 목적지인가?
3. 연결된 곳을 순회
4. 갈 수 있는가?
5. 체크인
6. 큐에 넣는다

- dfs 시작점 잘 보기. 여러번 for문으로 돌려서 여러 시작점에서 시작해야 하는 경우 있음

- dfs 들어갈 때 들어가는 상태 맞추기

자료구조

- 세그먼트 트리(빈출)

- Trie 클래스 작성 예시(참고문제: 9202. Boggle)

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord;
    boolean isHit;

    void clearHit() {
        isHit = false;
        for (int i = 0; i < children.length; i++) {
            if (children[i] != null) {
                children[i].clearHit();
            }
        }
    }

    boolean hasChild(char c) {
        int idx = c - 'A';
        return this.children[idx] != null;
    }

    TrieNode getChild(char c) {
        return this.children[c - 'A'];
    }
}

정수론

- 유클리드 호제법

public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

그래프

- union-find

- topological sort

1) 초기: indegree 0인 노드들을 큐에 추가

2) 큐가 빌 때 까지

a. 큐에서 노드 뽑고

b. 큐에서 뽑은 노드에 연결된 간선 다 삭제

c. 삭제된 간선에 따라 indegree 1 감소시켜주고

d. indegree 0 되는건 큐에 넣음

- MST: Kruskal

1) 간선 cost 오름차순으로 정렬한 다음에 하나씩 꺼냄

2) find 연산해서 cycle 형성 안하면 union

3) N-1개 간선 선택하면됨

- LCA

- 다익스트라

1) pq에 cost 오름차순으로 엣지 넣어서 정렬하고

2) 하나씩 꺼내서

3) visited 방문 표시 하고

4) dist[next] > dist[curr] + cost 인 경우 dist[next] = dist[curr] + cost 만들고

5) 큐에 또 넣음

- 벨만포드

1) 이중포문 노드 N -> 엣지 M 만큼 dist[next] > dist[curr] + cost 인경우 dist[next] = dist[curr] + cost 하도록 돌리고

2) M만큼 한 번 더 돌려서 변화 있으면 음수 사이클 존재

- 플로이드워셜

3중 포문 : k, i, j 순서 - dist[i][j] > dist[i][k] + dist[k][j] 인 경우 dist[i][j] = dist[i][k] + dist[k][j]

정렬

스트림 쓰는게 제일 편리함 (오름차순 정렬)

내림차순 하고싶을 때는 .reversedOrder() 이나 .reversed 붙이면 됨

list.sort(Comparator.comparing(Person::getHeight).thenComparing(Person::getWeight));

근데 Weight을 내림차순 하고싶어서 .reversed()를 뒤에 붙여버리면 Height, Weight에 둘 다 적용돼서 둘다 내림차순 되버림 ㅠ

하나 오름차순, 하나 내림차순일때일때는 이렇게 쓰는게 젤 직관적이고 쉬운거같은데 람다식 쓰는 방법도 있고 방법은 많다

(단 메서드 내부에 선언해야됨)

Comparator<Person> byHeight = Comparator.comparing(Person::getHeight);  // Height 오름차순
Comparator<Person> byWeightDesc = Comparator.comparing(Person::getWeight).reversed();  // Weight 내림차순
ArrayList<Person> list = new ArrayList<Person>();
list.sort(byHeight.thenComparing(byWeightDesc));

그 외 팁

- 1초가 걸리는 입력의 크기

(출처: https://velog.io/@jelkov/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%A4%80%EB%B9%84-Tip)

O(N) : 100,000,000
O(NlogN): 5,000,000
O(N^2): 10,000
O(N^3): 500
O(2^N): 26
O(N!): 11

- int : 2147483647

- 글로, 종이로, pseudocode 충분히 써보고 구현 들어갈 것

- 경계값 등등 히든테케 나올법한거 테스트 해보기

- toString 메서드 잘 오버라이딩해서 디버깅시 찍어보기

    @Override
    public String toString() {
        return String.format("학생 (이름 = %s, 학번 = %d)", name, studentNum);
    }

문자열 (String): %s
정수 (int, long): %d
실수 (float, double): %f
char : %c
불리언 : %b

- 아는거 나오길 기도해라...

- 24.11.23 추가

: 웹ide로 보는 시험의 경우(구름 등) 메서드명같은걸 외워가야 할 것 같다. String 관련 메서드가 toCharArray랑 contains, length 세개만 생각나서 시간 많이 잡아먹었다;; 이클립스도 짜증난다고 생각했는데 이건 디버깅도 못찍어보고 메서드도 못보고 그냥 더 열받는다.