Swift Algorithm4 이진 탐색을 공부하며, 1. 재귀를 이용한 이진 탐색 func binarySearch(target: Int, start: inout Int, end: inout Int) -> Int? { if start > end { return nil } let mid = (start+end)/2 if target == A[mid] { return mid } else if target > A[mid] { start = mid + 1 return binarySearch(target: target, start: &start, end: &end) } else if target < A[mid] { end = mid - 1 return binarySearch(target: target, start: &start, end: &end) } return .. 2021. 8. 31. 그리디 알고리즘 그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 이 알고리즘도 어떤 특정 코드가 있는게 아니다. 문제 해결 방식 중 하나에 불과. 사실 가장 간단한 문제 해결 방식인데, '현재 상황에서 지금 당장 좋은 것만 먼저 고르는 방법'이다. 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는지를 테스트하는 것이다. 그리디 알고리즘의 적용 그리디 알고리즘에서는 정당성 분석이 중요하다. 즉, 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해에 도달할 수 있는지를 검토해야 한다. 물론 그리디 알고리즘 문제는 일반적인 상황에서 최적의 해를 보장하지는 않는다. 하지만 코테에서는 탐욕법으로 얻은 해가 최적의 해가 되도록 출제한다. 즉, 단순히 가장 좋아보이는 것을 반복적으로 .. 2021. 8. 22. 다이나믹 프로그래밍 다이나믹 프로그래밍(동적 계획법)이란? 이미 계산된 결과(작은 문제)를 별도의 메모리 영역에 저장하고 필요할 때 꺼내 사용함으로 다시 계산하지 않도록 해서 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 따라서 완전 탐색을 할 때 일어나는 비효율성을 완화할 수 있다. 탑다운, 바텀업 두 가지 방식이 있다. 주로 바텀업. 다른 알고리즘처럼 어떤 특정한 코드가 있는게 아니다. 이런 문제해결 방식이 있다는 것을 익히고 자주 사용해보는게 좋다. 다이나믹 프로그래밍 조건? 1. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답이 모여서 큰 문제를 해결 할 수 있을 때 사용한다. 2. 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결해야 한다. 3. 이 두 가지 조건을 모두 충족해야.. 2021. 8. 22. 소수 판별 알고리즘 기본 : 약수 성질 이용, 제곱근사용 -> Foundation 필요 import Foundation func isPrime(_ num: Int) -> Bool { if num < 4 { return num == 1 ? false : true } for i in 2...Int(sqrt(Double(num))) { if num % i == 0 { return false } } return true } 에라토스테네스의 체 + 골드바흐 import Foundation let T = Int(readLine()!)! // 에라토스테네스의 체, n이 4이상이라는 조건이 있어서 n < 4 예외처리를 제외 // 조건을 잘 확인하고 관련한 조건을 꼭 충족시켜줘야 한다. func seiveEratos(_ n: Int, _ .. 2021. 8. 19. 이전 1 다음
