알고리즘 문제/Codeground10 [codeground] 123. 다이어트 codeground - Practice - SCPC 6회 예선 - 123. 다이어트 문제 : https://www.codeground.org/practice/practiceProblemList 그리디로 풀었다. A 식당, B 식당메뉴들을 오름차순 정렬한다. 가격이 작은 K개의 메뉴들을 가져와서 A 식당 메뉴의 최저가, B 식당 메뉴의 최고가들을 차례로 페어로 묶는다. 페어로 묶은 메뉴 가격들의 합 중 최고가가 정답이 된다. 시간복잡도는 O(NlogN + K). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codeground/123.%20%EB%8B%A4%EC%9D%B4%EC%96%B4%ED%8A%B8.cpp 2021. 7. 6. [codeground] 98. 소수 수열 codeground - Practice - SCPC 5회 예선 - 98. 소수 수열 문제 : https://www.codeground.org/practice/practiceProblemList 먼저 에라토스테네스의 체로 소수인지 여부를 저장하는 배열을 구한다. 127을 입력으로 받으면 12, 17, 27로 얻을 수 있는 점수를 구한다음 이 중 가장 큰 점수 + 1이 127로 얻을 수 있는 최대 점수가 된다. -> 점화식 이미 구한 숫자의 점수를 다시 탐색할수도 있으므로 배열을 만들어 memoization 한다. 만약 점수를 구하고자 하는 숫자가 소수가 아닌경우 0을 반환한다. (불가능) 숫자가 일의 자리라면 1을 반환한다. (점수 획득 가능) A, B 숫자로 점수를 구한다음 A == B (3), A > .. 2019. 9. 19. [codeground] 57. 괄호 codeground - Practice - SCPC 3회 예선 - 57. 괄호 문제 : https://www.codeground.org/practice/practiceProblemList 조건 1. 빈 문자열은 올바른 괄호 문자열이다. 2. S1이 올바른 괄호 문자열이라면, (S1), {S1}, [S1] 모두 올바른 괄호 문자열이다. 3. S1과 S2가 올바른 괄호 문자열이라면, S1S2도 올바른 괄호 문자열이다. 조건 1번에 의해 정답 ans의 초기값은 0이다. 조건 2를 위해서 스택을 만들고 여는 괄호인 경우 스택에 해당 괄호의 인덱스를 넣는다. 닫는 괄호인 경우 스택의 스택의 top에서 가장 최근의 여는 괄호 인덱스를 가져와서 여는 괄호와 현재 닫는 괄호의 짝이 맞다면 그 길이를 정답과 비교하여 최.. 2019. 9. 18. [codeground] 9. 화학자의 문장 codeground - Practice - 연습문제 - 9. 화학자의 문장 문제 : https://www.codeground.org/practice/practiceProblemList vector alph(26, vector (27, false)); vector check;//-1: 방문 x. 0: 불가능. 1: 가능 화학원소 기호들로 위 배열 2개를 채웁니다. alph 배열은 원소 기호들로 문자를 만들 수 있는지 여부를 저장합니다. 예를 들어 alph[0('a')][0] 은 a를 만들 수 있는지를 뜻하고 alph[0('a')][1('a')]은 aa를 만들 수 있는지를 뜻합니다. check 배열은 입력받은 문자열을 s라고 했을 때 check[ind] 는 s[ind~끝]에 해당하는 부분 문자열을 화학 원소.. 2019. 9. 15. [codeground] 71. 정수 정렬하기 codeground - Practice - 연습문제 - 71. 정수 정렬하기 문제 : https://www.codeground.org/practice/practiceProblemView 모든 수를 입력받아 오름차순으로 정렬하고 배열을 한바퀴돌면서 홀수번째는 더하고 짝수번째는 뺀다. 다른 방법도 있을까 생각해봤는데, 딱히 생각나는게 없다. N개수도 작고.. 시간복잡도는 O(NlogN). 정확히는 정렬하는 시간 O(NlogN) + 배열한바퀴씩 돌면서 정답구하는 시간 O(N). 공간복잡도는 O(N). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codeground/71.%20%EC%A0%95%EC%88%98%20%EC%A0%95%EB%A0%AC%ED%95.. 2019. 9. 14. [codeground] 31. 프리랜서 codeground - Practice - SCPC 2회 예선 - 31. 프리랜서 문제 : https://www.codeground.org/practice/practiceProblemList DP를 Top-down(탑다운) 방식으로 채워나가면서 문제를 해결합니다. D[0][ind] = ind주에 P사 작업했을 때 얻을 수 있는 최대 이익 D[1][ind] = ind주에 Q사 작업했을 때 얻을 수 있는 최대 이익 go(int ind) = ind주까지 작업했을 때 얻을 수 있는 최대 이익 반환 만약 ind주에 P사를 작업했을 때 얻을 수 있는 최대 이익은 D[0][ind] = go(ind-1) + P[ind] 입니다. ind주에 Q사를 작업했다면 그 전주에도 Q사 작업을 해야 하므로 D[1][ind] = g.. 2019. 9. 13. 이전 1 2 다음