땀두 블로그

우리가 흔히 알고리즘에서 사용하는 탐욕법은 현재 위치에서 가장 최적의 해를 구해가는 과정을 연속해서 진행하는 문제이다. 이러한 문제 유형 중에는 활동 선택 문제가 있는데 이는 n개의 시작점과 끝점을 주어진다. 문제를 해결하는 사람은 한번에 하나의 행동만 작업할 수 있기 때문에 이러한 행동의 합을 최대로 만드는 문제이다. 활동선택 문제는 활동 중에서 종료 시간을 기준으로 해당 내용들을 정렬하여 해결할 수 있다. 이에 대한 코드는 아래 위키피디아를 참고하면 된다. en.wikipedia.org/wiki/Activity_selection_problem 활동 선택 문제를 해결하는 방법은 먼저 각 활동에 대한 종료시간을 기준으로 오름차순하고, 첫 활동에서부터 다음활동 시작시간이 전 활동의 종료시간보다 짧으면 그 ..

문제에 대한 이해를 잘못하여 처음에는 인덱스까지 이용해서 해결해야 하는 문제인줄 알았지만 단순 그리디알고리즘을 이용한 문제였다. 입력받은 숫자들을 sorting해준 이후 2중 for문을 이용하여서 여태까지의 값들을 계속 더해주면 문제를 해결 가능하다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class p11339 { public static void main(String[] args) throws IOException { // TODO Auto-generated ..