반응형 Problem Solving155 백준 5719 : 거의 최단 경로 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net [ 문제풀이 ] 한 정점에서 다른 한 정점으로 가는 최단 경로를 구하는 것이기 때문에 다익스트라 알고리즘을 사용하면 된다. 초기에는 다익스트라로 최단 경로를 구한 후 최단경로가 갱신될 때까지 간선 제거+다익스트라를 반복하였다. 하지만 최단 경로가 2개 이상인 경우 문제가 발생하였다. 위와 같은 경우 하나의 최단 경로 간선을 제거한다면 두 번째 다익스트라에서 1->4-.. 2021. 6. 30. 백준 1593 : 문자 해독 https://www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net [ 문제풀이 ] W의 길이가 최대 3000이기 때문에 W의 문자들로 만들 수 있는 모든 순열을 생성 후 검사한다면 시간초과가 발생하게 된다.검사해야하는 문자열의 길이는 고정이기 때문에 슬라이딩 윈도우 기법을 사용하여 구간을 검사해나가면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import j.. 2021. 6. 29. 이전 1 ··· 15 16 17 18 다음 반응형
