본문 바로가기

Algorithm221

[프로그래머스] 미로탈출 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이미로를 탈출하는데 레버에 먼저 들리고 출구로 가야한다. 즉, 출발지 -> 레버, 레버 -> 출구 2차례 그래프 탐색으로 최솟값을 구하면 된다. bfs탐색을 통해 두 함수의 최솟값을 구해줬다.  메모리: 77.3MB시간: 0.42ms언어: Java 11import java.util.*;class Solution { static class Point { int r; i.. 2024. 5. 17.
[백준] 6506: 엘 도라도 - JAVA https://www.acmicpc.net/problem/6506 풀이n개의 숫자로 이루어진 배열에서 k개의 숫자로 만들 수 있는 증가하는 부분 수열의 개수를 구해야한다. dp배열을 long[n][k + 1] 로 만들었다. dp[i][j]가 의미하는 것은 arr[i]를 포함하여 인덱스가 i보다 큰 j-1개의 숫자들과 j길이의 증가하는 부분 수열의 개수이다. 즉, dp[i][j]를 구하기 위해서는 다음과 같은 코드를 이용한다.long tmp = 0;for (int x = i + 1; x arr[idx]) { tmp += solve(x, j - 1); }}dp[i][j] = tmp;이렇게 되면 i인덱스와 그 이상의 숫자를 포함한 j길이의 증가하는 부분수열의 개수가 구해진다. 따라서, n개.. 2024. 5. 17.
[백준] 17255: N으로 만들기 - JAVA https://www.acmicpc.net/problem/17255 풀이어떤 수 N을 만들어야 하는데 두 가지 행동을 반복해서 만들어야 한다. 1. 수의 왼쪽에 숫자를 하나 적는다. 2. 수의 오른쪽에 숫자를 하나 적는다. 따라서, 숫자 N을 입력받을때 char 배열로 받아서 인덱스로 탐색하면서 시작위치를 정하고 dfs탐색을 했다. left와 right 인덱스를 기억하면서 left가 0, right가 길이-1이 되면 set자료구조에 넣었다. 나온 수를 순서대로 string으로 만들어 set자료구조에 넣었기 때문에 중복된 것이 제외되고 set의 size를 출력하면 경우의 수가 된다.  메모리: 17296KB시간: 216ms언어: Java 11import java.util.*;import java.io.*;.. 2024. 5. 17.
[백준] 23352: 방탈출 - JAVA https://www.acmicpc.net/problem/23352 풀이상하좌우로 움직일 수 있는데 가장 긴 경로의 시작과 끝의 합을 구해야 한다. N x M 배열을 입력받고, 0이 아니면 bfs탐색을 한다. bfs탐색할 때 경로의 시작값을 함께 파라미터로 넘겨 진행했다. 더이상 갈 곳이 없을 때 지금까지의 최장 길이와 비교하여 답을 갱신해주었다.  메모리: 268784KB시간: 568ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int r; int c; int dist; public Node(int r, int c, int dist) {.. 2024. 5. 17.
[백준] 9370: 미확인 도착지 - JAVA https://www.acmicpc.net/problem/9370 풀이목적지까지 최단경로에 (g-h)나 (h-g) 도로를 거치는지 확인하는 문제이다. 목적지를 t, 출발지를 s라고 한다면 (s-t)의 거리가 (s-g) + (g-h) + (h-t), (s-h) + (h-g) + (g-t) 두 거리 중 작은 값과 같다면 g-h 도로를 지났다고 확인할 수 있다. 따라서 다익스트라 알고리즘을 사용하여 s부터의 거리 배열, g부터의 거리, h부터의 거리 3개의 배엻을 구한다. (s-t) 거리가 다른 두 거리 중 작은 값과 같다면 출력한다.  메모리: 63248KB시간: 676ms언어: Java 11import java.util.*;import java.io.*;public class Main { static.. 2024. 5. 17.
[백준] 1956: 운동 - JAVA https://www.acmicpc.net/problem/1956 풀이v개의 정점과 e개의 간선이 주어진다. 출발점에서 다시 출발점으로 돌아오는 사이클이 있는지, 있다면 최솟값을 구하는 문제이다. 모든 정점에서 다른 모든 정점까지의 최단경로가 필요하다. -> 플로이드 워셜 알고리즘을 사용한다. 원래 알고있던 플로이드 워셜에서는 거리를 저장할 이차원배열을 만들고, 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화를 했었다. 하지만 이 문제에서는 자기 자신에서 자기 자신으로 돌아와야하므로 다른 값들과 마찬가지로 INF로 초기화하였다. 그리고나서 플로이드 워셜 알고리즘을 통해 i정점에서 k를 거쳐 j로 이동하는 최솟값을 갱신해주면 자기 자신으로 다시 돌아오는 거리도 갱신된다. `dist[i][i]` 중 .. 2024. 5. 17.
[백준] 6087: 레이저 통신 - JAVA https://www.acmicpc.net/problem/6087 풀이목적지까지 가야하는데 방향전환을 하려면 거울을 써야한다. 거울을 최소로 쓰면서 목적지에 도달해야 한다. 거울을 쓴 개수가 적은것 부터 탐색하기 위해 우선순위큐를 사용했다. 방문처리를 쓴 거울의 개수로 하는 int 이차원배열로 했었는데 메모리초과가 발생했다. 삼차원배열로 방향까지 체크를 해서 어느 방향일때 최소인지 확인하였더니 해결됐다.  메모리: 15720KB시간: 172ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node implements Comparable { int r; int c; i.. 2024. 5. 17.
[백준] 2631: 줄세우기 - JAVA https://www.acmicpc.net/problem/2631 풀이1번부터 N번까지 오름차순으로 줄을 세워야 하는데 위치를 옮기는 횟수를 최소로 해야한다. 즉, 현재 상태에서 가장 긴 증가하는 부분수열(LIS)를 찾고 거기에 포함되지 않는 것들만 옮기면 최소로 옮기는 것이 된다. LIS는 다이나믹프로그래밍을 이용해 구할 수 있다. 0부터 N까지 탐색하는데, dp[i]의 값을 1로 해준다. 현재 위치(i)보다 이전의 원소(j)들 중에서 현재 원소보다 작은지 체크한다.(`arr[i] > arr[j]`) 현재 원소 보다 작다면 dp[i]의 값과 비교하여 갱신한다.(`dp[i] = Math.max(dp[i], dp[j] + 1)`)  메모리: 14072KB시간: 132ms언어: Java 11import ja.. 2024. 5. 17.
[백준] 2225: 합분해 - JAVA https://www.acmicpc.net/problem/2225 풀이0부터 N까지의 정수 K개를 더해서 합이 N이 되는 경우의 수를 구해야 한다. K개를 더해서 N이 되는 경우는 "K-1개를 더해서 N이 되는 경우에 0을 더한 경우", "K-1개를 더해서 N-1이 되는 경우에 1을 더한 경우", "K-1개를 더해서 N-2이 되는 경우에 2를 더한 경우", ... "K-1개를 더해서 0이 되는 경우에 N을 더한 경우" 들의 합으로 나타낼 수 있다. dp[k][n]에서 정수 1개를 이용해 n을 만드는 경우는 1개, 정수 k개를 이용해 0을 만드는 경우는 1개로 초기화 해주었다. 그 후 위의 경우들을 다 더하면서 저장하여 dp[k][n]을 출력하면 된다. 아래 코드에서 3중 for문에 있던for (int l.. 2024. 5. 17.
[백준] 2602: 돌다리 건너기 - JAVA https://www.acmicpc.net/problem/2602 풀이길이 두개가 있고, 두 길의 발판을 번갈아가며 밟으면서 길을 건너야 한다. 밟아야 할 발판의 종류는 정해져 있다. 완전탐색하면 시간초과가 날 것이고, dp를 사용해야 한다. 건너기 위해 밟아야 할 발판을 route라하고, 길을 a와 b라고 하면, dp배열을 [2][route][a,b]로 만들 수 있다. 지금 밟아야 할 발판과 현재 보고 있는 길의 발판이 같으면 `dp[현재 길][i][j] = dp[현재 길][i][j-1] + dp[다른 길][i-1][j-1]` 이 된다. 발판이 다르면 같은 길에서 바로 전에꺼를 가져오면 된다. 즉, `dp[현재 길][i][j] = dp[현재 길][i][j-1]` 이 된다. 끝까지 진행하여 dp[a]의 .. 2024. 5. 17.

티스토리툴바