IOS/알고리즘 문제 풀이 (11) 썸네일형 리스트형 [백준]1931_회의실 배정 문항번호: 1931번 회의실 배정 tags: problem solving 1. 문제 분석 목표: 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기 2. 풀이 계획 입력 제한 : N(1 ≤ N ≤ 100,000) 시간 제한 : 2초 생각한 방향 최대한 회의를 많이 하기 위해서는 가급적 빠른 시간에 끝나는 회의를 선택하는 방법을 선택해야한다. 빠른 시간에 끝나는 회의임을 찾기 위한 정렬 과정이 요구된다. -> sort() 메서드 사용 추가로 다음에 시작할 수 있는 회의는 현재의 종료시간 이후이거나 같은 값을 가져야 한다. -> if 조건문 3. 계획 검증 시간 복잡도 예상 : 최대 100,000개의 데이터가 들어온다고 가정했을 때, Swift에서 제공하는 sort 함수의 시간복잡.. [백준]15652 N과 M(4) 문항번호: 15652 N과 M(4) 1. 문제 분석 1 ~ N의 자연수 중 M개를 고른 수열 같은 수 여러번 고르기 가능. 고른 수열은 비 내림차순이어야 함. A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK 2. 풀이 계획 1부터 N까지 가면서 출력을 하게 된다. Back-tracking : 불필요한 탐색을 하지 않고, 이전 단계로 돌아와 다른 후보해를 탐색해 나가는 방법 이미 탐색한 값보다 작은 값의 경우, 다음 input으로 들어올 수 없으므로, 반복문 안에서 더 낮은 숫자의 반복문이 돌지 않도록 설정해주어야 하겠다. -> for 문의 시작점을 현재의 current Value부터 시작하도록 설정해서 위 조건을 만족 시킴. 사실 전형적인 DFS 문항이라고 생각했지만, 문제의 분류표를 살펴보고 난 후, 백.. [백준]1463_1로 만들기 문항번호: 1로 만들기 1. 문제 분석 정수 X가 사용할 수 있는 연산 X%3 == 0 -> X = X/3 X%2 == 0 -> X = X/2 X = X-1 2. 풀이 계획 입력 제한: 1 [백준]1966_프린터큐 목차 문항 분석 Code 결과 및 분석 문항 분석 입력 제한 큐 자료구조를 활용해야 하는 문제 Swift에서 Array를 활용해 큐를 간단하게 구현하게 될 경우 removeFirst() method : O(N) append() method: O(1) 순서에 맞는 자료 값에 대한 위치 계산을 계속 진행해야 하고, 반복문 안에서 점검을 진행해줘야 한다. Code import Foundation let testcase = Int(readLine()!)! var list = [(Int, Int)]() for _ in 0.. [백준]11047_동전0 문항 분석 입력 제한 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 가치가 더 큰 동전으로 가치가 더 작은 동전보다 더 적은 수를 활용해 합을 만들 수 있다. 가치가 큰 동전을 매번 하나씩 반복문을 통해 뺴는 방법을 사용하면 그만큼 시간적 소요가 크므로 나누기 연산과 나머지 연산을 활용해 접근하면 될 것 같다. Code import Foundation let input = readLine()!.split(separator: " ").map{ Int(String($0)) } var coins = [Int]() let n = input[0]! var k = input.. [백준]18830_좌표압축 1. 문제 분석 Xi의 값이 Xj보다 큰 좌표의 개수를 찾아야 한다.(좌표 압축) Xi를 좌표 압축한 결과 = Xi' 입력: X1, X2, ..., XN 출력: X1', X2', ..., XN' 2. 풀이 계획 입력 제한 1 ≤ N ≤ 1,000,000 -10^9 ≤ Xi ≤ 10^9 N^2으로 검증하는 순간 시간 초과는 분명. 3. 계획 검증 전체 반복문 n 개별 반복문 p 각 명령어 실행 시간 1 O(np) 4. 소스 코드 import Foundation var set = Set() var dic = [Int: Int]() _ = Int(readLine()!)! var input = readLine()!.split(separator: " ").map { Int(String($0))! } // O(N).. [백준]5430_AC 1. 문제 분석 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있음. R은 뒤집는 함수, D는 첫 번째 숫자를 버리는 함수 Error: 배열이 비어있는데 D를 사용한 경우 예제 입력: 1) Testcase 수 2) p : 수행할 함수 (String) 3) n : 배열에 들어있는 수 개수 4) [xi,...] : 수가 들어가 있는 배열 제한 조건 : Sum(P) + n tail } } import Foundation final class FileIO { private let buffer:[UInt8] private var index: Int = 0 init(fileHandle: FileHandle = FileHandle.standardInput) { buffer = Array(try! fileHand.. 알고리즘 문제 풀이 53번 : K진수 출력(stack) 목차 문항 분석 Code 결과 및 분석 문항 분석 10진수 N이 입력이 되었을 때, 이를 K진수로 변환해 출력하도록 하는 프로그램을 작성해야 한다. 접근 방법 : N을 입력 받았다고 했을 때, K로 나눈 나머지를 차례로 기록해 역순으로 출력하면 된다. N%K 연산을 진행할 때마다 값을 스택 구조를 활용해 차례대로 저장한 후, top부터 역순으로 출력하면 된다. 이를 저장하기 위해 입력 범위를 담을 수 있는 충분한 크기를 가진 스택을 구성했다. 스택 구조를 간단히 도식화한 그림은 다음과 같다. Code // // 53_k진수 출력.cpp // Algorithm // // Created by WANKI KIM on 2021/01/14. // #include using namespace std; .. 이전 1 2 다음
