알고리즘 문제408 [algospot][MATCHORDER] 출전 순서 정하기 문제 : https://algospot.com/judge/problem/read/MATCHORDER 그리디로 풀었다. 한국팀이 지는 경우는 무시하고 이기는 경우만 고려해보자. 한국이 이길 수 있을 때 최대 효율은 가장 적은 레이팅을 가진 선수로 이기는 경우이다. 따라서 먼저 선수들의 레이팅을 오름차순 정렬했다. 그리고 러시아팀의 레이팅을 앞에서부터 탐색한다. 한국팀 선수의 인덱스 변수(korInd)를 하나 두고 이를 0으로 초기화한다.(한국팀의 레이팅도 앞에서부터 탐색.) 탐색 중인 러시아팀의 레이팅보다 같거나 큰 한국팀 레이팅이 나올 때까지 korInd를 증가시킨다. 찾는 경우 정답 + 1을 하고 korInd는 이미 특정 러시안 선수와 매칭 되었으므로 더이상 사용하지 못한다. 따라서 korInd도 +1.. 2019. 7. 13. [leetcode] 1052. Grumpy Bookstore Owner 문제 : https://leetcode.com/problems/grumpy-bookstore-owner/ 슬라이딩 윈도우로 풀었다. grumpy가 0인 경우는 X 타임과 상관없이 항상 일정하다. -> 미리 저장. (변하지 않는 값) grumpy가 1인 경우는 X타임에 따라 달라진다. -> 슬라이딩 윈도우로 최대가 되는 값을 구한다. (변하는 값) customers를 앞에서부터 탐색하면서 슬라이딩 윈도우 범위내에 grumpy가 1인 custmoers 배열 요소의 합을 구한다. 구한 합의 최대 값과 gumpy가 0일 때의 customers 배열의 합을 더한 값이 정답이 된다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/1e7dff3e4b90c1d88e7b60.. 2019. 6. 15. [codeground] 36. 재활용 codeground - Practice - SCPC 2회 본선 - 36. 재활용 문제 : https://www.codeground.org/practice/practiceProblemList vector arr; //arr[i] : i집의 x위치 vector sum; //sum[i] : 1~i 집들의 x위치 합 int d[501][501]; //d[s][k] : s~n 까지의 집이 k개의 수집통에 재활용을 넣는 경우 드는 최소 비용 int go(int s, int k) //d[s][k] 채우는 함수 일단 x좌표에 대해 오름차순 정렬해준다. 이제 d배열을 채워보자. 만약 a~e 집이 1개의 재활용 수집통을 사용한다고 했을 때, 가장 적절한 수집통의 위치는 어디가 될까. 가장 적절한 수집통의 위치를 x라고 했.. 2019. 6. 12. [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 ··· 52 53 54 55 56 57 58 ··· 68 다음
