Outgoing Introvert

○ ? 투 포인터, 슬라이딩 윈도우 Silver 1 백준 15565 귀여운 라이언 음,, 통과는 되었는데 의문스럽다. 일단 내 답안은 다음과 같은데, n 과 k 의 범위가 1 이상 100만 이하인 상황에서 n번 반복문을 돌며 배열에 append 해주는 게 시간 초과 안뜨고 통과가 된다고..? 테스트 케이스가 문제인건가 🤔 안 될 줄 알았는데 한 번만에 통과가 되긴 했지만 몬가 찝찝하다눙,, // 122352KB 200ms let nk = readLine()!.split(separator: " ").compactMap { Int($0) } let n = nk[0] let k = nk[1] let input = readLine()!.split(separator: " ").compactMap { Int($0)..

× 슬라이딩 윈도우, 투 포인터, 누적 합 Silver 3 백준 10025 게으른 백곰 기본적인 슬라이딩 윈도우 문제로, 로직이 어렵진 않았는데 자나 깨나 조건 주의...! 답안 // 76920KB 156ms let nk = readLine()!.split(separator: " ").compactMap { Int($0) } var ice: [Int] = Array(repeating: 0, count: 1000001) var start = 0, end = 2 * nk[1] var sum = 0 for _ in 0..

투 포인터 알고리즘이란? - 1차원 배열에서 두 개의 포인터(시작점, 끝점)의 위치를 기록하면서 목표값을 구하는 알고리즘. - 완전탐색 O(n^2) -> O(n) 선형 시간 복잡도로 문제 해결 가능 - 연속된 구간의 원소들을 처리하거나, 정렬된 배열에서 무언가를 구할 때 사용 포인터 두 개가 한 곳에서 시작하는 경우 end 포인터가 0 에서 n 까지 움직일 때 까지 (배열의 길이만큼 순회하며) 반복하므로 O(n)의 시간복잡도를 가진다. (Linear time 선형 시간 복잡도) 1. 시작점과 끝 점이 첫번째 원소의 인덱스를 가리키도록 한다. 2. 부분합이 S보다 작으면 end ++ 3. 부분합이 S보다 크거나 같으면 start ++ 4. 문제에서 제시한 부분합의 조건을 만족시킬 경우 처리 모든 경우를 확..

△ 투 포인터, 누적 합 Gold 4 백준 1806 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 부분합의 합이 S 이상이 되는 것들 중에서, 가장 짧은 부분합의 길이를 구하는 문제. 내 답안 - 76292 KB,..

○ PrefixSum - Medium (난이도 이상함. Easy 임) LeetCode 2640. Find the Score of All Prefixes of an Array let solution = Solution() print(solution.findPrefixScore([2,3,7,5,10])) //[2,4,8,16,32,64] class Solution { func findPrefixScore(_ nums: [Int]) -> [Int] { var maxNum = nums[0] var conver = 0 var result = [Int]() for i in nums { maxNum = max(maxNum, i) conver += i + maxNum result.append(conver) } retu..

× Math, Dynamic Programming | Medium LeetCode 1884. Egg Drop With 2 Eggs and N Floors 뭐라는겨,,, 이해하는 데 오래걸렸다. 구간을 나눠서 계란이 확실히 깨지는 층수를 찾는다는 것 까지는 이해를 했는데... 예를 들어 10으로 나누면 10, 20 ... 100 까지 10번 던진 후, 100에서 깨지면 91~99 까지 9번을 더 던져 최소 19번을 던져야 한다. 구간을 다른 수들로 나눠도 다 19번이 나오는데 어떻게 답이 14가 될 수 있는거지??? 😮 요 영상보고 겨우 이해함 ㅎ https://youtu.be/NGtt7GJ1uiM 핵심은 구간을 일정하게 나누는 것이 아니라, 위로 올라갈수록 구간을 줄여가는 것! 크... 식을 세우면 n ..

○ Greedy | Easy 2078. Two Furthest Houses With Different Colors Constraints - n == colors.length - 2

○ (투포인터 ×) Two Pointers, Sorting | Medium 922. Sort Array By Parity II 문제 Given an array of integers nums, half of the integers in nums are odd, and the other half are even. Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even. Return any answer array that satisfies this condition. Constraints - 2

개발을 하거나 코딩테스트 문제를 풀 때, 특정 코드가 실행되는 시간을 구하고 싶을 때가 있다. 아래의 함수들을 이용해 코드의 수행시간을 측정할 수 있다. 1. CFTimeInterval public func progressTime(_ closure: () -> ()) -> TimeInterval { let start = CFAbsoluteTimeGetCurrent() closure() let duration = CFAbsoluteTimeGetCurrent() - start return duration } progressTime { //실행 시간 측정할 코드 } 2. Date public func measureTime(_ closure: () -> ()) -> TimeInterval { let startD..

○ (dp ×) Dynamic Programming, Memoization, Sorting | Medium LeetCode 1387. Sort Integers by The Power Value Constraints: - 1