목록PS (4)

Get Up & Code, MacKin Talk

[백준]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 문항이라고 생각했지만, 문제의 분류표를 살펴보고 난 후, 백..
IOS/알고리즘 문제 풀이 2021. 10. 19. 01:31
[백준]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..
IOS/알고리즘 문제 풀이 2021. 10. 6. 22:00
[백준]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)..
IOS/알고리즘 문제 풀이 2021. 10. 6. 21:34
알고리즘 문제 풀이 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; ..
IOS/알고리즘 문제 풀이 2021. 1. 15. 17:16
이전 Prev 1 Next 다음