Algorithm PS

문제https://www.acmicpc.net/problem/9251 풀이LCS(Longest Common Subsequence, 최장 공통 부분 수열)는  임의의 두 수열에서 각각의 부분 수열들 중, 서로 같은 부분 수열 중에서 가장 긴 수열을 의미한다. 문제의 예제를 보면 두 수열로 ACAYKP와 CAPCAK가 있다. 각 수열의 부분 수열은 아래와 같다.ACAYKP의 부분 수열 : {A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, {A, A}, ... , {ACAYKP}CAPCAK의 부분 수열 : {C}, {A}, {P}, {C}, {A}, {K}, {C, A}, {C, P}, ... , {CAPCAK}이들 중 {A}, {C}, {K}, {P}, {A, A}, ... , {A, C,..

문제https://www.acmicpc.net/problem/11053풀이이 문제는 DP 문제, LIS를 이용해서 푸는 문제이다.LIS (Longest Increasing Subsequence) : 최장 증가 부분 수열: 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘 문제에서 주어진 수열을 보면 arr = {10, 20, 10, 30, 20, 50}이므로 수열을 담는 배열인 arr[]과 dp 값을 설정하는 배열인 dp[]를 생성한다. 그리고 수열을 입력받으면서 dp 배열의 값들을 1로 초기화한다.dp 배열을 초기화하면 각 위치에서 최소 길이는 1이다. → dp = {1, 1, 1, 1, 1, 1}i = 2일 때, arr[2] = 20이다.j = 1에서 arr[2] > arr[1]..

문제https://www.acmicpc.net/problem/9657풀이돌이 N개가 있고 상근이가 먼저 게임을 시작하며 돌을 1개, 3개, 또는 4개를 가져갈 수 있을 때 마지막 돌을 가져가는 사람이 이기는 게임이다. 문제에 '완벽하게' 라는 조건이 붙었기 때문에 상근이가 이기는 쪽으로 게임을 해야 한다. 돌의 개수 별로 돌을 가져간 횟수?를 저장하는 배열 arr을 생성한다.돌을 한 번에 4개를 가져갈 수 있기 때문에 N=1 ~ N=4까지는 고정 값을 넣어주었다.N = 1 : 상근이가 돌 1개를 가져가면 게임이 끝난다. → 상근 Win : arr[1] = 1N = 2 : 상근이가 돌 1개를 가져가고 창영이가 돌 1개를 가져가면 게임이 끝난다. → 창영 Win : arr[2]  = 2N = 3 : 상근이가..

문제https://www.acmicpc.net/problem/1931 풀이이 문제에 그리디 알고리즘을 사용해서 풀었다. 최대한 많은 선택을 하기 위해서는 회의실 종료 시간이 빨라야 하고, 이전에 선택한 결과가 이후의 결과에 영향을 미치면 안된다.  즉, 서로 겹치지 않는 회의들에 대하여 종료 시간이 빠르면 더 많은 회의를 선택할 수 있다. 따라서 입력받은 회의들을 종료 시간을 기준으로 오름차순 정렬하고, 종료 시간이 같은 회의들은 시작 시간을 기준으로 오름차순 정렬했다.가장 빨리 끝나는 것은 a1이므로 첫 번째로 a1을 선택하고 a1의 종료 시간을 end에 저장한다. 그리고 end와 이후의 회의 시간의 시작 시간을 바교하여 end Codeimport java.util.*;import java.io.*;p..

문제https://www.acmicpc.net/problem/2170 풀이선의 정보를 입력받은 후 계산을 순차적으로 하기 위해 선의 시작 지점을 기준으로 오름차순 정렬하였으며 시작 지점이 같은 경우에는 끝 지점을 기준으로 오름차순 정렬하였다.  처음에 이전 선의 정보를 start에 시작 지점을 저장하고 end에 선의 끝 부분을 저장했다. 그리고 end - start로 현재까지의 선의 길이를 저장했다. 이제 이후의 선들을 비교할 때마다 3가지 조건에 맞게 계산을 해줘야 한다.현재 선이 이전 선에 겹치는 경우(현재 선이 이전 선에 포함되는 경우) → continue로 넘어간다.현재 선의 시작 지점이 이전 선에 겹치는(포함되는) 경우 → 현재 선의 끝 지점 - 이전 선의 끝 지점(end)를 length에 더해..

문제https://www.acmicpc.net/problem/11000 풀이수업의 시작 시간과 종료 시간을 입력 받는다. N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업이 가능하도록 해야 한다.단, 수업이 끝난 직후와 이후에 같은 강의실에서 다음 수업을 시작할 수 있다. 우선 2차원 배열로 수업의 시작 시간과 종료 시간을 입력받았다. 그리고 입력 데이터의 시작 시간을 오름차순으로 정렬했으며, 만약 시작 시간이 같은 경우에는 끝나는 시간을 오름차순으로 정렬하였다. 우선순위 큐(PriorityQueue)에 가장 처음 시작하는 강의의 종료 시간을 넣는다. 그리고 배정이 되지 않은 강의의 시작 시간이 우선순위 큐 안에서 가장 빠른 강의의 종료 시간보다 늦다면, 현재 우선순위 큐에서 top에 있는 ..

문제https://www.acmicpc.net/problem/15903 풀이카드의 개수 n개에 대하여 합체를 m번 한다.문제의 조건을 보면 두 장의 카드를 골라 카드에 쓰여진 수를 더하여 나온 수를 두 카드에 다시 덮어쓰는 것을 m번 반복하는 것이다.그리고 합체가 다 끝났을 때, 남은 카드들의 합의 최소값을 계산하는 것이다. 예제 2번으로 다시 설명을 하자면 4장의 카드인 4, 2, 3, 1의 카드들을 2번 합체한다. 단, 남은 카드들의 합의 가장 잡은 값을 만들려면 매번 합체할 때마다 가장 작은 두 수를 뽑아서 더해야 한다. 그래서 우선순위 큐(PriorityQueue)의 기본형을 사용하여 poll() 할 때마다 가장 작은 수를 뽑도록 하였다.1번째 합체 → 1, 2를 뽑아서 1+2=3을 두 카드에 덮..

문제https://www.acmicpc.net/problem/11652풀이카드에 적힌 수와 적힌 수의 카드의 개수를 저장해야 하므로 HashMap을 사용했다. 가지고 있는 수면 개수만 +1해서 저장하고, 없는 카드면 카드 번호와 1을 해시맵에 저장하도록 하였다.그리고 매 반복마다 해당 카드에 대한 개수를 확인해서 개수가 최대인 카드를 result에 저장했다.만약 가장 많이 갖고 있는 카드가 여러가지라면 Math.min()으로 작은 것을 저장하도록 하였다. 문제를 보면 "숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -2^{62}보다 크거나 같고, 2^{62}보다 작거나 같다." 라고 되어있으므로 타입을 long 타입으로 해야 한다.Codeimport java.util.*;import java.io..

문제https://www.acmicpc.net/problem/7795풀이A의 요소와 B의 요소를 비교하면서 A의 요소가 B의 요소보다 큰 경우의 개수를 구한다. 처음에 A의 요소와 B의 요소를 배열로 받고 이중 for문으로 직접 비교하니 시간 초과가 떠서 B의 요소를 Arrays.sort()로 정렬을 한 뒤, B의 요소를 이분탐색하며 A의 요소와 비교하는 방법을 사용했다.Codeimport java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReade..

문제https://www.acmicpc.net/problem/2910풀이문제를 보면 값에 대한 빈도수를 저장해서 정렬해야되기 때문에 HashMap 생각했고, 빈도수가 같은 경우에는 먼저 등장한 숫자가 앞으로 나오도록 해야 하므로 순서를 지정할 수 있는 LinkedHashMap을 사용했다. 를 가져야 하기 때문에 를 갖는 LinkedHashMap인 map을 생성하여 문자열을 끊어서 입력받았다.입력받은 문자열을 정수로 변환해서 map에 넣어줄건데, map에 해당 값(key)이 있다면 value+1을 하여 다시 저장해주고, key가 없다면 새로운 key값과 value에 1을 저장하였다. 그리고 map의 key들을 ArrayList에 저장하여 Comparator를 사용하여 map의 key에 대한 value(빈도..