yunwon's tech blog

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. # 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 이전 포스팅에서 다이나믹 프로그래밍을 사용해서 해결했는데, 스터디를 진행하면서 브루트 포스(재귀)로 푸는 방법을 습득하게 되어서 그 방식에 대해서도 따로 정리해두려 한..

문제 비어있는 공집합 S가 주어졌을 떄, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1, 2, ..., 20} 으로 바꾼다. empty: S를 공집합으로 바꾼다. # 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. # 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 이 문제 또한 "다이나믹 프로그래밍" 기법을 사용한다. 다이나믹 프로그래밍 문제는 다음과 같은 문제 해결 루틴을 적용하면 된다. 테이블 정의하기 점화식 찾기 초기값 정..

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) # 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 이 문제는 "다이나믹 프로그래밍" 기법을 사용하여 해결할 수 있다. 다이나믹 프로그래밍이란, 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 것으로 쉽게 말해 답을 재활용하는 기법이다. 성립되기 위한 두가지 조건은 다음과 같다. Overlapping Subproblem 큰 문제를 작은 문제로 나누었을 때, 작은 단위로 나누어진 문제들은 같은 정답의 형태가 되어야 한다. Optimal Substruction 작은 부분에서 구한 최적의 답..

문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. # 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 문제에서 말하는 GCD란? Greatest Common Divisor, 즉 최대공약수를 말한다. 그리고 여기서 새롭게 알게 된 알고리즘 "유클리드 호제법" 에 대해 소개하려 한다. 유클리드 호제법은, 주어진 두 수 사이에 존재하는 최대공약수 (GCD)..

문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 N이 주어진다. (0 = 5) { cnt += n / 5; n /= 5; } return cnt; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println(countZero(Integer.parseInt(br.readLine()))); } } © 참고 https://www.acmicpc.net/problem/1676 https://st-lab.tistory.com/1..

문제 오늘은 2007년 1월 1일 월요일이다. 그렇다면 2007년 x월 y일은 무슨 요일일까? 이를 알아내는 프로그램을 작성하시오. # 입력 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. # 출력 첫째 줄에 x월 y일이 무슨 요일인지에 따라 SUN, MON, TUE, WED, THU, FRI, SAT 중 하나를 출력한다. 풀이 import java.util.*; public class NewClass { public static void main(String[] args){ Scanner sc = new Scanner..

문제 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오. # 입력 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. # 출력 입력으로 주어진 숫자 N개의 합을 출력한다. 풀이 import java.util.*; public class NewClass{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int sum = 0; int count = sc.nextInt(); String num = sc.next(); if(num.length() == count) { for(int i = 0;i < count;i++) { sum ..

문제 입력 받은 대로 출력하는 프로그램을 작성하시오. # 입력 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시작하지 않고, 공백으로 끝나지 않는다. # 출력 입력받은 그대로 출력한다. 풀이 import java.util.*; public class NewClass{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); StringBuffer buffer = new StringBuffer(); while(sc.hasNextLine()) { buffer.append(sc...

문제 넥슨의 입사 문제였다는 "Self Number" 찾기를 해 보자. 문제는 다음과 같다. 어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101 이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1, 3, 5, 7, 9, 20, 31 은 셀프 넘버 들이다. 1 이상이고 5000 보..