Outgoing Introvert

○ 이분탐색 4단계 백준 2805 나무 자르기 문제 나무 M미터 필요. 목재 절단기 높이 h 지정. 한 줄에 연속해있는 나무 모두 절단. 20 15 10 17 -> h: 15 -> 15 15 10 15 -> 길이 5, 2 인 나무 들고 집에 갈 것 (총 7 미터) h : 0 ~ 양의 정수. 나무를 필요한 만큼만 집으로 가져갈 것. 적어도 M 미터의 나무를 집에 가져가기 위해 절단기 설정 높이 최댓값 구하기 입력 첫줄 - 나무의 수 N, 가져가려는 나무 길이 M. 1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000 둘째줄 - 나무의 높이. M Int { var s = 0 var e = trees.max()! var result = 0 while s < e { let mid = (s +..

△ 이분탐색 3단계 백준 1654 랜선 자르기 문제 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오..

해시 ○ 이분탐색 X 백준 10816 숫자 카드 2 이분 탐색 예제로 나와서 풀었는데, 해시로 풀어버렸다.. 해시로 푸는게 훨씬 간단하고 편한거같은데..? 이분탐색은 도대체 어떻게... 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다..

백준 1920 수 찾기 binary search 이분탐색 1단계 문제 : N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 : 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000) 다음 줄에는 N개의 정수 A[1], A[2], …, A[N] 다음 줄에는 M(1 ≤ M ≤ 100,000) 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 : M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 1차 시도 시간초과 실패 .contains 의 시간복잡도는 O(n)으로 다음과 같이 for문 안에 사용..

백준 2231번 브루트 포스 예제 2단계 1차시도 : 69100KB / 296ms 아무런 조건 없이 그냥 1부터 다 검사하는 걸로 해도 시간은 오래걸리지만 통과는 되더라. func minGenerator(_ n: Int) -> Int { for i in 1...n { var sum = i for j in String(i) { sum += Int(String(j))! } if sum == n { return i } } return 0 } 2차시도 : 69100KB / 8ms 1부터 다 체크하는 건 비효율적이기 때문에 조건을 달아주었다. 입력 숫자가 256일 경우, 각 자리 수의 최대 합은 2 + 9 + 9 = 20 이 된다고 생각했다. 그러면 256의 생성자는 최소 256 - 20 = 236 이상이 될 수..

백준 2798번 브루트 포스 예제 1단계 메모리 69104KB / 시간 8ms let input = readLine()!.split(separator: " ").map{ Int($0)! } let n = input[0], m = input[1] let cards = readLine()!.split(separator: " ").map{ Int($0)! } print(blackJack(n,m,cards)) func blackJack(_ n: Int, _ m: Int, _ cards: [Int]) -> Int{ var maxSum = 0 for i in 0..

보호되어 있는 글입니다.

백준 10870번 재귀함수 기초 예제 피보나치 수 let input = Int(readLine()!)! print(Fibonacci(input)) //재귀함수 func Fibonacci(_ n: Int) -> Int { if n == 0 { return 0 } else if n == 1 { return 1 } else { return Fibonacci(n - 1) + Fibonacci(n - 2) } } //재귀함수 축약 func Fibonacci(_ n: Int) -> Int { return n < 2 ? n : Fibonacci(n-1) + Fibonacci(n-2) } 재귀함수를 사용하면 코드가 직관적이고 가독성이 좋다. ternery operator를 사용하여 한 줄로 축약할 수도 있다. 반복문으..

백준 10872번 재귀함수 기초 예제 팩토리얼 //반복문 let input = Int(readLine()!)! print(factorial(input)) func factorial(_ n: Int) -> Int { var result = 1 if n > 1 { for i in 2...n { result *= i } } return result } //재귀함수 let input = Int(readLine()!)! print(factorial(input)) func factorial(_ n: Int) -> Int { if n == 0 { return 1 } return n * factorial(n - 1) } //꼬리재귀 let input = Int(readLine()!)! print(factorial(in..

Swift로 알고리즘 입문! 확실히 알고리즘같은 걸 공부하기엔 파이썬이 훨씬 편했던 것 같다.. 자주 사용하는 함수들이나 프로그램 자체가 Swift는 프론트 개발에 맞춰있어서 알고리즘 문제를 풀기엔 간단한 문제라도 아주 낯선느낌..? ㅎㅎㅎ 첫번째 난관은 입력 받아오기! 플레이그라운드에서는 입력 받아오는 게 불가하고, 새로운 Xcode 프로젝트를 생성할 때, macOS 의 Command Line Tool 을 사용해야만 console 창에 값을 입력할 수 있다고 한다. 백준 1000번 문제 : 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 : 첫째 줄에 A와 B가 주어진다. (0 < A, B < 10) 출력 : 첫째 줄에 A+B를 출력한다. readLine()으로 입력을..