엘리스 코드 챌린지 (2) 썸네일형 리스트형 [엘리스 알고리즘 코드 챌린지] Day 9. 격자 위의 ELICE (Java) 문제제한 시간 : 7초핵심다익스트라 알고리즘을 사용하여 각 문자 위치 간의 최단 경로를 찾을 수 있다.다익스트라 알고리즘의 시간 복잡도: O((V+E)logV), 여기서 V는 노드의 수, E는 간선의 수전체 시간 복잡도: O(N^2 log N^2)N이 1000일 때, 대략 1000^2 * log(1000^2) ≈ 10^8 정도의 연산이 필요하므로 7초 내에 충분히 해결 가능 전체 경로는 (1,1) -> E -> L -> I -> C -> E 순서로 이동하는 최단 경로의 합이 된다.단 E는 두 개이므로 둘 중 어느 것을 먼저 방문했을 때, 더 빠른지 고려해야 한다.Code (Java)import java.util.*;class Main { static int N; static int[][] gr.. [엘리스 알고리즘 코드 챌린지] Day 5. 수열 복원 (Java) 문제핵심핵심 로직단순한 방법으로는 모든 부분 수열의 합 조합을 제거하는 것이다.수열이 [1, 2, 4] 인 경우를 생각하면모든 부분 수열의 합은 아래와 같다.0a1a2a3a1 + a2a1 + a3a2 + a3a1 + a2 + a3 a1, a2, a3는 원래의 수열이고 그 외의 것들은 a1, a2, a3를 조합하여 합한 것임을 알 수 있다.따라서 주어진 부분 수열의 합을 정렬하고 작은 수부터 짝지어 합한 후 제외하면 결과적으로 원래의 수열이 남게 된다. 예를 들어 [0 1 2 3 4 5 6 7] 이 주어졌다면, 일단 공집합 0을 제외하고1 + 2 = 3 제거 [1 2 3 4 5 6 7]1 + 4 = 5 제거 [1 2 3 4 5 6 7]1 + 6 = 7 제거 [1 2 3 4 5 6 7]2 + 4 = 6 제거.. 이전 1 다음
