IT 기획의 길

문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 이 문제는 쉽지 않은 문제였다 일단 계단수란 인접한 모든 자리수의 차이가 1인 수를 말한다 길이가 1인 계단수는 1,2,3,4,5,6,7,8,9 총 9개이다 길이가 2인 계단수는 10,12,21,23,32,34,43,45,54,56,65,67..

문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카..

문제 정수 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의 합으로 나타내는 방법의 수를 출력한다. dp문제의 점화식을 어떻게 세우는지 감이 잡히게 된 문제였다. dp문제에서 가장 중요한것은 현재상태의 직전상태를 생각해서 점화식을 만든다는것이다. 이게 무슨말이냐면 위 문제는..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 드디어 DP part로 넘어왔다 2학년 2학기 겨울방학때 if문 for문 배열 문자열 조금 끄적인 뒤로 3학년 1학기는 열심히 학업에 집중하였고 3학년 1학기 여름방학에는 토익에 자격증공부에 코딩을 제대로 할 시간이 없었다 (물론 핑계인것은 안다..) 3학년 2학기는 학점..

큰 문제를 작은 문제로 나눠서 푸는 알고리즘은 1. 다이나믹 프로그래밍 2. 분할 정복 총 2가지가 있다. 큰 문제를 여러개의 작은 문제로 나누었을때 작은 문제가 문제끼리 중복이 가능한것이 DP이고 중복이 불가능한것이 분할정복기법이다. 그중에서 이번에는 다이나믹 프로그래밍에 대해서 공부해 보겠다. 작은 예시를 들어보겠다. 피보나치 수열이라고 많이 들어봤을것이다 0 1 1 2 3 5 8 13 21 34 55 와 같이 n번째 수는 n-1번째 수와 n-2번째 수의 합으로 이루어져 있는 수열을 피보나치 수열이라고 한다 우리는 보통 피보나치 수열 풀때 import java.util.*; public class Main { public static void main(String[] args){ System.out...

문제 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다. 출력 가능한 D값의 최댓값을 출력한다. 알고리즘 설계 수빈이의 위치 S에서 동생들이 있는 위치 A1,A2 -- An..

문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. GCD가 뭔지도 안알려주는 문제설명을 보고 실망하였다 구글에 검색해보니 최대공약수였다 ㅎㅎ.. 상식인가? 암튼 문제를 요약하자면 1. 첫줄에 테스트 케이스 개수를 입력하고 2. 각줄의 수의 개수 / 수 를 입력한다 3. 입력한 수를 모두 짝을 이루고 짝을 이..

문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ..

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 알고리즘 설계 일단 에라토스테네스의 체 문제를 풀고 와가지고 본 이 문제는 딱 봤을때 쉬웠다 그런데 정답률이 27퍼밖에 되지않았던 이유는 에라토스테네스의 체로 풀지않으면 시간초과가 나는 문제였다 이전에 풀었던 에라토스테네스의 체 문제는 규칙에 따라 수를 삭제 하고 몇번째 삭제한 수가 몇이냐는 걸 묻는 문제였고 이 문제는 규칙에 따라 수를 삭제하고 해당 범위내의 소수를 출력하라는 문제였다 1. 소수인걸 true 소수가 ..

문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000) 출력 첫째 줄에 K번째 지워진 수를 출력한다. 알고리즘 설계 1. 일단 크기가 n+1인 배열을 만들어 2부터 n+1까지의 수를 입력한다 2. 삭제한 수를 0으로 만든다 3..