3회차 월말평가(알고리즘) 대비 노트 — 9/28(월)

(삭제 예정)

JDK 8 기준 · 클래스명 Solution · 숨은 테스트케이스 부분채점 → 엣지케이스와 시간초과가 점수 차이를 만듭니다.

0. 출제 후보 한눈에 보기

왜 이렇게 봤나

1. 서술형이 BFS·DFS·그래프 표현·위상정렬만 다룸 → 이번 달 핵심은 “그래프 탐색”. 응용 문제도 이 범위(위상정렬 또는 BFS)일 가능성이 가장 큽니다.
2. 라이브 중 1767 → 삼성 A형 기출이고, 커버 가능한 코어 수/전선 길이 비교 등 숨은 케이스로 부분점수를 가르기 좋은 구조. 라이브에서 풀어준 걸 “다시 짤 수 있는지” 보기 딱 좋은 문제입니다.
3. 6808은 너무 쉬워서 변별력이 떨어지지만, 나오면 무조건 만점을 받아야 하는 문제. 5648은 0.5초 충돌 처리라는 함정 하나가 전부라 출제 시 변별력이 큽니다.
4. 과제 중 1868은 BFS 주제와 정확히 맞아떨어집니다. 1486은 부분집합 대표 문제라 짧고 채점하기 좋습니다. 1227은 쉽지만 BFS 기본형이라 후보로 유지.
5. 6782는 알고리즘보다 수학 트릭 문제라 출제 우선순위가 낮습니다. 다만 Math.sqrt 오차라는 숨은 케이스 함정이 있습니다.

우선 공부 순서 추천: 1767 → 1868 → 위상정렬 템플릿 → 5648 → 1486 → 7206 → 3421 → 6808 → 1227 → 6782

1. 서술형 모범 답안 (세부 문항별 부분점수 대비)

1-1. BFS vs DFS — 진행 순서의 차이와 핵심 자료구조

1-2. 그래프 표현 방식에 따른 탐색 시간

• 보충하면 좋은 한 줄: 희소 그래프(E ≪ V²)에서는 리스트가 유리하고, 밀집 그래프(E ≈ V²)에서는 둘이 비슷합니다. 공간은 행렬 O(V²), 리스트 O(V+E)입니다.

1-3. 위상 정렬의 대상 그래프 조건 2가지

1. **방향 그래프(Directed)**여야 함: 간선에 선후 관계(A→B: A가 먼저)가 있어야 순서를 정할 수 있음.
2. 사이클이 없어야 함(Acyclic): 사이클이 있으면 진입차수 0인 정점이 생기지 않아 순서를 정할 수 없음. → 즉 DAG (Directed Acyclic Graph).

• 보충: Kahn 알고리즘에서 결과에 들어간 정점 수가 V보다 작으면 사이클이 존재합니다.

2. 라이브 풀이 문제

2-1. SWEA 1767 프로세서 연결하기 ★★★

문제 요약: N×N(7~12) 칩에 코어(1)가 있다. 코어를 가장자리 전원까지 직선 전선으로 연결하되 전선끼리 교차하거나 코어를 지나면 안 된다. 최대한 많은 코어를 연결하고, 그중 전선 길이 합의 최솟값을 구한다. 가장자리에 붙은 코어는 이미 연결된 것으로 본다.

풀이 순서

1. 입력하면서 가장자리가 아닌 코어만 리스트에 저장(가장자리 코어는 무시해도 됨).
2. dfs(idx, 연결수, 전선길이)로 코어를 하나씩 결정.
3. 각 코어마다 4방향 + “연결 안 함”, 총 5가지 선택.
4. 방향 선택 시 가장자리까지 경로가 모두 0인지 확인 → 가능하면 전선을 2로 칠하고 재귀 → 돌아오면 0으로 지우기(백트래킹).
5. 끝(idx == 코어수)에서 비교:
   • 연결수 > max면 max와 min길이 모두 갱신
   • 연결수 == max면 min길이만 갱신
6. 가지치기: 연결수 + 남은 코어 수 < max면 return (시간초과 방지 핵심).

static void dfs(int idx, int conn, int len) {
    if (conn + (cores.size() - idx) < maxCore) return;          // 6. 가지치기
    if (idx == cores.size()) {                                   // 5. 갱신
        if (conn > maxCore) { maxCore = conn; minLen = len; }
        else if (conn == maxCore) minLen = Math.min(minLen, len);
        return;
    }
    int r = cores.get(idx)[0], c = cores.get(idx)[1];
    for (int d = 0; d < 4; d++) {
        int l = canConnect(r, c, d);          // 불가능하면 -1, 가능하면 길이
        if (l < 0) continue;
        fill(r, c, d, 2);                     // 전선 깔기
        dfs(idx + 1, conn + 1, len + l);
        fill(r, c, d, 0);                     // 되돌리기
    }
    dfs(idx + 1, conn, len);                  // 연결 안 함
}

함정: ① 테스트케이스마다 maxCore=0, minLen=MAX 초기화 ② “연결 안 함” 분기 누락 ③ 전선 길이를 코어 수보다 먼저 비교하는 실수.

2-2. SWEA 5648 원자 소멸 시뮬레이션 ★★☆

문제 요약: 원자 N개(≤1000)가 좌표(-1000~1000), 방향(0상 1하 2좌 3우), 에너지 K를 가진다. 1초에 1칸씩 동시에 이동하다가 같은 위치에서 만나면 모두 소멸하며 에너지를 방출한다. 방출된 에너지 총합을 구한다.

풀이 순서

1. 0.5초에 서로 스쳐 지나가는 충돌이 있으므로 좌표를 2배로 늘린다 → 한 스텝 = 0.5초.
2. 좌표 변환: x' = (x + 1000) * 2, 범위는 0~4000. 방향 벡터는 상(y+1), 하(y-1), 좌(x-1), 우(x+1).
3. 매 스텝:
   1. 살아 있는 원자를 모두 한 칸 이동, 범위를 벗어나면 제거(에너지 없음).
   2. map[x][y]++로 위치별 원자 수를 센다.
   3. map[x][y] >= 2인 원자는 소멸시키고 에너지를 합산한다.
   4. 이번 스텝에 쓴 칸만 map을 0으로 되돌린다(배열 전체를 초기화하면 느림).
4. 살아 있는 원자가 2개 미만이면 종료(최대 4000스텝이면 모두 밖으로 나감).

int[] dx = {0, 0, -1, 1}, dy = {1, -1, 0, 0};
static int[][] map = new int[4001][4001];   // static으로 한 번만 생성
// 스텝마다: 이동 → 카운트 → 충돌 처리 → 카운트 리셋

함정: ① 좌표를 2배로 늘리지 않으면 0.5초 충돌을 놓침 ② 소멸 판정을 이동 도중에 하면 “먼저 도착한 원자만 사라지는” 버그 → 전원 이동 후 일괄 판정 ③ map을 테스트케이스마다 new하면 메모리·시간 낭비.

2-3. SWEA 6808 규영이와 인영이의 카드 게임 ★★☆

문제 요약: 1~18 카드 중 규영이 9장을 정해진 순서로 낸다. 인영은 나머지 9장을 가지며, 인영이 카드를 내는 모든 순서(9! = 362,880)에 대해 각 라운드에서 높은 카드를 낸 사람이 두 카드 합만큼 점수를 얻는다. 규영이 이기는 경우와 지는 경우의 수를 구한다.

풀이 순서

1. boolean used[19]에 규영 카드를 표시하고, 나머지를 인영 배열에 넣는다.
2. 인영 카드로 순열 DFS(visited 배열)를 돌리며 라운드별 점수를 누적한다.
3. 깊이 9에서 규영 점수 > 인영 점수면 win++, 작으면 lose++.
4. 출력: #t win lose

static void perm(int depth, int gy, int iy) {
    if (depth == 9) { if (gy > iy) win++; else if (gy < iy) lose++; return; }
    for (int i = 0; i < 9; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        int a = gyu[depth], b = in[i];
        if (a > b) perm(depth + 1, gy + a + b, iy);
        else       perm(depth + 1, gy, iy + a + b);
        visited[i] = false;
    }
}

팁: 점수를 재귀 인자로 넘기면 끝에서 다시 계산할 필요가 없습니다. 테스트케이스마다 win/lose를 초기화하세요.

3. 과제 문제

3-1. SWEA 1868 파핑파핑 지뢰찾기 ★★★

문제 요약: N×N(≤300) 판에 *(지뢰)와 .(빈칸)이 있다. 빈칸을 클릭하면 주변 8칸의 지뢰 수가 표시되고, 그 수가 0이면 주변 8칸이 연쇄적으로 열린다. 지뢰가 아닌 모든 칸을 여는 최소 클릭 수를 구한다.

풀이 순서

1. 모든 빈칸에 대해 주변 8방향 지뢰 수 cnt[r][c]를 미리 계산한다.
2. 1차 순회: cnt == 0이고 아직 안 열린 칸 → 클릭 +1, BFS로 연쇄 오픈.
   • BFS 안에서 이웃 칸은 모두 열고(visited), 그 이웃도 cnt == 0일 때만 큐에 넣는다.
3. 2차 순회: 아직 안 열린 빈칸(숫자 칸) → 각각 클릭 +1.
4. 두 값을 합하면 정답.

for (r) for (c) if (map[r][c]=='.' && !vis[r][c] && cnt[r][c]==0) { bfs(r, c); click++; }
for (r) for (c) if (map[r][c]=='.' && !vis[r][c]) click++;

// bfs 내부
vis[nr][nc] = true;                       // 이웃은 무조건 열고
if (cnt[nr][nc] == 0) q.offer(new int[]{nr, nc});   // 0인 칸만 확장

핵심 이유: 0인 칸부터 눌러야 한 번에 가장 많이 열립니다. 순서를 바꾸면 최소가 아닙니다. 함정: 8방향(대각선 포함) 사용, 지뢰 칸은 절대 열지 않기.

3-2. SWEA 1227 미로 2 ★★☆

문제 요약: 100×100 미로(0 길, 1 벽, 2 출발, 3 도착)에서 출발점에서 도착점까지 갈 수 있으면 1, 없으면 0. 테스트케이스는 10개이고, 각 케이스 첫 줄은 케이스 번호.

풀이 순서

1. 케이스 번호를 읽고, 100줄을 char[]로 읽으면서 2의 위치를 저장한다.
2. 출발점에서 BFS(또는 DFS), 4방향, 벽(1)과 방문한 칸은 제외.
3. 3을 만나면 즉시 1을 반환하고, 큐가 비면 0.

함정: 입력이 공백 없이 붙어 있으므로 line.charAt(j) - '0'로 읽기. 재귀 DFS는 최악 10,000 깊이까지 가서 스택 오버플로 위험이 있으니 BFS 권장.

3-3. SWEA 6782 현주가 좋아하는 제곱근 놀이 ★☆☆

문제 요약: N(≤10¹²)에서 시작. 연산은 ① N → N+1 ② N이 제곱수면 N → √N. 2로 만드는 최소 연산 횟수.

풀이 순서 (그리디)

1. N == 2면 0.
2. N 이상인 가장 가까운 제곱수 s²를 찾는다.
3. (s² − N)번 +1 하고, 루트 1번 → cnt += (s² − N) + 1, N = s.
4. N == 2가 될 때까지 반복(10¹² → 10⁶ → 10³ → … 몇 번이면 끝남).

long n = Long.parseLong(...), cnt = 0;
while (n != 2) {
    if (n == 1) { cnt++; break; }              // 1은 루트해도 1 → 무한루프 방어
    long s = (long) Math.sqrt(n);
    while (s * s < n) s++;                     // 부동소수 오차 보정
    while ((s - 1) * (s - 1) >= n) s--;
    cnt += (s * s - n) + 1;
    n = s;
}

함정: ① 반드시 long 사용(int면 오버플로) ② Math.sqrt의 double 오차 → 위처럼 ± 보정 ③ 1씩 더하는 시뮬레이션은 시간초과.

3-4. SWEA 3421 수제 버거 장인 ★★☆

문제 요약: 재료 N개(≤20), 궁합이 안 맞는 재료 쌍 M개. 안 맞는 쌍이 함께 들어가지 않는 버거(재료 부분집합)의 수. 재료를 하나도 안 넣은 버거도 포함한다.

풀이 순서

1. conflict[i]에 i와 안 맞는 재료들을 비트로 저장한다(conflict[a] |= 1<<b, 양방향).
2. dfs(idx, mask): 재료를 하나씩 “넣는다 / 안 넣는다”로 분기한다.
3. 넣을 때 (mask & conflict[idx]) == 0일 때만 넣는다 → 불가능한 가지를 미리 잘라냄.
4. idx == N이면 count++.

static void dfs(int idx, int mask) {
    if (idx == N) { count++; return; }
    dfs(idx + 1, mask);                                            // 안 넣음
    if ((mask & conflict[idx]) == 0) dfs(idx + 1, mask | (1 << idx)); // 넣음
}

함정: 재료 번호가 1부터 시작하면 -1 해서 비트로 쓰기. 2²⁰ × M을 전부 검사하는 방식은 느릴 수 있으니 비트마스크 충돌 체크를 쓰세요.

3-5. SWEA 1486 장훈이의 높은 선반 ★★★

문제 요약: 점원 N명(≤20)의 키 Hᵢ, 선반 높이 B. 점원 일부를 쌓아 키의 합 ≥ B가 되게 할 때, (합 − B)의 최솟값.

풀이 순서

1. 부분집합 DFS: dfs(idx, sum).
2. sum >= B가 되는 순간 min = min(min, sum - B) 후 return(더 쌓아도 차이만 커짐 → 가지치기).
3. idx == N이면 return.
4. 포함/미포함 두 갈래로 재귀.

static void dfs(int idx, int sum) {
    if (sum >= B) { ans = Math.min(ans, sum - B); return; }
    if (idx == N) return;
    dfs(idx + 1, sum + h[idx]);
    dfs(idx + 1, sum);
}

함정: sum >= B 체크를 idx == N 체크보다 먼저 해야 마지막 사람까지 넣은 경우를 놓치지 않습니다. ans는 케이스마다 Integer.MAX_VALUE로 초기화.

3-6. SWEA 7206 숫자게임 ★★☆

문제 요약: 숫자 N(≤99999)의 자릿수 사이를 한 군데 이상 끊어 조각을 모두 곱한다. 결과가 한 자리 수가 될 때까지 반복할 때, 가능한 최대 턴 수를 구한다.

풀이 순서

1. solve(n): n < 10이면 0.
2. 자릿수 L이면 끊을 수 있는 틈은 L−1개 → 비트마스크 1 ~ 2^(L−1)−1로 모든 분할을 표현한다(0은 안 끊음이라 제외).
3. 각 분할마다 조각 곱 p를 계산하고 best = max(best, 1 + solve(p)).
4. 메모이제이션: dp[n](크기 100000, -1로 초기화)로 중복 계산을 막는다. 곱은 항상 n보다 작아서 배열 범위 안에 들어옵니다.

static int solve(int n) {
    if (n < 10) return 0;
    if (dp[n] != -1) return dp[n];
    String s = String.valueOf(n); int L = s.length(), best = 0;
    for (int mask = 1; mask < (1 << (L - 1)); mask++) {
        int prod = 1, cur = s.charAt(0) - '0';
        for (int i = 1; i < L; i++) {
            if ((mask & (1 << (i - 1))) != 0) { prod *= cur; cur = 0; }
            cur = cur * 10 + (s.charAt(i) - '0');
        }
        prod *= cur;
        best = Math.max(best, 1 + solve(prod));
    }
    return dp[n] = best;
}

함정: “0”이 섞인 조각(예: 1|05 → 1×5)도 정상 처리됩니다. dp는 테스트케이스 간에 공유해도 됩니다(값이 n에만 의존) → 한 번만 초기화하면 더 빠릅니다.

4. 응용 문제 대비 — 그래프 템플릿 (서술형 범위 = 응용 범위로 추정)

4-1. 위상 정렬 (Kahn, 인접 리스트)

관련 SWEA 연습: 1267 작업순서

1. 인접 리스트와 indegree[]를 만든다.
2. 진입차수 0인 정점을 모두 큐에 넣는다.
3. 큐에서 꺼내 결과에 추가하고, 이웃의 진입차수를 1씩 줄인다 → 0이 되면 큐에 넣는다.
4. 결과 크기 < V면 사이클 존재.

List<Integer>[] adj = new ArrayList[V + 1];              // JDK8: 제네릭 배열은 raw로 생성
for (int i = 1; i <= V; i++) adj[i] = new ArrayList<>();
// 간선 a→b: adj[a].add(b); indeg[b]++;
Queue<Integer> q = new ArrayDeque<>();
for (int i = 1; i <= V; i++) if (indeg[i] == 0) q.offer(i);
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
    int cur = q.poll(); sb.append(cur).append(' ');
    for (int nx : adj[cur]) if (--indeg[nx] == 0) q.offer(nx);
}

4-2. 인접 리스트 BFS 최단거리 / 레벨 탐색

관련 SWEA 연습: 1238 Contact(가장 마지막 레벨의 최댓값), 5643 키 순서(정방향과 역방향 BFS)

• dist[]를 -1로 초기화하고, 시작점을 0으로 둔 뒤 BFS로 dist[nx] = dist[cur] + 1.

4-3. 연결 요소 개수

관련 SWEA 연습: 7465 창용 마을 무리의 개수

• 모든 정점을 돌며 방문하지 않은 정점에서 BFS/DFS를 시작할 때마다 count++(Union-Find로 풀어도 됨).

5. JDK 8 시험장 체크리스트

1. public class Solution + main, 패키지 선언 금지.
2. var, List.of, String.repeat, Map.of 사용 금지(JDK 9 이상 문법).
3. 입력은 BufferedReader + StringTokenizer, 출력은 StringBuilder로 모아서 한 번에.
4. 테스트케이스마다 전역 변수 초기화(ans, count, visited, 리스트).
5. 10¹²처럼 큰 값은 long, 곱셈 오버플로 확인.
6. 재귀 깊이가 수천 이상이면 BFS로 바꾸기.
7. 출력 형식 #번호 답 정확히(공백 1칸).

참고 출처

• SWEA 5648 원자 소멸 시뮬레이션 정리 (GitHub Issue)
• SWEA 6782 제곱근 놀이 풀이 (velog)
• SWEA 7206 숫자게임 풀이 (Carpe Diem)
• SWEA 3421 수제 버거 장인 (스터디 이슈)
• SW Expert Academy 문제 목록