코후닝

알고리즘 분류: 이분 탐색, 매개 변수 탐색 문제 링크: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 【 풀이 】 자를 수 있는 나무의 마지노선 길이를 구하는 문제이다. 이분 탐색으로 구하면 쉽게 해결할 수 있다. start(최소 길이, 즉 0), end(최대 길이, 즉 배열에서의 최댓값) 두 변수를 이용해서 mid(중간값)를 설정하고 배열 요소에서 mid를 뺀 값을 모두 더한 값을 저장한다. 모두 더..

알고리즘 분류: 수학 문제 링크: https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 【 풀이 】 N! 의 뒤에서부터 처음 0이 아닌 수가 나올 때까지 0의 개수를 구하는 문제이다. 딱 보자마자 N! 을 구하여 저장한 후, 문자열로 변환시킨 후 맨뒤에서부터 0의 개수를 세는 알고리즘을 생각했다.그러나 N이 20 언저리를 넘어가는 순간부터 답이 이상해진다. 이는 N의 범위가 500까지이므로 파이썬이 아닌 이상 가장 큰 자료형으로도 N! 을 담을 수 없기 때문이다. (저장한 값이 중간에 잘려버림) 따라서 N! 을 소인수 분해하여 해결해야..

알고리즘 분류: 구현 문제 링크: https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 【 풀이 】 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 저장되어 있는 배열(세트)을 이용해 몇 개의 세트로 주어진 방 번호를 만들 수 있는지를 구하는 문제이다. 우선 각 숫자들의 등장 횟수를 세기 위한 배열을 하나 선언한다.그 후 각 숫자들을 문자로 저장, 입력받은 숫자를 반복문을 통해 검사하며 각 숫자의 등장 횟수를 센다.그런 다음 그 배열에서 최댓값을 출력해주면 끝이다. 다만 6과 9는 각 수가 세트에 존재하지 않을 때(이미 썼을 때) 바꿔 쓸 ..

알고리즘 분류: 수학, 구현, 정수론 문제 링크: https://www.acmicpc.net/problem/9506 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 【 풀이 】 수를 하나 입력받고, 그 수의 약수들의 합이 입력 받은 수와 일치하면 그 합을 출력하는 문제이다. 숫자 n을 입력받고, 1부터 n까지 숫자를 돌려가면서 n과 나누어 떨어지는 수가 있다면 배열에 저장한다. 그 후 배열에 저장된 수의 합을 구하고, n과 같은지 다른지 조건문으로 예제와 같이 출력하면 된다. 【 코드 】 #includ..

알고리즘 분류: 수학, 정수론, 유클리드 호제법 문제 링크: https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 【 풀이 】 유클리드 호제법을 재귀함수로 구현하여 최대공약수를 구한 다음 최대공약수를 활용하여 최소공배수를 구하면 되는 문제이다. 문제에서 수 형식을 long long int (C/C++) 를 사용하라고 하였으니, 변수든 함수든 모두 long long int로 구..

알고리즘 분류: 구현, 문자열 문제 링크: https://www.acmicpc.net/problem/11718 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net 【 풀이 】 문자열을 입력받고 입력받은 대로 출력하면 되는 문제이다. 개행까지 포함한 문자열을 한 번에 출력해도 되지만 문제에서 그러한 조건은 없으므로 단순하게 한줄씩 입력받고 한 줄씩 출력하면 된다. string 클래스와 getline을 이용하여 공백을 포함하여 입력받고 그대로 출력한 다음 비어있는 문자열을 받게 되면(개행만 하게 되면..