Medium174 [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. [algospot][WILDCARD] Wildcard 문제 : https://algospot.com/judge/problem/read/WILDCARD DP로 풀었다. dp[i][j] = pattern[i~끝] 부분문자열과 s[j~끝] 부분문자열이 같은가(같으면 1, 다르면 0, 아직 탐색 전이면 -1) 패턴문자열(pattern)과 패턴에 맞는지 확인하고자 하는 문자열(s)가 있다고 할 때 DP에 사용할 배열은 위와 같이 나타낼 수 있다. 패턴 문자열에 올 수 있는 문자는 '*', '?', 알파벳이다. 만약 알파벳이라면 pattern[i]와 s[j]가 같은지 체크하고 다르면 false를 반환, 같다면 i+1, j+1 부터 다시 탐색해간다. '?' 인 경우 s[j] 가 어떤 문자가 오던지 정답이 가능하므로 i+1, j+1 부터 다시 탐색해나간다. '*' 인 경.. 2019. 6. 3. [algospot][CLOCKSYNC] Synchronizing Clocks 문제 : https://algospot.com/judge/problem/read/CLOCKSYNC 완전탐색으로 돌린다. 만약 하나의 스위치를 4번 돌리면 원래 상태와 같아진다. 따라서 하나의 스위치를 0~3번 돌리면서 탐색해나간다. void solve(시계상태, 스위치 번호, 스위치 누른 횟수){ for (현재 스위치 누른 횟수 = [0,4)) { solve(시계상태, 스위치 번호 + 1, 스위치 누른 횟수 + 현재 스위치 누른 횟수); 스위치 한 번 눌렀을 때 시계상태 갱신. } } 의사 코드로 짜면 위와 같다. 여기에 몇 가지 종료 조건과 정답 갱신하는 코드 추가해준다.. 시간복잡도는 O(4^10). 10은 스위치 개수이다. 소스코드 : https://gist.github.com/fpdjsns/78c.. 2019. 5. 31. [leetcode] 1020. Number of Enclaves 문제 : https://leetcode.com/problems/number-of-enclaves/ DFS 문제. 배열 A를 탐색하면서 1일 때 현재 요소를 기준으로 상하좌우로 탐색(DFS)하면서 1의 개수를 센다. 세면서 방문한 배열 요소는 0으로 갱신한다. 만약 DFS 탐색시 배열밖으로 벗어난다면 1의 개수는 정답이 될 수 있으므로 정답에 더해준다. 소스코드 : https://gist.github.com/fpdjsns/91d296e10a828da48b4751a9fad00080 2019. 4. 8. [leetcode][1021] Best Sightseeing Pair 문제 : https://leetcode.com/problems/best-sightseeing-pair/ 투포인터로 풀었다. 배열 A를 1 인덱스부터 탐색하면서 탐색 중인 원소를 j 인덱스로 본다. A[i] + A[j] + i - j의 최대값이 정답이다. i 인덱스는 A[i] 2019. 3. 29. [leetcode][1014] Capacity To Ship Packages Within D Days 문제 : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/ 이분탐색으로 풀었다.l = weights 배열중 가장 작은 수. r = weights 배열의 합.정답이 될 수 있는 값의 제일 작은 값(l), 제일 큰 값(r)을 구하고 l을 증가, r을 감소 시키면서 정답이 될 수 있는 가장 작은 수를 구한다.l과 r의 중간값을 구한다음, 구한 중간 값으로 weights 배열을 탐색하면서 소요되는 day를 직접 구해본다.구한 day가 D보다 작거나 같다면 정답이 될 수 있는 경우이므로 r을 중간값으로 갱신한다음 다시 반복한다.day가 D보다 크다면 정답이 될 수 없으므로 l을 중간값+1으로 갱신 후 다시 반복한다.이를 l이 r보다 크거.. 2019. 3. 22. 이전 1 ··· 22 23 24 25 26 27 28 29 다음