종만북11 [algospot][STRJOIN] 문자열 합치기 문제 : https://algospot.com/judge/problem/read/STRJOIN 그리디로 풀었다. 문자열의 길이가 가장 짧은 것 2개 부터 차례로 합쳐나간다. 최소 힙에 문자열들을 넣고 top에 있는 것 2개를 꺼내서 두 문자열의 길이의 합을 정답에 더해나간다. 최소 힙에 있는 문자열이 1개 남을 때까지 이를 반복한다. 최소 힙에서 특정 원소를 추가하는 작업은 O(logN)이므로 총 시간복잡도는 O(NlogN)이 된다. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/algospot/STRJOIN.cpp fpdjsns/Algorithm 알고리즘 정리. Contribute to fpdjsns/Algorithm development by cr.. 2019. 7. 13. [algospot][LUNCHBOX] Microwaving Lunch Boxes 문제 : https://algospot.com/judge/problem/read/LUNCHBOX 그리디하면 나오는 단골 문제. 전자레인지에 돌리는 행동은 선형적이지만 먹는 것은 병렬적으로 처리할 수 있다. 따라서 시간을 효율적으로 사용하려면 중요한 건 먹는 시간이다. 병렬적으로 처리된다고 했을 때 가장 먼저 시작되어야 하는 것은 시간이 가장 오래 걸리는 것이다. 따라서 도시락을 먹는 시간의 내림차순으로 정렬하고 이 때 모든 도시락을 데우고 먹는 데 걸리는 시간(1)을 구하면 이 결과가 정답이 된다. (1)을 구하는 방법은 도시락을 정렬한 뒤 앞에서부터 탐색하면서 데우는 시간과 먹는 시간을 누적해간다. 데우는 시간은 선형적이므로 각 도시락의 데우는 시간의 합이다. 누적된 먹는 시간은 도시락을 데울 때 그 .. 2019. 7. 13. [algospot][MATCHORDER] 출전 순서 정하기 문제 : https://algospot.com/judge/problem/read/MATCHORDER 그리디로 풀었다. 한국팀이 지는 경우는 무시하고 이기는 경우만 고려해보자. 한국이 이길 수 있을 때 최대 효율은 가장 적은 레이팅을 가진 선수로 이기는 경우이다. 따라서 먼저 선수들의 레이팅을 오름차순 정렬했다. 그리고 러시아팀의 레이팅을 앞에서부터 탐색한다. 한국팀 선수의 인덱스 변수(korInd)를 하나 두고 이를 0으로 초기화한다.(한국팀의 레이팅도 앞에서부터 탐색.) 탐색 중인 러시아팀의 레이팅보다 같거나 큰 한국팀 레이팅이 나올 때까지 korInd를 증가시킨다. 찾는 경우 정답 + 1을 하고 korInd는 이미 특정 러시안 선수와 매칭 되었으므로 더이상 사용하지 못한다. 따라서 korInd도 +1.. 2019. 7. 13. [algospot][ASYMTILING] 비대칭 타일링 문제 : https://algospot.com/judge/problem/read/ASYMTILING DP로 풀었다. 먼저 가능한 모든 경우의 수를 구해서 dp 배열에 저장한다. dp[i] = 사각형의 너비가 i일 때 가능한 타일링 방법의 수 = dp[n - 1] + dp[n - 2] 점화식은 위와 같다. dp[n-1]은 현재 칸에 1 * 2를 채울 때 가능한 타일링 방법의 수이고 dp[n-2]는 현재 칸과 다음 칸에 2 * 1 타일들로 채울 때 가능한 타일링 방법의 수이다. 모두 가능한 경우를 구했으면 대칭한 타일링 방법의 수를 구한다. 대칭한 경우는 위와 같다. 빨간색 부분과 파란색 부분이 같으면 대칭한 경우이다. 위 2개는 짝수인 경우이다. 짝수인 경우 반으로 나눈 부분(N/2)이 같은게 나올 때와 .. 2019. 6. 12. [algospot][PI] 원주율 외우기 문제 : https://algospot.com/judge/problem/read/PI DP 문제로 풀었다. dp[ind] = 문자열[ind~끝]으로 구할 수 있는 최소 난이도. = 최소값(문자열[ind~ind+len)의 난이도 + dp[ind+len]) (3 2019. 6. 8. [algospot][JLIS] 합친 LIS 문제 : https://www.algospot.com/judge/problem/read/JLIS 배열 A, B의 인덱스(indA, indB)를 파라미터로 받는 재귀함수를 만든다. A[indA], B[indB] 는 증가 부분 수열에 반드시 포함된다고 가정한다. 따라서 A[indA], B[indB]의 최대 값보다 큰 배열 요소만이 증가 부분 수열에 추가 될 수 있다. int solve(indA, indB){ int maxNum = max(A[indA], B[indB]); for(nextInd = [indA + 1, N)){ if(maxNum < A[nextInd]) ans = max(ans, solve(nextInd, indB) + 1); } } 위 코드는 배열 A에 정답 배열에 들어갈 수 있는 다음 배열 .. 2019. 6. 7. 이전 1 2 다음
