김경록의 앱 개발 여정

풀이 아이디어좌표압축 문제입니다.처음 풀어 보는 유형이지만, 간략히 요약해 보면 결국 가장 작은 값을 0으로 잡고1씩 증가시키며 크기만 나타낼 수 있도록 하는 문제입니다. 풀이let n = Int(readLine()!)!let input = readLine()!.split(separator: " ").map { Int($0)! }let sortedSet = Array(Set(input)).sorted()var dic = [Int: Int]()for i in 0..

풀이 아이디어이분탐색 + 구현 문제입니다.이분탐색만으로 어떻게 해결해야하는지 애를 먹었는데조명으로 커버가 되는지 확인하는 작업을 거치는게 오히려 포인트인 문제였습니다. 자세한 설명은 주석 참고해주세요 풀이import Foundationlet n = Int(readLine()!)!let m = Int(readLine()!)!let input = readLine()!.split(separator: " ").map { Int($0)! }func isCoverd(with height: Int) -> Bool { var lastCovered = 0 for i in input { if i - height > lastCovered { return false } ..

풀이 아이디어이분탐색 문제입니다.이분탐색에선 최소 최댓값의 기준을 잡는 것이 중요합니다.해당 문제에서 1번 조건으로 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다 했으므로최댓값은 input의 max값이 됩니다. 나머지는 일반적인 이분탐색이고, 핵심부분에 주석으로 설명을 덧붙였습니다풀이import Foundationlet n = Int(readLine()!)!var input = readLine()!.split(separator: " ").map { Int($0)! }let total = Int(readLine()!)!var left = 0var right = input.max()!var result = 0while left

풀이 아이디어이분 탐색 문제입니다. 이분 탐색은 left와 right 의 중간값을 이용해 빠르게 값을 대치하며 찾는 방식입니다. 주의할점 톱날의 높이가 나무의 높이보다 높아져도 음수가 되진않는다left는 0 부터 시작 right는 나무 중 가장 큰 값이다 ( 나무를 가져가지 못하는 경우는 없으니, 전체 다 가져가야하거나 목표치가 0 일수 있음) 풀이import Foundationlet nm = readLine()!.split(separator: " ").map { Int($0)! }let (n, m) = (nm[0], nm[1])let trees = readLine()!.split(separator: " ").map { Int($0)! }var left = 0var right = trees.max()!v..

풀이 아이디어dp 문제입니다.점화식을 구해야하는데,마지막 상자가 어떤것일때 몇개인지 를 구하면 됩니다 dp[i]: i번째 상자를 마지막으로 포함할 때 넣을 수 있는 상자의 최대 개수예를 들어, 상자 크기가 1, 2, 3, 5, 4라고 할 때:dp[0] = 1 (상자 1 하나만 포함)dp[1] = 2 (상자 1, 2 포함)dp[2] = 3 (상자 1, 2, 3 포함)dp[3] = 4 (상자 1, 2, 3, 5 포함)dp[4] = 3 (상자 1, 2, 4 포함)자세한 과정은 주석과 추가 설명을 덧붙이겠습니다.풀이import Foundationlet n = Int(readLine()!)!let input = readLine()!.split(separator: " ").map { Int($0)! }// dp 배..

문제 요점첫번째 이동할땐 가격에 상관없이 다음 지역까지 갈 만큼의 주유를 진행해야한다도착한 후엔 주유 할 필요가 없으므로 마지막 주유소의 가격은 고려 대상이 아니다.서브 태스크첫 풀이let n = Int(readLine()!)!let length = readLine()!.split(separator: " ").map{Int($0)!}let oilPice = readLine()!.split(separator: " ").map{Int($0)!}var totalLength = length.reduce(0, +)var result = 0// 처음엔 가격에 상관없이 넣어야함result += oilPice[0] * length[0]totalLength -= length[0]var minimumOilPrice = o..

풀이 아이디어백트래킹을 이용하는 문제입니다.resultArr의 길이에 조건을 두어 불필요한 탐색을 방지합니다.한 경로를 탐색한 후 removeLast()를 호출하여 상태를 복구하고 다른 경로를 탐색합니다.풀이import Foundationlet input = readLine()!.split(separator: " ").map{ Int($0)! }let n = input[0]let m = input[1]var resultArr: [Int] = []func dfs(_ start: Int) { if resultArr.count == m { print(resultArr.map { String($0) }.joined(separator: " ")) return } // ou..

저도 백트래킹은 처음이라 백트래킹의 개념에 대해 먼저 짚어보면 다음과 같습니다.백트래킹의 핵심DFS(깊이 우선 탐색)를 기반으로 합니다.탐색 중, 조건에 맞지 않는 경우를 가지치기(pruning)하여 탐색 범위를 줄입니다.탐색이 끝난 후, 상태를 이전으로 복원(backtracking)합니다.풀이 아이디어는 다음과 같습니다.DFS를 이용해 깊이 우선으로 탐색:M 길이에 도달할 때까지 가능한 숫자를 하나씩 추가.가지치기:이미 선택한 숫자는 다시 선택하지 않음.상태 복원:재귀 호출 후, 선택했던 숫자를 제거하고 이전 상태로 되돌아감.풀이 코드는 아래와 같습니다.풀이let nm = readLine()!.split(separator: " ").map { Int($0)! }let (n, m) = (nm[0], nm..

풀이 아이디어만 생각해낸다면 구현자체는 크게 어렵지 않은 문제입니다.풀이 아이디어입력값들을 정렬한다정렬된 입력값들을 지그재그로 배치해준다(맨앞, 맨뒤로 시작하여 안쪽으로 차곡차곡)가장 큰 차이값을 구한다자세한 풀이는 코드의 주석 참고풀이 코드import Foundationlet testCase = Int(readLine()!)!for _ in 0..

유쾌한 제목의 골드 문제입니다.저는 이 문제를 보고 일반적인 구현 문제 생각했습니다.매 조건에 따라 선을 만들어주면 되겠구나 했거든요그런데 '스위핑'이라는 알고리즘을 사용한다고 합니다.풀고 보니 이런 걸 스위핑이라고 하는구나 한 문제였습니다.문제를 푼 후 스위핑이 뭔지 찾아봤는데 아래 블로그에서 그림과 함께 아주 친절하게 설명해 주시더라고요 참고하시면 좋을 것 같습니다.https://byeo.tistory.com/entry/%EC%8A%A4%EC%9C%84%ED%95%91-Sweeping 스위핑 (Sweeping)목차 개요 설명 일반화 코드 개요 스위핑 (Sweeping)은 "쓸다" 를 의미합니다. 스위핑 알고리즘 이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이라고 보시..