chorock.page
소개글시리즈프로젝트실험
© 2026 chorock.page
← 목록으로
Java코딩테스트

[Java] 코딩테스트 벼락치기 3

2026.11.09 · 2분 읽기 · 조회 0

목차
BFSDFSStringBuilderDynamic Programming

BFS

java
import java.util.*;
 
class Solution {
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        q.offer(new int[]{0,0,1});
        visited[0][0] = true;
        
        while (!q.isEmpty()){
            int[] cur = q.poll();
            
            if (cur[0] == n-1 && cur[1] == m-1) {
                return cur[2];
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i], ny = cur[1] + dy[i];
                // 맵을 뚫으면 못 감
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                // 벽이 있으면 못 감
                if (maps[nx][ny] == 0 || visited[nx][ny]) continue;
                visited[nx][ny] = true;
                q.offer(new int[]{nx, ny, cur[2] + 1});  
            }
        }
        return -1;
    }
}
  • 국룰로 많이 쓰이는 공식이니 로직을 외워두자.
  • dx, dy 테크닉, 큐를 이용해서 진입

BFS 최단거리 = Queue<int[]>에 {x, y, 거리} → 시작점 방문 표시 → 꺼내서 도착이면 return → 4방향 돌며 범위/벽/방문 체크 → 방문 표시하고 거리+1로 넣기 → 끝까지 못 가면 -1

DFS

  • 모든 경우의 수를 다 찾아야 할 경우 사용하면 된다
javascript
class Solution {
    public int cnt = 0;
    public int[] numbers;
    public int target;
    
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        dfs(0, 0);
        
        return cnt;
    }
    public void dfs(int idx, int sum) {
        if (idx == numbers.length) {
            if (sum == target) cnt++;
            return;
        }
        dfs(idx + 1, sum + numbers[idx]);
        dfs(idx + 1, sum - numbers[idx]);
    }
}

프로그래머스의 타겟넘버 찾기 문제이다. 템플릿은

java
dfs(n) {
  if (n == 종료조건) {
    ...
    return;
  }
  dfs(n-1);
}

이런 느낌이다. 재귀함수를 이용한다.

StringBuilder

  • 문자열을 계속 이어붙일 때 사용하는 도구다.
java
StringBuilder sb = new StringBuilder(); // 빈 문자열
sb.append("ab");                        // 뒤에 붙이기 -> "ab"
sb.append(3);                           // 숫자,char도 가능 -> "ab3"
String result = sb.toString();          // String으로 바꾸기
 
sb.reverse();                           // 뒤집기
sb.length();                            // 길이
sb.insert(0, "x");                      // 맨 앞에 끼우기

Dynamic Programming

  • 문제를 잘게 쪼개어서 조합해서 푼다는 의미인데, 점화식을 이용한다.
  • 피보나치 수열을 푸는 방법을 떠올리는게 가장 대표적이다.
java
class Solution {
    long memo[];
    public int solution(int n) {
        memo = new long[n+1];
        return (int) dp(n);
    }
    public long dp(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2; 
        if (memo[n] != 0) return memo[n];
        
        memo[n] = (dp(n-1) + dp(n-2)) % 1000000007;
        return memo[n];
    }
}
  • 시간 초과가 나지 않기 위해서는 메모이제이션이 필수이다.

반복문을 사용하면 더 빠르고 간단하게 풀 수 있다.

csharp
class Solution {
    public int solution(int n) {
        long[] dp = new long[n+2];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < dp.length; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        return (int) dp[n];
    }
 
}
초록
초록

앱과 웹을 만들고, 직접 운영하며 기록합니다.

댓글

giscus로 동작하며 GitHub Discussions에 저장됩니다.

관련 글

Java코딩테스트

[Java] 코딩테스트 벼락치기 2

2026.11.07·3분 읽기·조회 0
Java코딩테스트

[JAVA] 코딩테스트 벼락치기 1

2026.11.06·5분 읽기·조회 0

목차

BFSDFSStringBuilderDynamic Programming