ë°
- Get link
- Google+
- Other Apps
Labels:
blogging
code inspection
programming
thinking
- Get link
- Google+
- Other Apps
저도 간단한 알고리즘 문제 하나... :-)
어떤 수 n이 주어졌을때 1~n까지의 수를 쭈욱 썼을때 나오는 1의 개수를 구하는 문제입니다.
예를 들어 13이라는 수가 주어지면 1~13까지의 수 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13에서 1은 1, 10, 11, 12, 13에 나오며 그 개수는 6이 됩니다. 즉, f(13)=6.
원래 문제는 f(n)=n이 되는 1이 아닌 가장 작은 수를 구하는 문제인데 이 문제의 경우에는 처음부터 쭈욱 세어나가면 되기 때문에 간단히 다음과 같이 구현을 하면 됩니다. ((한가지 주의할 점은 이전에 찾았던 n-1값을 사용하지 않고 다시 처음부터 n까지 값을 계산하면 시간이 너무 많이 걸린다는 점입니다. 위의 코드에서는 static 변수를 사용하여 이전 값에 계속 더해나가는 방법을 사용했습니다.))
#include
int count1(int n)
{
static int cnt = 1; // not 0 because n starts from 2. see main.
while (n > 0) {
if ((n % 10) == 1) ++cnt;
n /= 10;
}
return cnt;
}
int main()
{
using namespace std;
int n = 2;
while (count1(n) != n) ++n;
cout << n << endl;
}
좀 재미가 없죠? 그래서 이번 문제는 어떤 수 n에 대해서 f(n)을 O(1)시간에 구하는 알고리즘을 만드는 것입니다. 관심있으신 분들은 한번 풀어보세요. 제가 만든 코드는 내일 올려보겠습니다.
어떤 수 n이 주어졌을때 1~n까지의 수를 쭈욱 썼을때 나오는 1의 개수를 구하는 문제입니다.
예를 들어 13이라는 수가 주어지면 1~13까지의 수 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13에서 1은 1, 10, 11, 12, 13에 나오며 그 개수는 6이 됩니다. 즉, f(13)=6.
원래 문제는 f(n)=n이 되는 1이 아닌 가장 작은 수를 구하는 문제인데 이 문제의 경우에는 처음부터 쭈욱 세어나가면 되기 때문에 간단히 다음과 같이 구현을 하면 됩니다. ((한가지 주의할 점은 이전에 찾았던 n-1값을 사용하지 않고 다시 처음부터 n까지 값을 계산하면 시간이 너무 많이 걸린다는 점입니다. 위의 코드에서는 static 변수를 사용하여 이전 값에 계속 더해나가는 방법을 사용했습니다.))
#include
int count1(int n)
{
static int cnt = 1; // not 0 because n starts from 2. see main.
while (n > 0) {
if ((n % 10) == 1) ++cnt;
n /= 10;
}
return cnt;
}
int main()
{
using namespace std;
int n = 2;
while (count1(n) != n) ++n;
cout << n << endl;
}
좀 재미가 없죠? 그래서 이번 문제는 어떤 수 n에 대해서 f(n)을 O(1)시간에 구하는 알고리즘을 만드는 것입니다. 관심있으신 분들은 한번 풀어보세요. 제가 만든 코드는 내일 올려보겠습니다.
벼랑끝 전술... ;ㅁ;
ReplyDelete펜과 종이로 재현하는건.. 제 고등학교 시절이 생각나는... 자습시간때문에 컴퓨터 앞에 앉을 시간이 없어서, 주중에는 노트에 코딩하고 주말에 허락된 2시간여동안 타이핑을 쳐서 실행시켜보는게 인생의 낙이었다죠. (덕분에 뇌의 일부분이 Java 인터프리터가 되어버렸었다는... 당시엔 Java공부중이었거든요 ㅋ)
벼랑끝 전술... 회사에서 저한테 쓰면 어떻게 하지 하는 걱정에 한줄 넣어두었습니다.
ReplyDelete가끔 현장에서 core dump가 나며 프로그램이 죽게 되면 저희 윗분께선 이런 말을 하십니다. "따라 죽어라." 물론 진담은 아닙니다만... 가시가 있죠.
전 중/고딩때는 집에서 컴퓨터를 안사주셔서... 잡지책만 보면서 서러움을 달랬었죠. 대학교 들어가고 나서 집에 온 컴퓨터는 고3 올라가는 사촌이 압수당한 놈이었다죠. ;-)
그러고보니 까막님도 자습시간에 공부는 잘 안되었겠네요. :-D
잡지책만 보면서 서러움을 달래다.. 동감 100%!
ReplyDelete잘안되지만, 노트에 코딩하는 것도 한계가 있어서... 할게 없어 공부를 했다는 우울한.. 이야기가 전해져 오지요. 물론, 할게 없다는건 만화책과 무협지를 모두 보고 나서라는 전제조건이 붙지만요. :)
중학교 시절에 은하영웅전설 sp3의 크랙파일을 디스어셈블해서 공부하던 생각이 문득.. ( '')