Problem Solving
[코딩테스트] 2026년 빈출 유형
개발자 쿠키
2025. 10. 5. 16:09
시간 복잡도
1초에 약 1억(10⁸)번 연산 가능하다고 가정
- 입력값 ≤ 500 이하: O(n³) -> 완전탐색, 백트래킹, DFS/BFS (그래프: V+E, 격자 N*M: 백트래킹: 선택지^깊이 순열: N!)
- 입력값 ≤ 2,000 이하: O(n²) -> DP, 그래프 Floyd-Warshall
- 입력값 ≤ 100,000 이하: O(n log n)이하 -> 정렬, 우선순위큐, 투포인터, 다익스트라
- 입력값 ≤ 1,000,000 -> 슬라이딩 윈도우, 해시, 스택
- 입력값 ≤ 10,000,000 이상: O(n)
코딩테스트 빈출 유형
1. 구현 (시뮬레이션, 문자열)
2. 완전탐색
2.1 순열 조합 부분집합 (백트래킹, 비트마스크)
2.2 그래프 탐색 (BFS, DFS) - 격자탐색 / 인접리스트
3. 자료구조 (배열, 동적배열, 스택, 큐, 덱, 힙, 해시) -> 스택, 큐, 덱 -> ArrayDeque 사용
4. DP
5. 슬라이딩 윈도우 / 누적합 (미리 계산해두고 사용) -> left=0; right=0;
6. 투 포인터 -> left=0, right=끝 조건 left<right
7. 이분 탐색 -> left=0 right=끝 조건: left<=right
8. 그래프 알고리즘 - 최단경로: 다익스트라, 벨만포드, 플로이드 워셜 | MST : 크루스칼, 프림 | Union-Find, 위상정렬
9. 그리디 알고리즘
1. 구현 (시뮬레이션, 문자열)
- 격자 이동 시뮬레이션 -> (로봇청소기, 뱀, 구슬 탈출)
- 상태 변화 시뮬레이션 -> (토마토, 불!)
- 완전탐색 + 시뮬레이션 -> (감시, 치킨배달, 12100)
- 회전 -> (스티커 붙이기, 테트로미노)
- 큐/덱 시뮬레이션 -> (프린터 큐, 회전하는 큐)
2. DFS / BFS / 백트래킹
DFS (Depth First Search)
// 순열: 서로 다른 n개 중에 순서를 고려하여 r개 뽑기 -> nPr
static void dfs(int depth) {
if (depth == n) {
return;
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
vis[i] = true;
arr[depth] = pick[i];
dfs(depth + 1);
vis[i] = false;
}
}
}
// 조합: 서로 다른 n개 중에 순서를 고려하지 않고 r개 뽑기 -> nCr
static void dfs(int start, int depth) {
if (depth == r) {
return;
}
for (int i = start; i < n; i++) {
arr[depth] = pick[i];
dfs(i+1, depth+1); // 중복 미허용 조합 -> 둘중하나 선택해서 사용
dfs(i, depth+1); // 중복 허용 조합
}
}
// 부분집합
static void dfs(int depth) {
if (depth == n) {
return;
}
vis[depth] = true;
dfs(depth + 1); // 선택
vis[depth] = false;
dfs(depth + 1); // 비선택
}
// 그래프 DFS
static List<Integer>[] graph;
static void dfs(int node, int depth) {
vis[node] = true;
for(int next : graph[node]) {
if(!vis[next]) {
dfs(next, depth + 1);
}
}
}
BFS (Breadth First Search)
// 격자탐색 BFS
static int n, m;
static int[][] board;
static boolean[][] vis;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static void bfs(int x, int y) {
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{x, y});
vis[x][y] = true;
while (!dq.isEmpty()) {
int[] cur = dq.poll();
System.out.println(cur[0] + " " + cur[1]);
for (int dir = 0; dir < 4; dir++) {
int nx = cur[0] + dx[dir];
int ny = cur[1] + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (!vis[nx][ny] && graph[nx][ny] == 1) {
vis[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
// 그래프 BFS (인접리스트), 최단거리
static List<Integer>[] graph = new List[n+1];
static boolean[] vis;
static int[] dist;
static void bfs(int start, int n) {
Deque<Integer> q = new ArrayDeque<>();
vis = new boolean[n+1];
dist = new int[n+1];
q.offer(start);
vis[start] = true;
while(!dq.isEmpty()) {
int cur = q.poll();
for(int next : graph[cur]) {
if(!vis[next]) {
vis[next] = true;
dist[next] = dist[cur] + 1;
q.offer(next);
}
}
}
}- 인접해 있는 섬 구하기 / (상하좌우 탐색)
- 미로 탐색 (최단 거리 찾기)
- 토마토 익히기 / 불 번지기 (확산 시간)
- 단어 변환 / 그래프 최단 경로 (최소 단계 수 찾기)
3. 자료구조 (배열, 스택, 큐, 힙, 해시)
배열: int[] arr = new int[5];
리스트: ArrayList<Integer> list = new ArrayList<>();
스택: Stack<Integer> stack = new Stack<>(); // 덱권장
큐: Deque<Integer> q = new ArrayDeque<>():
덱: Deque<Integer> dq = new ArrayDeque<>():
최소 힙: PriorityQueue<Integer> pq = new PriorityQueue<>();
최대 힙: PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
해시: Map<String, Integer> map = new HashMap<>();
집합: Set<Integer> set = new HashSet<>();
그래프 인접 리스트: List<Integer>[] graph = new ArrayList[N + 1];4. DP
1. bottom-up 방식 -> 미리 dp배열에 저장
2. 점화식에서 재귀(dfs), 메모이제이션을 사용하는 top-down 방식- 계단 오르기: dp[i] = max(dp[i-2], dp[i-3]+a[i-1]) + a[i]
- 연속합: 최대 부분합 (dp[i] = max(a[i], dp[i-1]+a[i]))
- 배낭 문제: dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i]]+v[i])
5. 슬라이딩 윈도우
- 고정 구간 합 or 문자 빈도 관리
- 투포인터와 함께 자주 사용
6. 투 포인터 (Two Pointers)
int left = 0, right = n;
while(left <= right) {
if(조건) {
left++;
} else {
right--;
}
}- 두 용액
- 부분합
- 연속된 문자열 최소 길이
7. 이분탐색
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
// 조건 만족 → 답 후보 저장하고 더 작은/큰 쪽 탐색
left = mid + 1;
} else {
right = mid - 1;
}
}1. 값 찾기
2. lower bound / upper bound
3. 파라메트릭 서치 -> (나무자르기, 공유기 설치)
8. 최단 경로 알고리즘
// 인접리스트 (가중치 X)
List<Integer>[] list = new ArrayList[n+1];
for(int i=1; i<=n; i++) list[i] = new ArrayList<>();
list[a].add(b);
list[b].add(a); // 양방향이면 양쪽, 단방향이면 한 줄만
// 인접리스트 (가중치 O) — 다익스트라, MST
List<int[]>[] list = new ArrayList[n+1];
list[a].add(new int[]{b, w}); // {도착노드, 가중치}1. 다익스트라 (Dijkstra) : 한 시작점에서 다른 모든 정점까지의 최단거리 (BFS+우선순위 큐)
2. 벨만-포드 (Bellman-Ford) - 가중치가 음수 일 때
3. 플로이드–워셜 (Floyd–Warshall)
8.1 그래프 알고리즘
1. 사이클 판별: DFS, Union-Find
2. 위상 정렬: 선수과목, 작업 스케줄링
3. MST (최소 신장 트리): Kruskal, Prim
어떤 그래프의 부분 그래프로, 그래프의 모든 노드와 간선 일부를 포함하며 모든 노드 간에 경로가 존재하는 것
8.2 크루스칼 (Kruskal)
1. 간선이 하나도 없는 그래프에서 시작 (노드만 존재)
2. 작은 가중치를 가지는 간선부터 차례대로 간선을 추가
8.3 프림 알고리즘
노드를 하나씩 선택해나가며 최소 신장 트리를 만듬
가중치가 최소인 간선으로 연결되는 노드를 구함
자주 나오는 함수
1. 배열 정렬
// 2차원 배열, a[0] 기준 오름차순
Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
// String 배열 오름차순 (기본 정렬, 사전순)
Arrays.sort(arr);
// String 배열 내림차순
Arrays.sort(arr, (a, b) -> b.compareTo(a));
// 길이 짧은 순, 길이 같으면 사전순
Arrays.sort(strs, (a, b) -> {
if (a.length() != b.length()) return a.length() - b.length(); // 길이 우선 비교
return a.compareTo(b); // 길이 같으면 사전순
});
// 두 문자열 배열, 첫번째 원소 같으면 두번째 원소 오름차순
Arrays.sort(tickets, (a, b) -> {
if (a[0].equals(b[0])) {
return a[1].compareTo(b[1]); // 1순위 동률이면 2순위 비교
}
return a[0].compareTo(b[0]); // 1순위 비교
});1. List 정렬
List<int[]> list = new ArrayList<>();
list.sort((a, b) -> b[1] - a[1]); // 1번째 인덱스 기준 내림차순
List<Integer> intList = new ArrayList<>();
Collections.sort(intList); // 오름차순
intList.sort(Collections.reverseOrder()); // 내림차순
2. HashMap, HashSet
// HashMap: 빈도수 세기 패턴
Map<String, Integer> map = new HashMap<>();
map.put(key, map.getOrDefault(key, 0) + 1); // key 없으면 0으로 취급 후 +1
map.containsKey(key); // key 존재 여부
// HashSet: 중복 제거, 존재 여부 확인
Set<String> set = new HashSet<>();
set.add(key);
set.contains(key);3. PriorityQueue
// 2차원 PQ, 첫번째 원소 오름차순 (다익스트라: {거리, 노드})
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
// 첫번째 원소 내림차순
PriorityQueue<int[]> pq2 = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// 다중 기준: 1순위 오름차순, 같으면 2순위 내림차순
PriorityQueue<int[]> pq3 = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) return a[0] - b[0]; // 1순위 비교
return b[1] - a[1]; // 1순위 동률이면 2순위 비교
});4. 형변환
// 문자열 ↔ 숫자
int n = Integer.parseInt("123");
String s = String.valueOf(123);
// 문자 ↔ 숫자
int d = '7' - '0'; // 7, 아스키코드 차이 이용
char c = (char)('a' + 2); // 'c', 아스키코드 더한 뒤 char로 캐스팅5. 배열 초기화 및 부분 추출
// 1차원 배열 초기화
int[] arr = new int[n];
Arrays.fill(arr, -1); // 전체를 -1로 채움
// 2차원 배열 초기화
int[][] arr2 = new int[n][m];
for (int[] row : arr2) Arrays.fill(row, -1); // 행마다 개별로 채워야 함
// 부분 추출
Arrays.copyOfRange(arr, 0, 2); // 배열(int[], String[] 등) 부분 복사, [0,2)
str.substring(0, 2); // 문자열 부분 추출, [0,2)
// 1차원 배열 디버깅
Arrays.toString(arr)
// 2차원 배열 디버깅
Arrays.deepToString(arr);6. StringBuilder
StringBuilder sb = new StringBuilder();
sb.replace(int start, int end, word);
sb.charAt(1); // 1번째 인덱스
sb.reverse().toString(); // 뒤집기
sb.deleteCharAt(sb.length()-1); // 마지막 문자 삭제
sb.deleteCharAt(3); // 3번째 인덱스 문자 삭제
sb.setLength(6); // 앞에 6개 남기고 모두 삭제
sb.insert(1, 2); // 1번째 인덱스에 값 삽입7. ArrayDeque
Deque<Integer> dq = new ArrayDeque<>();
// 큐(FIFO)로 쓸 때: BFS 표준 패턴
dq.offer(1); // = offerLast, 뒤에 추가
dq.poll(); // = pollFirst, 앞에서 꺼냄
dq.peek(); // = peekFirst, 앞을 꺼내지 않고 확인
// 스택(LIFO)으로 쓸 때: DFS 반복문 구현
dq.push(1); // = addFirst, 앞에 추가 (push는 앞으로 들어감에 주의)
dq.pop(); // = removeFirst, 앞에서 꺼냄
dq.peek(); // 스택 top 확인
// 양쪽 모두 명시적으로 제어 (덱 문제, 회전 문제)
dq.addFirst(1); // 앞에 추가, 공간 부족 시 예외
dq.addLast(2); // 뒤에 추가
dq.offerFirst(1); // 앞에 추가, 실패 시 false 반환 (예외 대신)
dq.offerLast(2); // 뒤에 추가
dq.pollFirst(); // 앞에서 제거, 비어있으면 null 반환 (안전)
dq.pollLast(); // 뒤에서 제거, 비어있으면 null
dq.removeFirst(); // 앞에서 제거, 비어있으면 NoSuchElementException (위험)
dq.peekFirst(); // 앞 확인, 비어있으면 null
dq.peekLast(); // 뒤 확인, 비어있으면 null
// 공통
dq.size(); // 크기
dq.isEmpty(); // while (!dq.isEmpty()) 형태로 BFS 종료 조건에 사용
dq.clear(); // 전체 비우기
dq.contains(3); // 포함 여부, O(n)이라 반복문 안에서 쓰면 시간초과 위험
// addAll: 컬렉션 통째로 뒤에 붙이기
List<Integer> list = List.of(1, 2, 3);
dq.addAll(list); // 뒤쪽에 1,2,3 순서 그대로 추가
dq.addAll(Arrays.asList(4, 5)); // 가변인자를 List로 감싸서 바로 추가
Integer[] boxed = {6, 7};
dq.addAll(Arrays.asList(boxed)); // Integer[]는 asList로 바로 변환 가능
int[] arr = {8, 9};
dq.addAll(Arrays.stream(arr).boxed().toList()); // int[]는 asList가 안 먹혀서 boxed()로 래핑 필요
// 회전 패턴: 앞에서 빼서 뒤로 (조세푸스, 프린터 큐 등)
dq.addLast(dq.pollFirst()); // 앞 원소를 뒤로 이동
// 순회: 앞에서 뒤 방향, poll 없이 내용만 볼 때
for (int x : dq) System.out.println(x);
Iterator<Integer> it = dq.descendingIterator(); // 뒤에서 앞 방향 순회
// 배열로 변환
Integer[] out = dq.toArray(new Integer[0]); // 제네릭이라 int[]가 아닌 Integer[]로만 가능
8. String 처리
String s = "a,b,c";
s.split(","); // 배열로 분리, 정규식이라 "\\." 처럼 이스케이프 필요한 문자 주의
s.split(""); // 한 글자씩 String[]로 분리
s.toCharArray(); // char[]로 변환, 인덱스 접근이 잦으면 이게 빠름
s.charAt(0); // 특정 위치 문자
s.length(); // 길이, 배열은 length (괄호 없음)이라 헷갈리지 않게 주의
s.contains("b"); // 포함 여부
s.indexOf("b"); // 위치, 없으면 -1
s.replace("a", "z"); // 치환, 원본은 안 바뀌므로 반환값을 받아야 함
s.equals("abc"); // 문자열 비교는 == 가 아니라 반드시 equals
s.compareTo("abd"); // 사전순 비교, 음수면 s가 앞
s.repeat(3); // 반복
String.join("-", list); // 리스트를 구분자로 이어붙이기
// 문자 판별
Character.isDigit(c); // 숫자 여부
Character.isAlphabetic(c); // 알파벳 여부
Character.isUpperCase(c); // 대문자 여부
Character.toUpperCase(c); // 대문자 변환9. Map, Set 순회와 정렬
// Map 순회: entrySet이 key, value 동시 접근이라 가장 효율적
for (Map.Entry<String, Integer> e : map.entrySet()) {
String k = e.getKey();
int v = e.getValue();
}
for (String k : map.keySet()) { // key만 필요할 때
map.get(key); // value
}
// Map을 value 기준 내림차순 정렬 (빈도수 1등 찾기)
List<Map.Entry<String, Integer>> entries = new ArrayList<>(map.entrySet());
entries.sort((a, b) -> b.getValue() - a.getValue()); // value 내림차순
// 정렬 순서가 필요하면 TreeMap
TreeMap<String, Integer> tm = new TreeMap<>();
tm.firstKey(); // 최소 key
tm.lastKey(); // 최대 key
// Set 중복 제거 후 정렬된 배열로
int[] result = set.stream().mapToInt(Integer::intValue).sorted().toArray();10. 진법과 수학
Integer.parseInt("1010", 2); // 2진 문자열을 10진수로
Integer.toBinaryString(10); // 10진수를 2진 문자열로
Integer.toString(10, 3); // 10진수를 3진 문자열로 (n진법 일반형)
Math.pow(2, 10); // 반환형이 double이라 (int) 캐스팅 필요
Math.sqrt(16);
(int) Math.ceil(7 / 2.0); // 올림, 정수끼리 나누면 소수가 사라지니 2.0으로 실수 나눗셈
// 최대공약수, 최소공배수
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b); // 유클리드 호제법, b가 0이면 a가 답
}
int lcm = a / gcd(a, b) * b; // 곱을 먼저 하면 오버플로라서 나눗셈 먼저
SWEA 기준 코테 기본 구조
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = sb = new StringBuilder();
StringTokenizer st;
int t = Integer.parseInt(br.readLine());
for(int tc=1; tc<=t; tc++) {
n = Integer.parseInt(br.readLine());
arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
sb.append("#").append(tc).append(" ").sb.append(1).append("\n");
}
System.out.println(sb.toString());
}