본문 바로가기

전체 글156

[백준] 1504번: 특정한 최단 경로 (Java) 1. 문제설명방향성 없는 그래프에서 1번 정점에서부터 N번 정점으로 최단 거리로 이동하려 한다. 한 번 이동했던 정점 또는 간선을 다시 이동할 수 있다. 주어진 두 정점을 반드시 거치면서 최단 경로를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식`Node` 객체를 사용하여 정점과 거리 정보를 저장한다.인접리스트 형식(`List[] list`)으로 간선 정보를 저장한다. (양방향으로)다익스트라 알고리즘을 사용한다.우선순위 큐를 사용하여 가장 짧은 경로를 먼저 처리하고, 현재 경로에서 더 짧은 경로를 찾으면 경로 정보를 갱신하는 방식으로 구현한다.두 가지 경로를 구한다.1 → v1 → v2 → N1 → v2 → v1 → N총 3번의 다익스트라 메서드 호출을 통해 두 가지 경로의 최.. 2024. 9. 10.
[백준] 1238번: 파티 (Java) 1. 문제설명N개의 마을에 각각 한 명의 학생이 있다. 이 마을 사이에는 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T(i)의 시간을 소비한다. 각각의 학생들을 최단 시간에 파티(X)에 오고 가기를 원한다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생을 구하는 문제이다.모든 학생은 집에서 X에 갈 수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식인접리스트 형식으로 그래프 정보를 입력받는다.정방향 그래프: X 마을에서 각 마을로 가는 경로를 구할 때 사용역방향 그래프: 각 마을에서 X 마을로 가는 경로를 구할 때 사용다익스트라 알고리즘을 두 번 실행한다.첫 번째: 정방향 그래프를 사용하여 X에서 각 마을로 .. 2024. 9. 10.
[백준] 17396번: 백도어 (Java) 1. 문제설명0번째에서 N-1번째 분기점까지 가는 최단 거리를 구하는 문제이다. 이때 적의 시야에 걸리는 곳은 지나칠 수 없다. 시야 정보가 0이면 상대 시야에 보이지 않고, 1이면 상대 시야에 보인다. 시야에 걸리지 않으면서 N-1번째 분기점에 도달하는 최단 거리를 구한다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식`Node` 객체를 사용하여 각 노드(`end`)에 그 노드의 비용(`time`)을 저장하고, 우선순위 큐에서 경로 비용이 짧은 순서대로 처리된다.각 분기점 사이의 정보를 `List[] list` 에 저장한다. (인접리스트 방식, 양방향으로 저장)다익스트라 알고리즘을 사용하여 최단 거리를 구한다.우선순위 큐를 사용하여 가장 짧은 경로를 먼저 처리하고, 현재 경로에서 더 짧은 경로.. 2024. 9. 10.
[백준] 11726번: 2xn 타일링 (Java) 1. 문제설명2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식`dp[i]`는 `i` 길이의 직사각형을 채우는 방법의 수를 저장한다.`dp[1]`과 `dp[2]`의 초기값을 설정한다.위 그림을 참고하면 `dp[i] = dp[i-1] + dp[i-2]` 점화식을 구할 수 있다.`dp[i]`를 저장할 때 오버플로우 방지를 위해 문제에서 주어지는 10,007로 나눈 값을 저장한다.최종적으로 `dp[n]`을 구한다. 3. 최종 코드import java.io.*;public class Main { public static void main(String[] args) throws IOExcep.. 2024. 8. 29.
[백준] 가장 긴 짝수 연속한 부분 수열 (small) (Java) 1. 문제설명길이가 N인 수열 S가 있고, S는 1 이상인 정수로 이루어져 있다. 수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제할 수 있다. 삭제를 수행 후 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구하는 문제이다.시간 제한: 1초메모리 제한: 1024MB 2. 접근 방식`dp[i][j]`: 수열의 `i` 번째까지의 원소에서 `j` 개의 홀수를 제거했을 때의 가장 긴 짝수 부분 수열의 길이만약 `s[i]`가 짝수일 경우 이전 상태에서 `j` 개의 홀수를 제거한 것과 동일한 상태에서 현재 짝수를 추가하여 길이를 1 증가시킨다⇒ `dp[i][j] = dp[i-1][j] + 1`만약 `s[i]`가 홀수이고,현재 홀수를 제거 가능할 경우 (j > 0) 이전 상태에서 `j-.. 2024. 8. 28.
[백준] 1463번: 1로 만들기 (Java) 1. 문제설명정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위의 연산 세 개를 적절히 사용해서 1을 만들려고 한다.연산을 사용하는 횟수의 최솟값을 구하는 문제이다.시간 제한: 0.15초메모리 제한: 128MB 2. 접근 방식`dp[i]`에 i를 1로 만드는데 필요한 소 연산 횟수를 저장한다.점화식을 계산한다.`dp[2]`, `dp[3]`은 각각 1로 초기화 한다.`dp[i]`는 기본적으로 `dp[i-1] +1`로 초기화 한다. (1을 빼는 연산)i가 2의 배수이면, `dp[i]`는 `dp[i/2] + 1`과 비교하여 더 작은 값을 선택한다.i가 3의 배수이면, `dp[i.. 2024. 8. 28.
반응형