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..

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

△ 그리디 Silver1 백준 1931번 회의실 배정 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주..

○ 그리디 Silver4 백준 11047번 동전 0 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 그리디 유형의 대표 문제 동전 가능한 범위 내에서 무조건 가치가 큰 동전부터 더해나가면 되는 문제. 처음에 결과값..

Gold3 × 누적 합, 수학, 순열과조합 백준 10986번 나머지 합 능력 밖의 문제였다,, 절대 풀 수 없어 1차 시도 : 시간초과 직관적으로 누적 합만 사용해서 간단하게 구현해보면 다음과 같다. n 의 범위가 100만 이하이니까 중첩 반복문으로 돌리면 O(n^2)으로 당연히 시간초과 뜰 줄 알았음 let nm = readLine()!.split(separator: " ").compactMap { Int($0) } let (n, m) = (nm[0], nm[1]) let arr = readLine()!.split(separator: " ").compactMap { Int($0) } var psum = Array(repeating: 0, count: n+1) for i in 1...n { psum[i]..

○ 다이나믹 프로그래밍, 누적 합 Silver1 백준 11660번 구간 합 구하기 5 시간은 한시간 넘게 걸린거같은데 한번만에 통과함 ㅎㅎ 어떻게 계산해야될지 방법을 찾기만 하면 구현이 어렵진 않았음. 생각해내는건 쉽지않았음 ㅎㅎ (뻔한 말인가,,?) 누적 합과 DP의 경계가 살짝 모호하지만 행렬을 사용하니깐 공간에 값을 저장해나가는 게 누적합을 사용한 DP에 좀 더 가까운 것 같다는 느낌? //85696KB 584ms let nm = readLine()!.split(separator: " ").compactMap { Int($0) } let n = nm[0] let m = nm[1] var matrix: [[Int]] = [Array(repeating: 0, count: n+1)] for _ in 0..