알고리즘 공부/강의 - 2. 반복문을 이용한 산수문제

기본적인 산수를 풀 수 있는 실력이 되었다면 그다음으로 보는 것이 반복문이다. 반복문의 종류는 크게 두 가지로 나뉜다고 생각한다.

 

1. 배열로 저장이 필요 없는 반복문.

 

2. 배열로 저장이 필요한 반복문.

 

 

 

 

배열로 저장이 필요 없는 반복문은 값을 받는 for문에서 바로 비교가 가능하고 계산해서 출력이 가능한 경우이다. 예를 들면 다음과 같다.

ex) 3< n <100,000,000의 숫자가 입력이 되고, 1부터 n까지의 숫자를 센다. 사용된 숫자의 개수는 몇일까?라는 문제에서 1부터 n까지의 숫자를 모두 배열에 저장할 필요는 없다. for문을 돌려 앞에서부터 바로바로 값을 저장시키면 된다. 위의 문제는 수가 크기 때문에 일일이 값을 받지 않고 약간의 수학적 직관성을 이용하여 문제를 풀 수 있다. 10 단위씩 끊어서 10까지 몇 개, 100에서 10 빼면 몇 개, 1000에서 100 빼면 몇 개라는 식으로 풀 수 있다.

int n, sum=0, cnt=1, digit=9, res=0;
scanf("% d", &n);
while(sum+digit <n){
sum=sum+digit;
res=res+(cnt*digit);
cnt++;
digit=digit*10;
}
res=res+((n-sum)*cnt);
printf("% d\n", res);

배열로 저장이 필요한 부분은 정렬 같은 문제가 대표적이다. 다른 뒤에 것들과 모두 비교해서 순서나 등수를 매기는 문제들은 모두를 놓고 비교해야 하므로 배열에 저장할 필요가 있다. 근데 위에 문제처럼 단위가 1억 개 정도로 커지면 그때는 저장보다는 바로 비교가 가능하다는 뜻이다. 다음 문제처럼 문자열이 나오거나 서로 비교해야하면 보통은 문자열로 받아서 풀면 편하다.

 

그러면 다음 문제는 배열이 필요할까요? 안 필요할까요? 한 번 생각해보시기 바랍니다.^^