2026.11.09 · 2분 읽기 · 조회 0
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;
}
}BFS 최단거리 = Queue<int[]>에 {x, y, 거리} → 시작점 방문 표시 → 꺼내서 도착이면 return → 4방향 돌며 범위/벽/방문 체크 → 방문 표시하고 거리+1로 넣기 → 끝까지 못 가면 -1
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]);
}
}프로그래머스의 타겟넘버 찾기 문제이다. 템플릿은
dfs(n) {
if (n == 종료조건) {
...
return;
}
dfs(n-1);
}이런 느낌이다. 재귀함수를 이용한다.
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"); // 맨 앞에 끼우기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];
}
}메모이제이션이 필수이다.반복문을 사용하면 더 빠르고 간단하게 풀 수 있다.
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에 저장됩니다.