본문 바로가기

Algorithm

 (140)
이코테 - 커리큘럼 with JAVA 해결 기본적으로는 위상정렬 알고리즘을 사용한다. 하지만, 주의할 점은 다음 노드를 방문할 때이다. 예를 들어, 3번 과목은 1, 2번 과목을 선수행해야하고 2번은 1번과목을 선수행해야한다고 가정하자. 이 때, 3번과목의 비용은 (2번과목까지 선수행 비용 + 3번 비용) vs (1번과목까지 선수행 비용 + 3번 비용) 중 큰 것으로 매겨진다. 코드 import java.util.*; // 커리 큘럼 public class Practice3 { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] graph = new int[n]; int[] times = new int[n]..
이코테 - 도시 분할 계획 with JAVA 해결 아이디어 : 크루스칼 알고리즘으로 노드들을 비용이 적은 간선부터 연결을 한다. 이 때, 사이클 발생시에는 간선을 설치를 하지 않는다. 그렇게 진행한다면 모든 노드들이 연결이 되는데 마지막 가장 비용이 큰 노드를 제거하여 그룹을 두개로 나누면 된다. 코드 import java.util.*; // 도시 분할 계획 public class Practice2 { public static int[] parent; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); // 부모 리스트 갱신 parent = new int[n+1]; for(int i=1..
이코테 - 정확한 순위 with JAVA 해결 - 기본적으로 플로이드 워셜 알고리즘을 사용한다. - 그래프를 만들어 노드 A, B 중 한쪽 방향으로만이라도 이동가능하면 두 사람은 비교 가능하다고 판단이 가능하다. - 한 노드에서 모든 노드로 다 비교가 가능하면(한쪽 방향이라도 이동이 가능하다면) 정확한 순위를 알 수 있다. 실수 - (int)1e9는 비교가 가능하다. - i, j 구분이 안되어서 실수를 했다. - 한쪽 방향으로만이라도 라는 로직을 처리할 때, and 연산자를 사용하였다. 코드 package JAVA.TCT.ShortestWay; import java.util.*; // 정확한 순위 public class Q2 { public static void main(String[] args){ Scanner sc = new Scanner(..
이코테 - 편집거리 with JAVA 해결 - 동작은 삽입, 삭제, 교체가 가능하다고 문제에서 제시한다. sunday를 saturday로 변경한다고 가정하자 2차원 테이블은 다음과 같이 구성된다. (2차원 테이블 : 가장 왼쪽열에 있는 sunday를 가장 위쪽행에 있는 saturday로 변경하는 비용 테이블, 0은 빈문자열을 의미) 0 S A T U R D A Y 0 0 (0, 0) 1 2 3 4 5 6 7 8 S 1 0 1 2 3 4 5 6 7 U 2 N 3 D 4 A 5 Y 6 - 예를들어, (2, 4)는 s1의 처음부터 두번째까지 글자를 s2의 처음부터 4번째 글자로 만드는 가장 적은 연산수이다. 삽입 : 왼쪽 칸 + 1 삭제 : 위쪽 칸 + 1 교체 : 왼쪽 위칸 +1 삽입, 삭제, 교체 중 가장 작은 값을 찾아 선택 후 + 1을 더..
이코테 - 못생긴 수 with JAVA 해결 못생긴 수는 2,3,5만을 약수로 갖는 수들을 의미한다. 따라서, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 순서대로 이루어진다. 중요한 것은 못생긴수는 못생긴수에 2, 3, 5를 곱한 결과로 이루어진다는 것이다. 문제에서 1은 못생긴 수라고 주어진다. 1 1x2, 1x3, 1x5 = [1, 2, 3, 5] 2 2x2, 2x3, 2x5 = [1, 2, 3, 5, 4, 6, 10] = [1, 2, 3, 4, 5, 6, 10] 3 3x2, 3x3, 3x5 = [1, 2, 3, 4, 5, 6, 9, 10, 15] 코드 import java.util.*; public class Q5 { public static void main(String[] args){ Scanner sc = new..
이코테 - 병사 배치하기 with JAVA 해결 전투력이 높은 순서대로 배열을 설정하기 위해 몇몇의 병사들을 제거하여 이를 설정하려고 하는데, 최대한 병사를 적게 줄여야한다. 전투력이 15 11 4 8 5 2 4라고 가정하자. 뒤에서부터 DP를 적용한다. - 전투력이 4인 병사에서 살릴 수 있는 병사의 수는 1이다. - 전투력이 2인 병사에서 4보다 작으므로 살릴 수 있는 병사의 수는 1이다. - 전투력이 5인 병사에서 2보다 크므로 병사 2에서 살릴수 있는 병수+1이고 마찬가지로 4에도 적용된다. 즉, 로직을 보면 뒤부터 진행을 하는데 이미 처리한 병사들 중 현재 전투력보다 작다면 해당 병사가 갖는 최대 병사+1 처리를 해주면 된다. 코드 import java.util.*; public class Q4 { public static void ma..
이코테 - 퇴사 with JAVA 해결 만약, 아래와 같은 표가 있다고 가정하자 첫번째 줄은 걸리는 날, 두번째 줄은 받는 돈이다. 5 5 5 5 5 5 5 5 5 5 10 9 8 7 6 10 9 8 7 6 인덱스 9에 위치한 스케줄부터 인덱스6에 위치한 일은 할 수 없다. 인덱스 5에서는 일을 할 수 있고 인덱스 10부터 다시 일할 수 있다. 하지만 10은 존재하지 않으므로 여기까지 가장 많이 벌 수 있는돈은 10이다. 인덱스1부터 4까지는 일은 할 수 있지만 일을 하게되면 인덱스 5에 위치한 일을 할 수 없다. 따라서 돈을 최대한으로 벌려면 해당 인덱스들에서는 일을 하지 않아야 한다. 인덱스 0에서 일을하면 인덱스 5부터 다시 일을 할 수 있다. 또한, 항상 DP에서는 전의 값이 현재 값의 영향을 끼치는 형태고 기존의 리스트의 값을 ..
이코테 - 효율적인 화폐 구성 with JAVA 해결 예를 들어, 동전이 2원 3원이 존재하고 15원을 만든다고 가정하자. 2원만 사용하는 경우 만약, 0원이 존재한다면 0원+2원으로 2원을 만들 수 있다. 만약, 1원이 존재한다면 1원+2원으로 3원을 만들 수 있다. 만약, 2원이 존재한다면 2원+2원으로 4원을 만들 수 있다. 만약, 3원이 존재한다면 3원+2원으로 5원을 만들 수 있다. 이를 식으로 정리하면, dp[i] = Math.min(dp[i], dp[i-2]+1) 이 된다. 2원 = Math.min(2원, (2-2)원 +1) 3원 = Math.min(3원, (3-2)원 +1) 4원 = Math.min(4원, (4-2)원 +1) 코드 package JAVA.TCT.DP; import java.util.*; // 효율적인 화폐 구성 publi..

티스토리툴바