CodingTest 7

[그리디] 1이 될때까지

[내가 생각한 코드]n, k = map(int, input().split())count = 0while True: if n%k: count+=1 n=n-1 if n==1: break else: count += 1 n = n/k if n==1: break print(count)이 문제에 대한 해결방법은 N에 대하여 '최대한 많이 나누기'를 수행하면 된다. 나누는 것이 하상 더 숫자를 빠르게 줄이기 때문이다.[단순하게 푸는 답안]#1이 될때까지(책 풀이)n, k = map(int, input().split())result = 0#N이 K..

[그리디] 큰수의 법칙

#큰수의 법칙n, m, k = map(int, input().split())data = list(map(int, input().split()))data.sort()first = data[n-1]second = data[n-2]result=0while True: for i in range(k): if m==0: break result += first m -= 1 if m ==0: break result += second m -= 1print(result)# N, M ,K를 공백으로 구분하여 입력받기n, m, k = map(int, input().split())# N개의 수를 공백으로 구분하여 입력받기data = li..

[그리디]그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분하다. 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

백준 1271번문제

[내가 작성한 정답]package BaekJoon;import java.util.Scanner;public class baek1721 { public static void main (String args[]) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int quotient, remainder; quotient = n / m; remainder = n % m; System.out.println(quotient); System.out.println(remainder); }} [문제점]1. 이 문제에서는 큰 정수, 즉 int형이나 long형의 범위를 초과하는 숫자..