ios Note

https://www.acmicpc.net/problem/1715 정렬되어 있는 카드 묶음을 모두 합치는 최소 비교 횟수를 구하는 문제카드의 개수가 적은 묶음부터 2개씩 합치면 최소한의 비교로 구할 수 있음 예를들어10, 20, 40개의 카드를 가진 묶음이 있다면10장과 20장을 합친 뒤, 합친 30장 묶음과 40장 묶음을 합치면 100번의 비교가 필요함(10 + 20) + (30 + 40) 그럼 카드의 개수가 작은 순서대로 정렬 후 두 묶음의 개수 합과 다음 묶음 개수의 합을 하면 될까?50, 60, 70, 80 으로 예를 들면 순서대로 두 묶음 씩 합칠 때(50 + 60) = 110(70 + 110) = 180(80 + 180) = 260→ 총 550번의 비교가 필요함 하지만, 정답은?(50 + 60..

https://www.acmicpc.net/problem/1541 +, -, 양수로 이루어진 식에서 괄호를 이용하여 최소 값을 만드는 문제‘-’ 부호가 나오면, 다음 ‘-’ 부호 앞까지 괄호로 묶어주면 빼는 수의 값이 최대가 되어 가장 작은 값이 될 것 같음 예를 들어10 + 20 - 30 + 10 + 20 - 30 + 10→ 10 + 20 - ( 30 + 10 + 20) - (30 + 10)→ 30 - 60 - 40 = -70 → 입력값의 ‘-’ 부호 기준으로 배열을 나눔위 예시를 이용하면,input: “10 + 20 - 30 + 10 + 20 - 30 + 10”arr = [”10+20”, “30+10+20”, “30+10”] 첫 번째 인덱스 값에서 나머지 모든 배열의 값을 빼주면 정답→ arr[0] ..

https://www.acmicpc.net/problem/1931 진행할 수 있는 회의의 최대 개수를 구하는 문제회의가 끝나는 시간을 기준으로 정렬하고 회의가 끝나고 바로 진행할 수 있는 회의를 선택하면 최대한 많은 회의를 진행할 수 있을 거 같다→ 그리디 알고리즘 이용 첫 번째 시도let N = Int(readLine()!)! // 회의 수var arr = [(start: Int, end: Int)]() // 회의 시작 시간, 끝나는 시간 배열for _ in 0..= startTime { // 다음 회의 시작 시간이 이전 회의가 끝난 시간보다 이후라면 선택 answer += 1 startTime = end // 회의를 추가했으니, 다음 회의 시작 시간은 현재 회의 끝난 시간 이..

https://www.acmicpc.net/problem/11047   여러 단위의 동전을 최소한 사용하여 목표 값을 만드는 문제큰 단위의 동전부터 차례로 최대한 많이 사용하면 최소한의 동전으로 목표값을 만들 수 있음→ 그리디 알고리즘첫 번째 시도let NK = readLine()!.split(separator: " ").map{Int($0)!}let (N, K) = (NK[0], NK[1]) // N: 동전의 종류 개수, K: 목표 값var coins = [Int]() // 동전 단위 배열var target = K // 남은 값var answer = 0 // 필요한 동전 개수for _ in 0..

첫 번째 방법: Dictionary 사용x 좌표를 기준으로 dictionary 형태로 만들고 x 좌표에 따른 y 값을 value 배열로 받음x 값 기준으로 정렬을 한 후 딕셔너리를 돌면서 작은 x값부터 y값 배열을 정렬하고 순서대로 출력let N = Int(readLine()!)!var dic = [Int: [Int]]() // for _ in 0..→ 80%에서 시간 초과key에 대한 정렬과 value에 대한 정렬을 나눠서 한 점이 시간 초과의 원인인 것 같다 두 번째 방법: 2차원 배열 사용[x, y] 형태로 2차원 배열에 저장하고 배열을 돌면서 x 값이 같으면 y 값에 따라 정렬, x값이 다르면 x값에 따라 정렬하는 방식 사용let N = Int(readLine()!)!var arr = [[Int]..

https://www.acmicpc.net/problem/10972 첫 번째 방법: 재귀 함수 이용 (String 타입 배열)let N = Int(readLine()!)!let input = readLine()!.split(separator: " ").map{String($0)}var visited = Array(repeating: false, count: N + 1) // 숫자의 방문 여부 저장var flag = false // 현재 입력 순열을 찾았는지 여부var isLast = false // 마지막 순열인지 여부 (마지막 순열까지 입력 순열을 못찾았으면 "-1" 출력을 위함)func recur(choose: [String]) { if choose.count == N { if fl..

https://www.acmicpc.net/problem/1010   첫 번째 방법: 팩토리얼 이용// 팩토리얼 구하기func factorial(_ n: Int) -> Int { if n == 0 || n == 1 { return 1} return n * factorial(n - 1)}let T = Int(readLine()!)!for _ in 0.. C(M, N) == M! / N! * (M - N)! let facM = factorial(M) let facN = factorial(N) print(facM / (facN * factorial(M - N)))}→ Thread 1: Swift runtime failure: arithmetic overflow : 오버 플로우..

https://www.acmicpc.net/problem/9613   각 테스트케이스마다 가능한 모든 쌍의 GCD의 합을 출력해야 한다면GCD는 유클리드 알고리즘을 사용각 케이스마다 자신을 제외한 모든 케이스와의 GCD를 구해야 함 → 이중 for문 사용i번째 배열의 값을 기준으로 이후 인덱스 값과의 GCD를 더함i는 테스트케이스의 수를 나타내는 0번 인덱스를 제외한, 1번 인덱스부터 전체 테스트케이스 - 1까지 (마지막 값은 비교할 수 없기 때문)j는 i+1 값부터 마지막까지로 할당하여 순차적으로 비교함 // 유클리드 호제법 - 최대 공약수 구하기func gcd(_ a: Int, b: Int) -> Int { return a % b == 0 ? b : gcd(b, b: a % b)}let t = ..

https://www.acmicpc.net/problem/17087​ 수빈이의 위치 X일 때 1초에 D씩 이동해서 모든 동생을 찾아야 된다수빈이의 위치에서 동생들의 위치(A1, A2 … An)의 차는 수빈이와 동생들 사이의 거리를 뜻함따라서, 수빈이가 이동해야 하는 거리의 최대 공약수를 구하는 문제! 모든 동생들과의 거리에서 최대 공약수를 구해야 하기 때문에 재귀함수를 사용함 let NS = readLine()!.split(separator: " ").map{Int($0)!}let (N, S) = (NS[0], NS[1]) // N: 동생 수, S: 수빈 위치var A = readLine()!.split(separator: " ").map{Int($0)!} // 동생들 위치A = A.map{abs($0..

www.acmicpc.net​ 입력 N보다 큰 소수이면서, 팰린드롬인 가장 작은 수를 구해야 하기 때문에,에라토스테네스의 체 알고리즘을 사용하여 최대 값인 1,000,000까지의 소수를 판별 후N 보다 큰 수를 돌면서 소수인지 확인 및 팰린드롬인 수인지 확인해야 함 첫 번째 시도팰린드롬인 수 판별을 투 포인터를 이용하여 구현 → 테스트 케이스는 통과하지만, “틀렸습니다”let maxNum = 1000000var isPrime = Array(repeating: true, count: maxNum + 1)isPrime[0] = falseisPrime[1] = falsefor i in 2...maxNum { if !isPrime[i] { continue } for j in stride(from: i..