- 이진 탐색을 공부하며, 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.08.31
- 탐색 알고리즘 1. 탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 검색 엔진은 탐색 알고리즘을 사용하고 있는 거죠. 2. 탐색의 종류 1) 선형 탐색(리니어 서치) - O(N) 한쪽 끝에서 다른 한쪽 끝으로 순서대로 하나씩 확인해 나가는 것. 아무 생각도 요령도 필요없이 그냥 하나씩 확인해가면 된다. 대표적인 방법으론 반복문을 사용하는 것이다. 찾는 대상이 탐색을 시작하는 쪽에 가까우면 짧은 시간에 탐색할 수 있지만 반대인 경우 혹은 데이터가 없는 경우는 비효율적이다. 단순, 구현이 쉽지만 효율은 낮다. 2) 이진 탐색(바이너리 서치) - O(logN) 보장 이진탐색은 데이터가 미리 오름차순, 내림차순으로 정렬되어 있는 경우에 사용할 수 있다. 특정 데이터를 찾기 위해서 범위를 반으로 좁혀서.. 2021.08.30
- 그리디 알고리즘 그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 이 알고리즘도 어떤 특정 코드가 있는게 아니다. 문제 해결 방식 중 하나에 불과. 사실 가장 간단한 문제 해결 방식인데, '현재 상황에서 지금 당장 좋은 것만 먼저 고르는 방법'이다. 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는지를 테스트하는 것이다. 그리디 알고리즘의 적용 그리디 알고리즘에서는 정당성 분석이 중요하다. 즉, 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해에 도달할 수 있는지를 검토해야 한다. 물론 그리디 알고리즘 문제는 일반적인 상황에서 최적의 해를 보장하지는 않는다. 하지만 코테에서는 탐욕법으로 얻은 해가 최적의 해가 되도록 출제한다. 즉, 단순히 가장 좋아보이는 것을 반복적으로 .. 2021.08.22
- 다이나믹 프로그래밍 다이나믹 프로그래밍(동적 계획법)이란? 이미 계산된 결과(작은 문제)를 별도의 메모리 영역에 저장하고 필요할 때 꺼내 사용함으로 다시 계산하지 않도록 해서 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 따라서 완전 탐색을 할 때 일어나는 비효율성을 완화할 수 있다. 탑다운, 바텀업 두 가지 방식이 있다. 주로 바텀업. 다른 알고리즘처럼 어떤 특정한 코드가 있는게 아니다. 이런 문제해결 방식이 있다는 것을 익히고 자주 사용해보는게 좋다. 다이나믹 프로그래밍 조건? 1. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답이 모여서 큰 문제를 해결 할 수 있을 때 사용한다. 2. 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결해야 한다. 3. 이 두 가지 조건을 모두 충족해야.. 2021.08.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.08.19