JArchive 프로그래밍 일기

오늘 한 일 

알고리즘 문제 5개를 풀었다. 

6일에 3개, 8일에 5개, 9일에 2개를 풀었었다. 

풀고 깃헙에 푸시하고 잠드니까 TIL을 건너뛰게 됬다. 

기록을 게을리 하지 말아야지!

코로나 때문에 4달째 세상이 흉흉한데 건강관리(마음도 몸도)에 힘써야겠다. 

오늘 할 일 

알고리즘 문제를 풀었다. 2개 풀었는데 다 내힘으로 풀어서 기분 좋았다. 

오늘 한 일 

알고리즘 문제를 풀었다. 

숫자의 총 개수 (small 버전, large 버전) 문제.

처음에는 생각나는대로 문제를 푸는 것이 좋다는 것이 오늘의 교훈이었다. 

복잡하게 하려다가는 첫걸음 조차 꼬이는 경우가 생기기 때문이다. 

전역변수와 지역변수의 차이를 짚고 넘어갔다.

추가로, 전역변수에서는 배열을 선언하면 왜 자동으로 0으로 초기화 되는지 확인 해봐야겠다. 

문제 

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하세요.

만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다.

출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.

1 2 2 3 2 4 2 4 와 같이 출력한다.

입력설명 

첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.

출력설명

첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다

풀이 

이중 반복문을 이용해서 숫자 마다의 약수를 구하려고 했었다. 

하지만 그렇게 하면 시간초과가 난다. 

그래서 약수의 개수를 for문을 순회할 때마다 +1 해주는 방식이 필요하다. 

"1을 약수로 갖는 숫자들은 어떤 숫자들일까?"
"1의 배수들이다."

"2을 약수로 갖는 숫자들은 어떤 숫자들일까?"
"2의 배수들이다."

2의 배수들은 2를 약수로 갖는다. 

이 점을 이용한 것이다. 

1은 모든 수의 약수이므로 배열 모든 칸에 +1을 해준다. 

2는 모든 짝수 들의 약수이므로 2의 배수에 해당하는 칸에 +1을 해준다. 

. . . 

내부 for문을 이렇게 구현한다. 즉, j는 i로 시작하되, i의 배수이니까 j는 j+i만큼 커지면서 배열을 건너뛰어가면서 배수를 인덱싱한다. 

궁금한 점 

50001 크기의 int 배열 cnt는 지역변수 인 경우에 테스트케이스에서 fail이 난다. 

그런데 cnt가 전역변수 인 경우에는 테스트케이스를 전부 통과했다. 

그 차이가 뭔지 궁금했다. 

#include <stdio.h> 

int cnt[50001];

int main(int argc, char** argv) {
	
	//freopen("input.txt", "rt", stdin);
	int input=0, i=0, j=0;
	scanf("%d", &input);
	
	for(i=1; i<=input; i++){
		
		// i의 배수들을 +1 처리해준다. 
		// i를 약수로 갖는 숫자들을 찾는 것이다.  
		for(j=i; j<=input; j=j+i){
			cnt[j]++;
		}
	}
	
	for(i=1; i<=input; i++){
		printf("%d ", cnt[i]);
	} 

	return 0;
}

선생님이 답변을 달아주셨다. 

오늘 한 일 

거의 3주만에 뇌를 자극하는 알고리즘 책을 다시 폈다. 

이진탐색트리를 다시 짜봤다. 

알고리즘 문제풀이 감을 살리기 위해 간단한 조건문 반복문을 활용한 문제풀었다.

오늘 한 일 

따배C++ 강좌를 들었다. 오늘은 프로그램 기본 구조 에 대한 내용이었다. 

동국대 컴공에서 아주 유명한 교수님이라고 들었다. 

믿음도 가고 강의 스타일도 쏙쏙 들어오는 타입이라 완강까지 기대된다. 

오늘 한 일 

게시판 글에 댓글(comment)기능을 완성했다. 

세션처리를 했다. 

C++ 배우기를 시작했다.