[java] 코딩테스트 벼락치기
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
- 아는거 나오길 기도해라...