동적프로그래밍4 [알고리즘] ACM Craft (백준 1005번) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 그래프 상으로 본인보다 앞서 있는 건물들이 모두 지어져야 해당 건물을 지을 수 있다는 설정을 보면 알 수 있듯이 위상 정렬을 쓰는 문제다. 다만 건물 건설 시간이 각각 다르다보니 기교를 가해야한다. 결론적으론 '위상정렬 + DP' 문제다. Solution 1. topologicalSort 함수 static int topologicalSort(int N, int W, int[] complete_time, ArrayList graph, int inEdge[].. 2020. 10. 5. [알고리즘] 등굣길 (프로그래머스 Level3) 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 그림만 봐도 느껴지겠지만 탐색 문제이다. 다만 문제에서 최단 경로라고 언급을 했으니 BFS를 이용하기로 했다. 하지만 Level3 문제답게 단순한 BFS 문제는 아니다. 단순히 '최단 경로' 만 구하라고 한 것이 아니라 '최단 경로의 개수'를 구하라고 했다. 즉 특정 노드를 기준으로 그곳에 도착한 경로들의 개수들을 세어야 하고 이것은 동적 프로그래밍을 이용해서 메모이제이션해야한다. 즉 BFS + DP 문제이다. (추후에 알게된 사실인데 BFS도 .. 2020. 9. 7. [알고리즘] 팰린드롬? (백준 10942번) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 팰린드롬을 판별하는 동적 프로그래밍 + 문자열 처리 문제이다. 우선 팰린드롬이란 문자열 중앙을 기준으로 좌측, 우측이 마치 데칼코마니처럼 일치하는 경우를 말한다. EX) 121, 5, 2345432 문제에선 S 인덱스부터 E 인덱스까지의 문자열이 팰린드롬인지를 판별하라고 했는데 동적 프로그래밍을 사용하지 않고 일일이 계산한다면 O(N ^ 3) 혹은 O (N * M) 의 시간이 걸리는데 최악의 경우 무려 80억번의 계산이 필요하다. 하지만 동적 프로그래밍을 사용해서 구하게 된다면 O (N ^ 2) 의 시.. 2020. 8. 25. [알고리즘] LCS (최장 공통 부분) 찾기 public class Main { public static void main(String[] args) { String x = "abcdedc"; String y = "bbbcec"; int c[][] = new int[x.length()][y.length()]; String lcs[][] = new String[x.length()][y.length()]; for(int i = 0;i< lcs.length;i++) for(int j = 0;j c[i][j-1]) { c[i][j] = c[i-1][j]; lcs[i][j] = lcs[i-1][j]; } else { c[i][j] = c[i][j-1]; lcs[i][j] = lcs[i][j-1]; } } } } System.out.println(c[x.le.. 2020. 8. 22. 이전 1 다음
