[코딩테스트] 2025년 빈출 유형

시간 복잡도

1초에 약 1억(10⁸)번 연산 가능하다고 가정

• 입력값 ≤ 500 이하: O(n³) -> 완전탐색, DFS/BFS, 백트래킹
• 입력값 ≤ 2,000 이하: O(n²) -> DP, 그래프 Floyd-Warshall
• 입력값 ≤ 100,000 이하: O(n log n)이하 -> 정렬, 우선순위큐, 투포인터, 다익스트라
• 입력값 ≤ 1,000,000 -> 슬라이딩 윈도우, 해시, 스택
• 입력값  ≤  10,000,000 이상: O(n)

코딩테스트 빈출 유형

1. 구현 (시뮬레이션, 문자열)
2. 완전탐색 (BFS, DFS, 백트래킹)
3. 자료구조 (배열, 스택, 큐, 힙, 해시)
4. DP
5. 슬라이딩 윈도우 / 누적합 : 미리 계산해두고 사용하기
6. 투 포인터
7. 이분 탐색
8. 최단 경로 알고리즘 (Dijkstra, Bellman-Ford, Floyd-Warshall)
9. 그래프 (위상정렬, MST)

Java 문법
알고리즘 유형별 정리

1. 구현 (시뮬레이션, 문자열)

Simulation

1. 격자 이동 시뮬레이션 -> (로봇청소기, 뱀, 구슬 탈출)
2. 상태 변화 시뮬레이션 -> (토마토, 불!)
3. 완전탐색 + 시뮬레이션 -> (감시, 치킨배달, 12100)
4. 회전 -> (스티커 붙이기, 테트로미노)
5. 큐/덱 시뮬레이션 ->  (프린터 큐, 회전하는 큐)

2. DFS / BFS / 백트래킹

DFS (Depth First Search)

// 순열
static void dfs(int depth) {
    if (depth == n) {
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            arr[depth] = nums[i];
            dfs(depth + 1);
            vis[i] = false;
        }
    }
}

// 조합
static void dfs(int start, int depth) {
    if (depth == r) {
        return;
    }
    for (int i = start; i < n; i++) {
        arr[depth] = nums[i];
        dfs(i + 1, depth + 1);
        dfs(i, depth+1); // 중복 허용 조합이면 
    }
}

// 부분집합
static void dfs(int depth) {
    if (depth == n) {
        return;
    }
    pick[depth] = true;
    dfs(depth + 1); // 선택
    pick[depth] = false;
    dfs(depth + 1); // 비선택
}

// 그래프 DFS
static void dfs(int node) {
    vis[node] = true;        // 1. 방문
    order[node] = cnt++;     // 2. 정보 기록
    
    for(int next : list[node]) {   // 3. 이웃 순회
        if(!vis[next]) {
            dfs(next);              // 4. 재귀
        }
    }
}

 

BFS (Breadth First Search)

static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};

static void bfs(int x, int y) {
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{x, y});
    vis[x][y] = true;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        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] == 0) continue;
            vis[nx][ny] = true;
            q.add(new int[]{nx, ny});
        }
    }
}

1. 인접해 있는 섬 구하기 / (상하좌우 탐색)
2. 미로 탐색 (최단 거리 찾기)
3. 토마토 익히기 / 불 번지기 (확산 시간)
4. 단어 변환 / 그래프 최단 경로 (최소 단계 수 찾기)

 

3. 자료구조 (배열, 스택, 큐, 힙, 해시)

배열: int[] arr = new int[5];
리스트: ArrayList<Integer> list = new ArrayList<>();
스택: Stack<Integer> st = new Stack<>();
큐: Queue<Integer> q = new LinkedList<>();
덱: Deque<Integer> dq = new LinkedList<>(); 
최소 힙: PriorityQueue<Integer> pq = new PriorityQueue<>();
최대 힙: PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
해시: Map<String, Intger> map = new HashMap<>();

 

4. DP

1. bottom-up 방식 -> 미리 dp배열에 저장
2. 점화식에서 재귀(dfs), 메모이제이션을 사용하는 top-down 방식

1. 계단 오르기: dp[i] = max(dp[i-2], dp[i-3]+a[i-1]) + a[i]
2. 연속합: 최대 부분합 (dp[i] = max(a[i], dp[i-1]+a[i]))
3. 배낭 문제: dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i]]+v[i])

 

5. 슬라이딩 윈도우

1. 고정 구간 합 or 문자 빈도 관리
2. 투포인터와 함께 자주 사용

 

6. 투 포인터 (Two Pointers)

int left = 0, right = 0;
while(right < n) {
    // 조건 만족 검사
    if(조건) left++;
    else right++;
}

1. 두 용액
2. 부분합
3. 연속된 문자열 최소 길이

 

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. 최단 경로 알고리즘

1. 다익스트라 (Dijkstra) : 한 시작점에서 다른 모든 정점까지의 최단거리
2. 벨만-포드 (Bellman-Ford)
3. 플로이드–워셜 (Floyd–Warshall)
 

9. 그래프

1. 사이클 판별: DFS, Union-Find
2. 위상 정렬: 선수과목, 작업 스케줄링
3. MST (최소 신장 트리): Kruskal, Prim

 

자주 나오는 함수

# 정렬

// 2차원 배열
Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0])); // a[0] 기준 오름차순

List<int[]> list = new ArrayList<>();
list.sort((a, b) -> b[1] - a[1]); // 1번째 기준 내림차순

// List 정렬
List<Integer> list = new ArrayList<>();
Collections.sort(list);                    // 오름차순
list.sort(Collections.reverseOrder());     // 내림차순

// String 정렬
Arrays.sort(arr) // 오름차순
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]);
     }
     return a[0].compareTo(b[0]);
});

# HashSet, HashMap

// HashMap 
Map<String, Integer> map = new HashMap<>();
map.put(key, map.getOrDefault(key, 0) + 1);
map.containsKey(key);

// Set
Set<String> set = new HashSet<>();
set.add(key);
set.contains(key);

// 순회
for (Map.Entry<String, Integer> e : map.entrySet()) {
    e.getKey(); e.getValue();
}

// 값 기준 정렬 (HashMap → List 변환 필수)
List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
list.sort((a, b) -> b.getValue() - a.getValue());

# 우선순위큐

// PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<>();                    // 최소힙
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Comparator.reverseOrder()); // 최대힙

// 2차원 PQ (가중치 기준)
PriorityQueue<int[]> pq3 = new PriorityQueue<>((a, b) -> a[1] - b[1]);

// 문자열 ↔ 숫자
int n = Integer.parseInt("123");
String s = String.valueOf(123);

// 문자 ↔ 숫자
int d = '7' - '0';        // 7
char c = (char)('a' + 2); // 'c'

// 배열 초기화
int[] arr = new int[n];
Arrays.fill(arr, -1);
int[][] arr2 = new int[n][m];
for (int[] row : arr2) Arrays.fill(row, -1);

// 쪼개기
str.substring(0, 2);              // String (문자열)
Arrays.copyOfRange(arr, 0, 2);    // 배열 (int[], String[] 등)

// 문자열 뒤집기
String reversed = new StringBuilder("abc").reverse().toString();

// StringBuilder
sb.deleteCharAt(sb.length()-1); // 마지막 문자 자르기

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

static long lcm(int a, int b) {
	return (long) a * b / gcd(a, b);
}

 

 

 

 

 

 

 

 

다시 풀어야 할 것 

1. 백준 대기업 문제와 비슷한 기출 문제
2. 상어 시리즈
3. 삼성 A형 기출문제

16236 → 21610 → 20056 → 20057 → 20058 → 21611 → 19236 → 19237 → 23290 → 23291
1️⃣ 21610 마법사 상어와 비바라기
2️⃣ 20056 마법사 상어와 파이어볼
3️⃣ 20057 마법사 상어와 토네이도
4️⃣ 20058 마법사 상어와 파이어스톰
5️⃣ 16236 아기 상어
6️⃣ 19237 어른 상어
7️⃣ 21611 마법사 상어와 블리자드
8️⃣ 19236 청소년 상어
9️⃣ 23290 마법사 상어와 복제
🔟 23291 어항 정리