Outgoing Introvert

○ 다이나믹 프로그래밍 (나는 재귀로 풀어뜸) - Silver 3 백준 1904 01타일 규칙 찾는데 시간 너무 오래걸림 ㅠ 5 까지는 무난무난. 아 피보나치구나 했는데 확인용으로 6도 계산해보자 하고 6에서 3개 빼먹고 엥 피보나치가 아니었나..? 하고 멍청이짓하다가 시간날림 ㅎ 암튼 결론은 피보나치 수열이다. 나는 재귀로 품 // recursion - 69100KB 12ms let n = Int(readLine()!) print(tiles(1, 0, 1)) func tiles(_ a: Int, _ b: Int, _ c: Int) -> Int { if a == n { return (b + c) % 15746 } return tiles(a + 1, c % 15746, (b + c) % 15746) } 근..

× 수학, 정수론, 유클리드 호제법 Silver 3 백준 1735 분수 합 Euclidean algorithm 유클리드 호제법 : 두 양의 정수의 최대공약수를 구하는 방법 두 양의 정수 a, b (a > b) 에 대하여 a = bq + r (0 Int { print(a, b) if b == 0 { return a } else { return gcd(b, a % b) } } 이거 안쓰고 푸니까 당연히(?) 시간 초과 뜸 30000 이하 자연수니까 3만 * 3만 = 9억 -> 최악의 경우 4.5억번 반복문 돌아야,,, // 시간초과 let first = readLine()!.split(separator: " ").compactMap { Int($0) } let second = readLine()!...

○ 그리디 Silver 3 백준 1213 팰린드롬 만들기 * 팰린드롬 : 거꾸로 읽어도 동일한 문장, 숫자, 문자열 ex) 이효리, 토마토 임한수와 임문빈은 서로 사랑하는 사이이다. 근친상간 문제 인가요..? (개소리임 제송 ㅎ) // 69108KB 8ms let name = readLine()! print(palindrome(word: name)) func palindrome(word: String) -> String { var dict = [Character: Int]() var oddNumberCount: Int = 0 var center: String = "" var result: String = "" for i in name { if let _ = dict[i] { dict..

○ ? 투 포인터, 슬라이딩 윈도우 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