Maintenance script: Repair batch-0003 pages from live compare

2026-03-27T00:29:13Z

Repair batch-0003 pages from live compare

← Older revision		Revision as of 00:29, 27 March 2026
Line 20:		Line 20:

	int main() {		int main() {
	int arr[LIMIT] = {0}, num, index = 0, target;		int arr[LIMIT] = {0}, num, index = 0, target;
	clock_t start,end; // 수행시간 구할 때 쓰려고 넣은 변수.		clock_t start,end; // 수행시간 구할 때 쓰려고 넣은 변수.
	target = 1500; // 1500번째 수를 구하도록 할 때 쓰는 변수.		target = 1500; // 1500번째 수를 구하도록 할 때 쓰는 변수.

	start = clock(); // 시작한 시간.		start = clock(); // 시작한 시간.
	for(int i = 1;arr[target-1] == 0;i++) {		for(int i = 1;arr[target-1] == 0;i++) {
	num = i;		num = i;
	while((num % 2) == 0) {		while((num % 2) == 0) {
Line 37:		Line 37:
	}		}
	if(num == 1) { // 2, 3, 5 로 나눴는데 몫이 1이면 못난이수.		if(num == 1) { // 2, 3, 5 로 나눴는데 몫이 1이면 못난이수.
	arr[index] = i; // 몫이 1이 아니면 그냥 잡수.		arr[index] = i; // 몫이 1이 아니면 그냥 잡수.
	index++;		index++;
	}		}
Line 44:		Line 44:

	cout << "Run time = " << (double)(end-start)/CLK_TCK << endl		cout << "Run time = " << (double)(end-start)/CLK_TCK << endl
	<< arr[target-1] << endl;		<< arr[target-1] << endl;
	return 0;		return 0;
	}		}
Line 64:		Line 64:

	아... 괜히 어렵다.		아... 괜히 어렵다.

imported>sksmsvlxk at 05:39, 23 September 2008

2008-09-23T05:39:45Z

New page

== 설명 ==
* 조낸 간단함. 1500개짜리 배열이 꽉 찰때까지 1부터 시작해서
쭉 훑으면서 찾는 방식.
* 2, 3, 5의 배수라는 점에 착안해서 코딩.

== 소감 ==
정말 좋지 않은 코드. 900번째까지 구하는데 2 초걸리고,
1000번째까지 구하는데 7초 걸린다...

1500번째꺼 구하도록 했더니... 76초 걸린다...

#include <iostream>
#include <ctime>
using std::cout;
using std::cin;
using std::endl;
using std::clock_t;

#define LIMIT 1500 // 배열 한계수

int main() {
int arr[LIMIT] = {0}, num, index = 0, target;
clock_t start,end; // 수행시간 구할 때 쓰려고 넣은 변수.
target = 1500; // 1500번째 수를 구하도록 할 때 쓰는 변수.

start = clock(); // 시작한 시간.
for(int i = 1;arr[target-1] == 0;i++) {
num = i;
while((num % 2) == 0) {
num /= 2;
}
while((num % 3) == 0) {
num /= 3;
}
while((num % 5) == 0) {
num /= 5;
}
if(num == 1) { // 2, 3, 5 로 나눴는데 몫이 1이면 못난이수.
arr[index] = i; // 몫이 1이 아니면 그냥 잡수.
index++;
}
}
end = clock(); // 끝난 시간.

cout << "Run time = " << (double)(end-start)/CLK_TCK << endl
<< arr[target-1] << endl;
return 0;
}

== 느낀 점 ==
다른 방식의 알고리즘으로 그냥 막 배열에 때려넣은 뒤
sorting 을 사용하는 방법을 생각해봐야 하겠다 라는 것을 느낌.

사실 처음부터 정렬을 써야겠다고 생각했으나
도무지 방법이 생각이 안남.

2, 3, 5의 거듭제곱꼴이라는 것에 착안해서 지수에서 어떤 법칙을 찾아내려고 했으나
30개까지 구해봐도 법칙을 못찾아서 그냥 위의 방법으로 구했음...

보창이형 코드보니 지수를 써서 하는 방법이 있는거 같은데
자세히 보진 않았지만 그냥 막 때려넣지 않았나... 하는 생각이...
결국 퀵 소트로 정렬하신 듯 한데...

아... 괜히 어렵다.

UglyNumbers/송지훈 - Revision history

Maintenance script: Repair batch-0003 pages from live compare

imported>sksmsvlxk at 05:39, 23 September 2008