알못에서 잘알까지

    9번 문제   

    내가 풀이한 답   

  처음에는 간단히 모든 수를 돌며 그 수에 해당하는 수까지 또 돌아서 약수를 구하는 방식으로 코드를 짰다. 즉, 모든 수를 다 돌기 때문에 N제곱의 시간복잡도가 나온다. 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	
	int n, i, j, cnt=0;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++) {
		cnt=0;
		for(j=1; j<=i; j++){
			if(i%j==0){
				cnt++;
			}
		}
		printf("%d ", cnt);
	}
	printf("\n");
}

 그 결과는 60점에 큰 숫자로 들어가버리면 시간 초과가 뜬다... (Time Limit: 1초)

 더 곰곰히 생각해보다가 더 이상 떠오르질 않아서 강의 초반부에서 전략을 들었다. 모든 경우의 수를 다 도는 것은 비효율적이므로 어차피 약수를 구하는 것은 배수의 개념으로도 풀 수 있다고 말하였다. 다시 머리를 한 대 얻어맞은 듯한 느낌을 받았다. 강의의 내용은 다음과 같다. 순회(for)를 돌면서 해당하는 값의 배수들만 값을 증가시켜주는 방법이다. 

#include <stdio.h>
using namespace std;
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int array[50001];
	int n, i, j;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++) {
		for(j=i; j<=n; j=j+i){
			array[j]++;
		}
	}
	
	for(i=1; i<=n; i++){
		printf("%d ", array[i]);
	}
}

 그 결과 80점... 왜 그럴까.. 하고 사이트의 답안과 비교해봤다. 

    사이트의 답안   

#include<stdio.h>
using namespace std;
int cnt[50001];
int main(){
	//freopen("input.txt", "rt", stdin);
	int n, i, j;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		for(j=i; j<=n; j=j+i){
			cnt[j]++;
		}
	}
	for(i=1; i<=n; i++){
		printf("%d ", cnt[i]);
	}
	return 0;
}

  사이트의 답안과 내 코드는 배열을 선언한 부분의 전역인지 지역인지의 차이였다. 지역변수와 전역변수의 차이점에 대해 조사를 해봐야겠다...

    8번 문제   

    내가 풀이한 답   

 처음에는 ' ( ' 에 대한 변수, ' ( ' 에 대한 변수를 따로두어서 둘의 개수가 같지 않으면 NO라고 출력하면 된다고 생각해서 코드를 짰다. 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	char a[31];
	int i, left = 0, right= 0;
	scanf("%s", &a);
	
	for(i=0; a[i]!='\0'; i++){
		if(a[i] == '(') left++;
		if(a[i] == ')') right++;
	}
	//printf("left: %d, right:%d\n", left, right);
	if(left != right) printf("%s", "NO");
	else printf("%s\n", "YES");
	
	return 0;
}

 그 결과는 60점...

 다시 곰곰히 생각을 해보니 중간에 ' ( '로 시작해버리는 예 ( ( ) ( ) ) ) (  이것도 올바른 괄호가 아니기 때문에 코드의 수정이 필요했다. 2개의 변수를 합쳐서 ' ( '로 시작하는 것은 음수로 두고 음수이면 for문을 빠져나오도록 코드를 다시 짰다. 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	char a[31];
	int i, cnt=0;
	scanf("%s", &a);
		
	for(i=0; a[i]!='\0'; i++){
		if(a[i] == '(') cnt++;
		else cnt--;
		if(cnt<0) break;
	}
	
	if(cnt == 0) printf("%s\n", "YES");
	else printf("%s\n", "NO");
	return 0;
}
	

 그 결과 통과를 했다.

    사이트의 답안   

#include<stdio.h>
using namespace std;
int main(){
	//freopen("input.txt", "rt", stdin);
	char a[100];
	int i, cnt=0;
	scanf("%s", &a);
	for(i=0; a[i]!='\0'; i++){
		if(a[i]=='(') cnt++;
		else if(a[i]==')') cnt--;
		if(cnt<0) break;
	}
	if(cnt==0) printf("YES\n");
	else printf("NO\n");
	return 0;
}

  사이트의 답안과 내 코드가 같은 논리로 짜여진 것을 확인했다.

    7번 문제   

    내가 풀이한 답   

 처음에 배열 하나만 가지고 index의 위치를 기준으로 코드를 짜려고 했다. 하지만, 너무 비효율적이라는 생각이 들었고 다른 방법을 생각해보았다. 방법이 잘 떠오르지 않아서 강의 초반부를 들었다. 그 때, 머리를 망치로 얻어맞은듯한 느낌을 받았다. 배열을 하나 더 사용하는 것이었다. 왜 이런 방법이 안떠올랐을까 하면서 자괴감이...

 처음 입력된 값을 받는 scanf에서 공백이 섞인 문자를 읽어들이기 위해 %[^\n]이라는 것을 사용했다. 이는 \n을 제외한 나머지들을 읽어들이는 역할을 한다. 그리고 공백없이 문자를 담을 배열인 b는 index라는 변수를 따로두었다. 공백이 아닌 문자가 확인될 때마다 index 변수에 해당하는 index에 값을 소문자로 변환해서 집어넣었다. 이 때, 소문자로 바꿔주는 것은 cctype 라이브러리의 tolower를 썼다. 이것도 정리를 해놔야겠다. 

#include <stdio.h>
#include <cstring>
#include <cctype>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	char a[101], b[101];
	scanf("%[^\n]", &a);
	
	int i, index = 0;
	
	for(i=0; i<strlen(a); i++){
		if(a[i] != ' '){
			b[index] = tolower(a[i]);
			index++;
            		// b[index++] = tolower(a[i]);
		}		
	}
	
    	//b[index] = '\0';
	printf("%s", b);
	return 0;
}
}

 그 결과 통과를 했다.

    사이트의 답안   

#include<stdio.h>
using namespace std;
int main(){
	//freopen("input.txt", "rt", stdin);
	char a[101], b[101];
	int i, p=0;
	gets(a);
	for(i=0; a[i]!='\0'; i++){
		if(a[i]!=' '){
			if(a[i]>=65 && a[i]<=90){
				b[p++]=a[i]+32;
			}
			else b[p++]=a[i];
		}
	}
	b[p]='\0';
	printf("%s\n", b);	
	return 0;
}
	
	

  나는 공백이 섞인 문자를 읽어들이기 위해 %[^\n]이라는 것을 사용했는데 gets라는 함수를 써서 쉽게 해결할 수 있었다. 또 하나 배워간다. 그리고 여기서 대, 소문자를 구분하기 위해 아스키 코드 65~90에 해당하는 대문자를 조건문으로 삼아 +32를 해주어 소문자로 만들었다. 

   1. char  to int   

 첫 번째 방법은 아스키 코드를 이용하는 방법이다. char 변수는 1 byte 정수이다. 하지만, char 자료형이 정수일지라도 아스키 코드로 해석된다. 아스키는 American Standard Code for Information Interchange의 약자로 영어 문자 또는 특수문자를 0에서 127 사이의 숫자(아스키 코드)로 나타낸다. 예를 들어 숫자 0은 코드 48이고 9는 57이다. 그리고 'a' 문자는 코드 97이다. 'b'는 98이다. 

 이러한 아스키 코드를 이용하여 char형 데이터를 int 형으로 바꾸는 방법은 48을 빼주는 방법과 '0'을 빼주는 방법이 있는데 예제는 다음과 같다. 

// 1. 48을 빼주는 방법

char one = "1";
int num = one - 48;

scanf("%d", num + 3); 		// 4


// 2. '0'을 빼주는 방법

char one = "1";
int num = one = '0';

scanf("%d", num + 4); 		// 5

   2. char 배열 길이만큼 순회(for)문 돌기   

char 배열의 길이만큼 순회(for)문을 도는 방법은 많은데 그 중 두 가지를 소개한다. 첫 번째 방법은 cstring 라이브러리의 함수 strlen()를 쓰는 방법이다. 마지막으로는 데이터가 없는 인덱스의 값이 '\0'임을 이용하는 방법이다. 두 번째 방법은 아래 그림을 참조하면 된다. 

 두 가지 예제는 다음과 같다.

// 1. cstring 라이브러리 strlen() 함수 이용하기

#include <cstring>

char array[51];
scanf("%s", &array);			// g0en2Ts8eSoft 입력

int len = strlen(array);        	// 13

for(int i=0; i<len; i++) {
	// 작업
}


// 2. 값이 없는 index의 값이 '\0'임을 이용하기

char array[51];
int res = 0;
scanf("%s", &array);			// g0en2Ts8eSoft 입력

for(int i=0; array[i] != '\0'; i++) {
	if(a[i]>=48 && a[i]<=57){
		res = res * 10 + (a[i] - 48);
	}
}

    6번 문제   

    내가 풀이한 답   

 문자가 50을 넘지 않으므로 51까지 배열을 선언하였다. 그리고C/C++ 에서는 Char형 데이터와 Int형 데이터를 제대로 구분해 본 적이 없었다. 그러던 중 아스키 코드를 알게 되었고 공부를 하게 되었다. (https://almotjalal.tistory.com/22) 공부를 한 뒤 코드를 짜 보니 char형과 int형이 구분되었고 char형 데이터를 int형 데이터로 바꾸는 작업도 성공했다. 그리고 순회(for)를 돌면서 숫자들이 쌓이면 자릿수가 변하므로 *10씩 곱해주었다. 약수 구하는 것은 5번 문제(진약수)와 비슷했다.  

#include <stdio.h>
#include <cstring> 
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	char a[51];
	int	num = 0, cnt = 0, i;
	scanf("%s", &a);
	
	for(i=0; i<strlen(a); i++){
		if((a[i]>=48) && (a[i]<=57)){
			num = num * 10 + (a[i]-'0');
		}
	}
	
	for(i=1; i<=num; i++) {
		if(num%i==0) cnt++;
	}
	
	printf("%d\n%d\n", num, cnt);
	return 0;
}

 그 결과 통과를 했다.

    사이트의 답안   

#include<stdio.h>
using namespace std;
int main(){
	//freopen("input.txt", "rt", stdin);
	char a[100];
	int res=0, cnt=0, i;
	scanf("%s", &a);
    
	for(i=0; a[i]!='\0'; i++){
		if(a[i]>=48 && a[i]<=57){
			res=res*10+(a[i]-48);
		}
	}
    
	printf("%d\n", res);
	for(i=1; i<=res; i++){
		if(res%i==0) cnt++;
	}
    
	printf("%d\n", cnt);
	return 0;
}
	

 사이트의 답안과 비슷한데 순회(for)문을 도는 과정에서 차이가 있었다. 배열에서 빈 인덱스는 '\0'으로 채워지는데 그것을 이용한 것이다. 나머지는 다 똑같은 논리였다.

    5번 문제   

    내가 풀이한 답   

 문제를 보니 입력 예제의 맨 앞자리 두 자리 수와 "-" 뒤의 자리 수가 제일 중요하다는 느낌을 받았다. 나이를 계산할 때에는  <stdlib.h> 라이브러리의 atoi 함수를 이용하여 문자열을 숫자열로 바꿔주는 작업을 하였고 년도가 2019년으로 고정되어 있기 때문에 1900년생들은 119, 2000년대생들은 19를 기준으로 맨 앞자리 두 자리수를 빼서 +1을 붙여주면 됐고 성별을 알기 위해서는 "-" 뒤의 숫자가 무엇에 해당하는지만 확인하면 됐고 문제에서 주어진대로 1, 2, 3, 4 총 4가지 경우의 수만 생각을 하고 코드를 짰다. 

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

int main(int argc, char** argv) {
	string s;
	cin >> s;
	
	int age = atoi(s.substr(0, 2).c_str());
	int gender = atoi(s.substr(7, 1).c_str());
	
	if(gender == 1) cout << 119 - age + 1 << " M" << endl;
	else if(gender == 2) cout << 119 - age + 1 << " W" << endl;
	else if(gender == 3) cout << 19 - age + 1 << " M" << endl;
	else cout << 19 - age + 1 << " W" << endl;
	
	return 0;
}

 그 결과 통과를 했다.

    사이트의 답안   

#include <stdio.h>
int main(){
	char a[20];
	int year, age;
	scanf("%s", &a);
	
	if(a[7]=='1' || a[7]=='2') year=1900+((a[0]-48)*10+(a[1]-48));
	else year=2000+((a[0]-48)*10+(a[1]-48));
	
	age=2019-year+1;
	printf("%d ", age);
	
	if(a[7]=='1' || a[7]=='3') printf("M\n");
	else printf("W\n");
    
	return 0;
}

 강의에서 <iostream> 보다는 <stdio.h>를 쓰는 것이 입출력면에서 훨씬 성능이 좋다고 하였다. 나도 이제부터는 <stdio.h>로 바꾸어서 코드를 짜는 습관을 들여야겠다. 그리고 C++을 너무 오랜만에 만져서 그런지 char 배열로 해결할 수 있는 것을 string으로만 해결하려고 했던 행동을 반성하게 되었다. 어쩐지 비교연산자를 쓸 때 힘들게 되더라니...  그리고 강의에서는 아스키 코드를 썼다. 0은 48이고 1씩 증가하여 9는 57이 된다. 나머지는 논리적으로 다를게 없었다. 

    정리   

#include <stdio.h>   // scanf 함수를 쓰기 위한 라이브러리(iostream) 대체
#include <stdlib.h>  // atoi 함수를 쓰기 위한 라이브러리
#include <string>    // substr 함수를 쓰기 위한 라이브러리

1. 문자열을 잘라서 숫자로 바꿔주기

    // substr 문자열을 잘라주는 함수
    // atoi 해당 문자열을 숫자로 바꿔주는 함수
	int age = atoi(s.substr(0, 2).c_str());
	int gender = atoi(s.substr(7, 1).c_str());
    
 
2. 다음부터는 string 대신에 cahr[]도 고려할 것
    char a[20];


3. cin, cout 객체 대신에 scanf("%s", &a), printf("%d ", age) 함수를 사용할 것

    4번 문제   

    내가 풀이한 답   

 보자마자 풀이가 2개 떠올랐다. 하나는 각 입력들은 배열에 담아 sort 함수를 이용해 정렬을 하는 방법이었고 또 하나는 입력된 숫자만큼 순회(for)를 돌면서 최솟값과 최댓값을 업데이트하는 방법이다.

 먼저 배열에 담아 sort 함수를 이용해 정렬하는 코드는 다음과 같다. sort 함수를 사용하기 위해서는 표준 템플릿 라이브러리(STL)을 사용해야 하므로 algorithms 라이브러리를 #include 헤더에 포함시켜준다. 그리고 배열을 사람 개수만큼 동적으로 할당해주고 sort 함수를 사용해 배열을 오름차순으로 정렬해준다. 마지막 째 배열 요소와 첫 번째 배열 요소를 빼준 값을 출력해준다. 마지막으로 동적으로 생성한 배열을 해제하기 위해 delete[]를 선언한다.(delete와 delete[]의 차이점은 단일 객체와 배열 객체 각각의 원소의 차이로 소멸자 생성과 메모리 환원을 한다고 대강 알고 있지만 나중에 따로 블로그에 자세히 정리해 보는걸로...)

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char** argv) {
	int n;
	cin >> n;
	int *array = new int[n];
	
	for(int i=0; i<n; i++){
		cin >> array[i];
	}
	
	sort(array, array+n);
	
	cout << array[n-1] - array[0] << endl;
	
	delete[] array;
	return 0;
}

 두 번째 방법은 STL을 안쓰는 방법... 순회(for)를 돌면서 최솟값과 최댓값을 업데이트하는 방법이다. 최솟값인 min은 나이를 최대 100살까지로 고려해서 100으로 설정하였고 최댓값인 max는 음수가 아닌 제일 작은 값인 0으로 설정하였다.

#include <iostream>
using namespace std;

int main(int argc, char** argv) {
	int n, a, min=100, max=0;
	cin >> n;
	
	for(int i=0; i<n; i++){
		cin >> a;
		
		if(a > max) max = a;
		if(a < min) min = a;
	}
	
	cout << max - min << endl;
	
	return 0;
}

 두 방법 모두 통과를 했다.

    사이트의 답안   

#include<iostream>
using namespace std;
int main(){
	int n, i, a, max=-2147000000, min=2147000000;
	cin>>n;
	for(i=1; i<=n; i++){
		cin>>a;
		if(a>max) max=a;
		if(a<min) min=a;
	}
	cout<<max-min;
	return 0;
}

 사이트의 답안은 두 번째 방법과 똑같은 것을 확인할 수 있다.

    3번 문제   

    내가 풀이한 답   

 솔직히 처음에 풀이가 생각나질 않았다.  진약수는 자기 자신을 포함하지 않는 약수들의 집합이기 때문에 위의 출력 예제에서 마지막 10에서 = 으로 가는 방법이 생각나질 않았다. 한참을 고민했고 array를 써볼까도 했지만 이 문제 단계에서는 굳이 안써도 될 것 같다는 생각이 들기도 했고 한참을 더 고민했다. 도저히 생각나질 않아 동영상 풀이를 보았는데 초반부에 "모든 수의 진약수는 앞에 1이 공통적이고 (+ 2) (+ 4) (+ 5) 이런식으로 접근을 해야한다." 라는 얘기를 들었을 때 머리를 한 대 맞은 듯한 느낌이 들었다. 나는 고정관념에 휩싸였는지 무조건 플러스가 뒤에 있는 (1 + ) (2 +) (4 +) 이런식으로만 생각했다. 생각을 바로잡고 코드를 짜보니 답이 금방 나왔다. 

#include <iostream>
using namespace std;

int main(int argc, char** argv) {
	int n, sum=1;
	cin >> n;
	
	cout << sum;
	for(int i=2; i<n; i++){
		if(n%i==0){
			sum += i;
			cout << " + " << i;
		}
	}
	
	cout << " = " << sum << endl;
	
	return 0;
}

 1은 모든 수의 약수이므로 sum을 1로 아예 고정시켰다. 그리고 주어진 수 n까지 순회(for)를 돌면서 n을 i로 나누었을 때 나머지가 0인 것을 찾아 sum에 더하고 출력시켜주는 작업을 하였다.

 결과는 통과

    사이트의 답안   

#include <iostream>
using namespace std;
int main(){
	int n, sum=1, i;
	cin>>n;
	cout<<"1";
	for(i=2; i<n; i++){
		if(n%i==0){
			sum+=i;
			cout<<" + "<<i;
		}
	}
	cout<<" = "<< sum;
	return 0;
}

 강의 초반부에서 힌트를 듣고 코드를 짜다보니 사이트의 답안과 매우 비슷하다는 것을 알 수있다. 아니 똑같다. 앞으로 고정관념에서 좀 벗어나는 연습을 좀 해야할 것 같다...

    2번 문제    

.    1번 문제      

    1번

    내가 풀이한 답    제   1 문제   

    내가 풀이한 답   

#include <iostream>
using namespace std;

int main(int argc, char** argv) {
	int a, b, sum=0;
	cin >> a >> b;
	
	for(int i=a; i<=b; i++){
		sum += i;
		if(i==b){
			cout << i << " = ";
		}
		else {
			cout << i << " + ";
		}
	}	
	cout << sum << endl;
	return 0;
}

 문제를 보자마자 떠오른 생각은 string 변수를 하나 두어 변수에 값들을 추가하는 방식으로 생각을 했다. 하지만, 굳이 string 변수를 쓰지 않아도 cout 객체만으로도 출력할 수 있음을 깨달았다. 출력 예제를보면  마지막에만 "=" 이고 나머지는 "+" 인 것을 확인하고 순회를 돌면서 마지막 숫자인 b에 해당하는 부분에 분기문(if)으로 처리를 하였다. 

 결과는 통과를 하였다.

    사이트의 답안   

#include<stdio.h>
int main(){
	int a, b, sum=0, i;
	scanf("%d %d", &a, &b);
	for(i=a; i<b; i++){
		sum+=i;
		printf("%d + ", i);
	}
	printf("%d = %d\n", i, sum+i);
	return 0;
}

 여기서는 C 언어로 작성되었다. 굳이 분기문(if)문을 안쓰고 짤 수 있다는 것을 확인했다. +에 해당하는 부분에만 순회를 돌고 마지막은 그냥 따로 빼서 출력을 한 모습... 이렇게 더 간단하게 짤 수 있다는 것을 느꼈다.

    1번 문제   

    내가 풀이한 답   

#include <iostream>
using namespace std;

int main(int argc, char** argv) {
	int n, m, sum = 0;
	cin >> n >> m;
	int temp = m;
	
	for(int i=0; i<n/m; i++) {
		sum += temp;
		temp = temp + m;
	}
	
	cout << sum << endl;
	
	return 0;
}

 처음에는 자연수 N의 개수만큼 순회(for)를 돌고 조건문(if)을 사용해 M으로 나누어서 0이되는 숫자를 찾아 Sum 변수에 더해줄 생각을 하였지만 너무 불필요하게 순회를 돈다고 생각했다.

 하지만, 어차피 배수만 더해주면 되는 조건이라고 생각을 해서 N을 M으로 나눈 개수만큼만 돌고 순회를 도는 동안 m을 계속 더한 값을 저장해주는 temp 변수를 설정해서 sum 변수에 더하는 것을 생각해보았다. 

 결과는 통과

    사이트의 답안   

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
	int n, m, sum = 0;
	cin >> c >> n >> m;
    
	for (int i=1; i<=n; i++) {
		if(i%m==0) {
			sum=sum+i;
		}
	}
    
	cout << sum << endl;
    
	return 0;
}

 처음에 생각했던 것과 똑같은 답이였다. 오늘은 쉬운 문제를 풀어봤는데 C++이 좀 오랜만이기도 해서 낯설었다. Time Limit이 1초 이내라는데 지금 단계에서는 체감이 느껴지지 않는다. 실행 시간 체크와 메모리 누수 체크는 기초 다지기 이후로 알고리즘을 어느정도 복습한 뒤에 해야겠다...