[Algorithm] 셀프 넘버
어떤 자연수 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보다 작은 모든 셀프 넘버들의 합을 구하는 프로그램을 작성하라.
이 문제는 게임 회사인 넥슨의 입사문제라고 알려진 문제들 중 제일 쉬운 것이다.
'Project > Dev Story' 카테고리의 다른 글
[Algorithm] 재귀 함수 기초 2 (0) | 2017.11.07 |
---|---|
[Algorithm] 재귀 함수 기초 1 (0) | 2017.11.06 |
[Algorithm] 1부터 n까지 더하는 알고리즘의 설계 (0) | 2017.08.26 |
[OpenBCI] 뇌파로 마인크래프트의 스티브 움직이기 (1) | 2017.08.03 |
[OpenBCI] Cython 보드 Windows 10에 설치하기 (3) | 2017.08.01 |
[Algorithm] 재귀 함수 기초 2
6. 2진수 변환, 진법 변환
14를 2진법으로 고칠 때 어떤 과정을 거칠까?
14 / 2 = 7 … 0
7 / 2 = 3 … 1
3 / 2 = 1 …. 1
따라서 1110이 된다.
십진법 수 n을 2진법으로 나타내는 함수는 f(n, 2)로 정의할 수 있다.
그럼, 십진법 수 n이 2보다 작은 경우 n을 출력, 2보다 크거나 같은 경우 점화식을 f(n/k, k), printf(“%d”, n % k);로 정리할 수 있다.
2진법 외 다른 진법으로 변환하고자 하는 경우 f(n, 2) 부분을 f(n, k)로 바꾸기만 하면 된다.
11진법-16진법으로 변환하고자 하는 경우 알파벳을 출력하는 부분을 만들어야 하므로 아래와 같이 서식 문자를 바꾼다.
(서식문자만 바꾸면 됨 -> %X[대문자], %x[소문자])
아래 예시 코드는 16진법까지 변환할 수 있다.
20진법까지 바꾸고자 하는 경우, char letter[21] =“0123456789ABCDEFGHIJ"; 변수를 만들어 변수 내 값을 꺼낸다. 이 부분은 한번 생각해보길 바란다.
7. 우박수(3n+1) Basic
1. 어떤 자연수 n 이 입력되면,
2. n이 홀수이면 3n + 1을 하고,
3. n이 짝수이면 n/2 를 한다.
4. 이 n이 1이 될때까지 2, 3 과정을 반복한다.
예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.
이 처럼 어떤 자연수 n이 입력되면 위 알고리즘에 의해 1이 되는 과정을 모두 출력한다.
솔직히 이 문제는 문제에서 해결 전략을 다 줬다... 종료 조건만 생각하면 된다.
8. 우박수(3n+1) reverse
1. 어떤 자연수 n 이 입력되면,
2. n이 홀수이면 3n + 1을 하고,
3. n이 짝수이면 n/2 를 한다.
4. 이 n이 1이 될때까지 2, 3 과정을 반복한다.
예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.
이 처럼 어떤 자연수 n이 입력되면 위 알고리즘에 의해 1이 되는 과정을 모두 출력한다.
근데, 이 순서의 역순을 출력하고자 한다.
즉, 1, 2, 4, 8, 16, 5가 출력되어야 한다.
반대로 한다 (...)
조건은 같으나 n == 1인 경우 printf("1\n"); 해주고 더 이상 함수를 호출하지 않도록 한다.
9. 삼각형 출력하기 (반대로)
5가 입력되면
*****
****
***
**
*
을 출력한다.
이 문제는 * 출력과, \n 출력할 부분을 구별해 주면 된다.
10. 피보나치 수열 (Large)
자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.
단, N이 커질 수 있으므로 출력값에 10,009를 나눈 나머지를 출력한다.
이 문제는 Large 문제이므로 이전에 계산한 값을 메모리에 저장함으로써
동일한 계산의 반복 수행을 제거하는 메모이제이션 기법으로 프로그램을 작성한다.
'Project > Dev Story' 카테고리의 다른 글
[Algorithm] 셀프 넘버 (0) | 2017.11.08 |
---|---|
[Algorithm] 재귀 함수 기초 1 (0) | 2017.11.06 |
[Algorithm] 1부터 n까지 더하는 알고리즘의 설계 (0) | 2017.08.26 |
[OpenBCI] 뇌파로 마인크래프트의 스티브 움직이기 (1) | 2017.08.03 |
[OpenBCI] Cython 보드 Windows 10에 설치하기 (3) | 2017.08.01 |
[Algorithm] 재귀 함수 기초 1
재귀 함수는 자기 자신을 호출하는 함수이다.
프로그램 실행 중 재귀 함수를 만나면, 현재 위치를 저장하여 호출할 함수의 주소로 넘어가 함수 내용을 수행한다.
함수 실행이 끝나면 원래 위치로 복귀해 다음 코드를 수행한다.
무한 루프에 빠지지 않기 위해 종료 조건이 있어야 하고, 코드를 단순화할 수 있다. 무리하게 호출하면 스택 공간을 이용한다는 재귀함수의 특성 때문에 ‘스택 오버플로우’ 가 일어날 수 있다.
1. 1부터 n까지 출력하기
scanf로 n을 입력받은 후, solve(1) 호출, 이후, solve(n+1)을 수행해 n과 a가 같으면 종료 (종료조건)
따라서, 소스코드는 아래와 같이 쓸 수 있다.
2. n부터 1까지 출력하기 (역순)
solve 함수에서 printf와 solve(n+1) 위치만 바꾸어 주면 된다...
3. 두 수 사이의 홀수 출력하기
1부터 n까지 출력하는 소스 코드에서 홀수를 찾아 모두 출력한다.
if(n % 2 != 0) 조건을 사용하면 된다.
4. 팩토리얼 출력하기
n을 입력받아 n!을 출력한다.
예를 들어, n이 5인 경우, 5! = 5 * 4 * 3 * 2 * 1 = 120을 출력한다.
이 경우에는 점화식을 세워야 한다. 1!은 1이 되므로 종료조건을 아래와 같이 설정하며,
아닌 경우에는 아래와 같이 점화식이 도출되도록 Code를 작성한다.
f(5)
= 5 * f(4)
= 5 * 4 * f(3)
= 5 * 4 * 3 * f(2)
= 5 * 4 * 3 * 2 * f(1)
= 5 * 4 * 3 * 2 * 1
= 120
따라서, 여기서의 점화식은 n * f(n-1) 이다.
5. 피보나치 수열
N번째 피보나치 수를 출력한다. 이 경우에도 점화식을 세운다.
피보나치 수열의 기본 규칙은 처음 두 항은 1이고 세 번째 항부터 이전 두 항의 합이 된다.
즉, 1, 1, 2 다음부터 1+2 가 다음 항이 된다. 그 다음은 2+3=5가 된다.
따라서, 종료조건 if(n==0) return 0, if(n==1) return 1;
점화식은 f(n-1) + f(n-2) 로 세우면 된다.
'Project > Dev Story' 카테고리의 다른 글
[Algorithm] 셀프 넘버 (0) | 2017.11.08 |
---|---|
[Algorithm] 재귀 함수 기초 2 (0) | 2017.11.07 |
[Algorithm] 1부터 n까지 더하는 알고리즘의 설계 (0) | 2017.08.26 |
[OpenBCI] 뇌파로 마인크래프트의 스티브 움직이기 (1) | 2017.08.03 |
[OpenBCI] Cython 보드 Windows 10에 설치하기 (3) | 2017.08.01 |