"구현·시뮬레이션 문제를 풀 때 어떤 순서로 설계하고 구현하며, 입력 크기로 허용 시간 복잡도를 어떻게 가늠하고, Java에서 입출력과 자료구조를 어떻게 골라 시간 초과와 흔한 실수를 피하는가?" 이 페이지는 그 질문에 답한다. 원문은 구현 문제에서 문제를 있는 그대로 코드로 옮기는 것이 핵심이라고 본다.[1] 그래서 이 페이지는 하나의 알고리즘이 아니라 반복해서 쓰는 절차, 어림 기준, 코드 도구, 점검 목록을 다룬다. 어떤 설계 전략을 고를지는 Algorithm Design Strategies가 다룬다.
| N 범위 | 허용 복잡도 |
|---|---|
| N ≤ 100 | O(N³) |
| N ≤ 1,000 | O(N²) |
| N ≤ 100,000 | O(N log N) |
| N ≤ 1,000,000 | O(N) |
// 방향 벡터 (상하좌우)
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// 범위 체크
boolean inRange(int x, int y, int N, int M) {
return x >= 0 && x < N && y >= 0 && y < M;
}
// 90도 회전 (시계방향)
// (x, y) → (y, N-1-x)
int nx = y;
int ny = N - 1 - x;
sc.next() 다음에 sc.nextLine()을 한 번 불러 버퍼를 비운 뒤 줄 단위 입력을 읽는다.[10]import java.util.Scanner;
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
String word = sc.next();
sc.nextLine(); // 버퍼 비우기
String line = sc.nextLine();
while (sc.hasNextInt()) {
int nextNum = sc.nextInt();
}
sc.close();
import java.io.*;
import java.util.StringTokenizer;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
StringTokenizer st = new StringTokenizer(line, " ");
int num = Integer.parseInt(st.nextToken());
br.close();
import java.io.*;
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write("Hello\n");
bw.flush();
bw.close();
// 또는 StringBuilder로 모아서 한 번에 출력
StringBuilder sb = new StringBuilder();
sb.append("Hello\n");
sb.append("World\n");
System.out.print(sb);
| 용도 | 원문의 선언 | 원문 설명 |
|---|---|---|
| 큐 (FIFO) | Queue<Integer> q = new LinkedList<>(); |
offer, peek, poll |
| 스택 (LIFO) | Deque<Integer> stack = new ArrayDeque<>(); |
ArrayDeque 사용 권장, push, peek, pop |
| 덱 (양방향) | Deque<Integer> dq = new ArrayDeque<>(); |
addFirst, addLast, pollFirst, pollLast |
| 해시 Map / Set | HashMap, HashSet |
O(1), 순서 없음 |
| 트리 Map / Set | TreeMap, TreeSet |
O(log N), 키 기준 정렬과 범위 탐색(floorKey·ceilingKey, floor·ceiling, subMap·subSet) |
Collections.reverseOrder()를 넘기면 최대 힙이 되며, 비교자를 넘기면 배열 같은 객체를 원하는 기준으로 정렬한다.[14]// 최소 힙 (기본)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.poll(); // 가장 작은 값
// 최대 힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 객체 기준 정렬
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // 0번 인덱스 기준
| 알고리즘 | 쓰는 자료구조 |
|---|---|
| BFS | 큐 |
| 반복 DFS | 스택 |
| 위상 정렬 (Kahn) | Queue(LinkedList), 사전순 결과가 필요하면 PriorityQueue |
| Dijkstra | PriorityQueue<int[]>와 Comparator.comparingInt |
stack을 쓰므로, Java에서 위 표의 ArrayDeque 스택을 쓰는 것도 이 Wiki의 대응이다.// 다중 조건 정렬
Arrays.sort(arr2d, (a, b) -> {
if (a[0] != b[0]) return a[0] - b[0]; // 첫 번째 기준
return a[1] - b[1]; // 두 번째 기준
});
int index = Arrays.binarySearch(arr, 3); // 이진탐색 (정렬 필수)
Arrays.binarySearch와 Collections.binarySearch는 정렬된 데이터에서만 쓴다.[16:1]a[0] - b[0]처럼 뺄셈으로 쓴다. 값의 차이가 int 범위를 넘을 만큼 크면 뺄셈이 넘쳐 순서가 뒤집힐 수 있다.[17] Dijkstra 노트는 Comparator.comparingInt(a -> a[0])를 쓴다.[18]PriorityQueue를 쓰고, Floyd-Warshall의 정점 수 상한이 이 페이지의 O(N³) 기준과 비교된다.(x, y) → (y, N-1-x)를 N×M 배열에 쓸 때 무엇을 조심해야 하는가?구현 유형 접근법.md 64-68행 — "코드로 옮기는 것이 핵심 — 과도한 최적화 X", "변수명을 문제 용어와 맞추면 디버깅이 쉬워짐", "기능별 함수 분리 → 검증이 쉬워짐". 66행 원문은 "있는 그대로"를 굵게 표시했다. ↩︎ ↩︎ ↩︎ ↩︎
구현 유형 접근법.md 9-15행 — "문제에서 요구하는 동작을 목록으로 분리", "각 기능에 살 붙이기 (조건, 순서, 예외)", "풀기 전에 O(?) 계산해서 가능한지 확인", "기능 단위로 함수 분리하며 작성", "최솟값, 최댓값, 빈 입력 등 테스트" ↩︎
구현 유형 접근법.md 19-26행 — "시간복잡도 기준 (1억 연산 ≈ 1초)", "| N ≤ 100 | O(N³) |", "| N ≤ 1,000 | O(N²) |", "| N ≤ 100,000 | O(N log N) |", "| N ≤ 1,000,000 | O(N) |" ↩︎
출처 매핑 미확인 — 원문은 "1억 연산 ≈ 1초"를 조건 없이 기준으로 쓴다. 이 값이 언어나 채점 환경에 따라 달라진다는 점은 이 vault의 Raw source로 확인하지 않은 일반적인 주의다. ↩︎
Floyd-Warshall.md 97·99행 — "| 시간 복잡도 | (V^3)$ |", "| 적합 정점 수 | \leq 500$ 수준 |" (셸 치환으로 깨진 표기; 시간 복잡도는 _Algorithm.md 22행 "
구현 유형 접근법.md 30-50행 — "자주 쓰는 패턴", "방향 벡터 (상하좌우)", "int[] dx = {-1, 1, 0, 0};", "return x >= 0 && x < N && y >= 0 && y < M;", "90도 회전 (시계방향)", "// (x, y) → (y, N-1-x)", "int ny = N - 1 - x;". 원문은 각 코드 블록 위에 제목을 두었고, 이 페이지는 그 제목을 코드 첫 줄 주석으로 옮겼다. ↩︎
DFS.md 75-77·163-167행 — "int x[4] = {0, 0, 1, -1};", "int y[4] = {1, -1, 0, 0};", "// 경계 확인 및 조건 확인" ↩︎
구현 유형 접근법.md 54-60행 — "입력 범위 확인 (int 범위 초과 → long)", "좌표계 방향 정의 (행/열 기준 통일)", "경계 조건 처리 (배열 범위 벗어남)", "시뮬레이션 순서가 문제와 동일한지 재확인", "조건문 누락 없는지 확인". 원문은 체크박스 목록이지만 이 페이지에서는 일반 목록으로 바꿨다. ↩︎
Simulation/Java.md 239-243행 — "Integer / Long 상수 & 변환", "// 2,147,483,647", "// 9,223,372,036,854,775,807". 이 값을 체크리스트의 int 범위 항목과 잇는 것은 이 Wiki의 해석이다. ↩︎
Simulation/Java.md 11-25행 — "Scanner — 간단한 입력", "String word = sc.next();", "sc.nextLine(); // 버퍼 비우기" ↩︎
Simulation/Java.md 27-37행 — "BufferedReader — 빠른 입력 (대량 입력 시 필수)", "import java.util.StringTokenizer;", "int num = Integer.parseInt(st.nextToken());" ↩︎
Simulation/Java.md 39-53행 — "BufferedWriter — 빠른 출력 (출력이 많을 때 TLE 방지)", "// 또는 StringBuilder로 모아서 한 번에 출력" ↩︎
Simulation/Java.md 76-140행 — "// HashMap — O(1), 순서 없음", "// TreeMap — O(log N), 키 기준 정렬 + 범위 탐색", "treeMap.floorKey(4); // 4 이하 최댓값 키", "// HashSet — O(1), 순서 없음", "// TreeSet — O(log N), 정렬 + 범위 탐색", "// Queue (FIFO)", "// Stack (LIFO) — ArrayDeque 사용 권장", "// Deque (양방향)" ↩︎ ↩︎
Simulation/Java.md 171-177·288행 — "// 다중 조건 정렬", "if (a[0] != b[0]) return a[0] - b[0]; // 첫 번째 기준", "// 두 번째 기준", "int index = Arrays.binarySearch(arr, 3); // 이진탐색 (정렬 필수)", "Collections.binarySearch(list, 3);" ↩︎ ↩︎
출처 매핑 미확인 — 원문은 뺄셈 비교자를 쓰지만 그 위험을 말하지 않는다. 뺄셈 결과가 int 범위를 넘을 수 있다는 점은 Java int 산술의 일반적인 성질에 근거한 보충이며, 이 vault의 Raw source로 확인하지 않았다. ↩︎
Dijkstra.md 34행 — "PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));" ↩︎