알고리즘 문제408 [leetcode][1200] Minimum Absolute Difference 문제 : https://leetcode.com/problems/minimum-absolute-difference/ arr 배열을 오름차순으로 정렬한다. b - a 값은 오름차순 정렬시 바로 옆에 있는 요소들의 차가 최소 값이 된다. 따라서 정렬된 arr 배열을 앞에서부터 탐색하면서 [arr[i], arr[i-1]]가 [a, b]이다. arr[i-1] - arr[i] 값을 구하고 이 값이 이때동안 계산한 diff의 최소값보다 크다면 정답이 될 수 있으므로 skip. diff 최소 값이랑 같다면 정답배열에 추가. diff 최소 값보다 작다면 이때동안 구한 정답 배열을 빈 배열로 초기화 시키고 정답 배열에 추가한다. 시간복잡도는 정렬하는데 걸리는 시간인 O(NlogN). 소스코드 : https://github.. 2019. 9. 22. [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. [leetcode] 1191. K-Concatenation Maximum Sum 문제 : https://leetcode.com/problems/k-concatenation-maximum-sum/ A : arr 배열 내 앞에서부터 최대부분합 B : arr 배열 내 뒤에서부터 최대부분합 C : arr 배열 내 최대부분합 D : arr 배열 총합 이라고 하자. 정답이 가능한 경우는 위와 같다. 위 그림에서 한 칸이 배열 arr이라고 했을 때 1. B D D D A 2. D D D D D 3. C 4. B A 이 네가지 중 최대 값이 정답이 된다. 시간복잡도는 O(arr.length + k) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1191.%20K-Concatenation%20Maximum%20Sum.cpp 2019. 9. 16. [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. 이전 1 ··· 49 50 51 52 53 54 55 ··· 68 다음
