도전하라! 시작하라!

XCYAZTX

YES

CTA

NO

SGHDJHFIOPUFUHCHIOJBHAUINUIT

YES

CCCATT

NO

[문제 풀이]

순서대로 "CAT"이라는 단어가 순서대로 한 번만 존재해야하지만  "YES"가 출력되는 문제이다.

꼭 붙어있을 필요는 없고, 예제 이력 4를 보면 CAT가 하나 있는 것처럼 볼 수도 있겠지만!

CCCATT, CCCATT, CCCATT, CCCATT, CCCATT, CCCATT 로 여러가지의 CAT이 나오므로 출력은 NO라고 볼 수 있다.

[소스코드 설명]

변수 cat은 사용자의 입력이 들어가게 되고, cat2에는 C, A, T일 경우, 그 단어를 받아들이는 임시 변수라고 보면 된다.

그리고 여기서 cat2.find("CAT"); 라는 것을 썼는데, 그것은 C++에서 제공하는 find()함수를 이용하여 cat2에 CAT이 존재하는지를 찾아주는 함수이다.

#include <iostream>
#include <string>

using namespace std;

int main()
{
 int count;
 int i;
 string cat, cat2;

 cin >> cat;
 count = cat.length();

 for (i = 0; i < count; i++){
  if ((cat[i] == 'C') || (cat[i] == 'A') || (cat[i] == 'T'))
  {
   cat2 += cat[i];
  }
 }
 
unsigned int found = cat2.find("CAT");
 if (found != string::npos)
 {
  if (cat2.find_first_of("C") < found){
   cout << "NO";
  }
  else if (cat2.find_last_of("T") > found + 2){
   cout << "NO";
  }
  else
   cout << "YES";
 }
 else {
  cout << "NO";
 }
 return 0;
}

입력

5

출력 

74

출처: 2010-2011 October COCI Q3
번역+추천: likepad

[문제 풀이]

4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777, ....

[소스코드 설명]

이번 문제는 재귀함수를 이용해서 풀어보았습니다.

일단 위에 문제 풀이를 보시면서 규칙이 보이시나요?

만약 제 이전 알고리즘 포스팅을 보신 분이라면 어떤 규칙인지 아실텐데요.

네, 바로 홀수번째와 짝수번째로 나뉘어진 규칙입니다.

홀수 : 4, 44, 74, 444, 474, 744, 774, ...    // 4로 끝나고 있다.

짝수 : 7, 47, 77, 447, 477, 747, 777, ...    // 7로 끝나고 있다.

1의자리가 홀수번째에는 4이고, 짝수번째에는 7로 나타나고 있습니다.

#include <iostream>

using namespace std;
int k;

void recur(int num){
	if(num==0)
		return;
	recur((num-1)/2);
	if(num%2==0)
		cout << "7";
	else
		cout << "4";
}

//4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777...
//1의 자리는 4 7반복
//10
int main()
{

	cin >> k;
	
	recur(k);

	return 0;
}

입력

6

출력

1 2 3 6
4
12 

[문제 풀이]

문제는 크게 어려운 부분이 없습니다.

입력한 숫자의 약수와 약수의 갯수와 그 약수들의 곱을 구하는 문제입니다.

[소스코드 설명]

저는 먼저, 약수의 갯수를 세주는 count를 선언해주었습니다.

그리고 입력된 값 n이 for문을 돌면서 나누어 떨어지면 약수가 맞기 때문에 arr 배열에 값을 넣어주고 count값을 증가시켜주는 식으로 했습니다.

#include <iostream>
#include <string>
#define MAX (50)

using namespace std;

int n;

int main(){
	int i, j, k, arr[MAX], count = 0;
	int sum = 0, mul = 1;

	cin >> n;	//6

	//약수 출력 - 1,2,3,6
	for(i=1; i<=n; i++){
		if(n % i == 0){
			arr[count]=i;
			cout << arr[count] << " ";
			++count;
		}
	}
	cout << endl;

	//약수 개수 - 4
	cout << count << endl;;

	//약수 총합 - 12
	//약수 곱의 일의 자리수 - 6
	for(j=0; j<count; j++){
		sum += arr[j];
		mul *= arr[j];
		
	mul = mul%10;
	}

	cout << sum << endl;
	cout << mul << endl;

	return 0;
}

입력

13

출력

0 2 3 

[문제 풀이]

이 문제의 경우 10진수를 2진수로 바꾼 후에 1이 나타나는 위치를 찾는 문제입니다.

주어진 예제에서 13의 경우 2진수로 바꾸면 1101 이 됩니다.

문제에서 제일 오른쪽에서부터 0으로 시작한다 하였으니, 

현재 1이 나타나는 위치는 오른쪽에서부터 순서대로 0, 2, 3이 됩니다.

[소스코드 설명]

저는 짝수일 때와 홀수 일때에 대해서 따로 생각을 했습니다.

홀수 : 0001(1), 0011(3), 0101(5), 0111(7), 1001(9), 1011(11), 1101(13), ...

짝수 : 0010(2), 0100(4), 0110(6), 1000(8), 1010(10), 1100(12), 1110(14), ...

혹시 규칙이 보이시나요?

홀수의 경우 0의 자리가 무조건 1로 끝나고, 짝수의 경우 0의 자리가 무조건 0으로 끝나게 됩니다.

그래서 저는 "isFirst" 라는 것을 선언해서 홀수면서 처음나누어지는 것에 대해서는 무조건 1임을 나타내서 출력할 때 0도 포함이 되게 하였습니다.(1011)

그 다음 10진수를 2진수로 바꾸는 것을 손으로 직접 해보시면 아시겠지만, N값이 1이 될 때까지 계속 나눕니다. 따라서 N이 1이되면 break;로 계산을 멈추게 하였습니다.

그리고 2진수로 바꾸는 것이기 때문에 한 번 계산이 끝날 때마다 N값을 N/2로 갱신해주었습니다.

//bit_pos
#include <iostream>

using namespace std;
int n;

int main(){
	int ans=0;
	bool isFirst = true;

	cin >> n;	//13
	
	do{
		if (n%2 != 0){
			if(isFirst){
				isFirst = false;
			}
			else
				cout << " ";
			cout << ans;
		}
		ans++;
		if(n == 1)
			break;

		n = n/2;

	}while(true);

	cout << endl;
	return 0;
}

알고리즘.........................!!!!!!!!!!

제가 개인적으로 많이 부족한 기술력도 있지만, 학교에서 이론만 배워보고 알고리즘 문제를 접하거나 코딩을 직접 해 본 적이 없는 상태입니다.

현재 알고리즘이 매우 중요하게 된 멤버십에서 저는 완전 멘붕상태였죠..ㅠ

멤버십(이하 멤)에서 내주는 일일 알고리즘 3문제도 하루 반나절을 붙잡아야 풀 수 있는 정도였습니다.

매주 자체적으로 멤에서 매주 토요일마다 2시간동안 3문제를 푸는 '멤고리즘' 대회를 여는데요.

이 시험을 통해 알고리즘 등급이 메겨집니다. 

A~F등급이 있는데...(저희 대전 멤버십 내에서의 등급입니다. 전체멤버십과는 관련 없습니다.)

사실 저는 맨 처음 F등급을 받고, 현재는 D등급까지 올라왔습니다.

이렇게 올라온 것도 기존 회원분들 중에 멤고리즘이나 일일 알고리즘에 참여하지 않으시는 분들이 있기때문에 자동적으로 올라가게 된 것이 아닌가 싶습니다. 물론 한 문제라도 풀 수 있게 된 것도 있지만요!!

결론은 아직도 부족...

알고리즘...저도 정말 잘하고 싶습니다!! 

그런데 당장 어떻게 공부해야 될지도 모르겠어서 답답하기만 하답니다.

그 동안 알고리즘 공부하려고, 쉬운 책도 찾아봤지만...제 수준에 맞는 책이 없습니다!

자료구조 책을 다시보는것도 알고리즘을 잘하는 것에 도움이 되는 것도 한계가 있습니다!

잘하는 사람의 소스코드를 보거나, 설명을 듣는것도 물론 도움이 되지만... 제가 너무 타인에 의존적으로 변해버리더랍니다.

마치 우리가 궁금한 게 있으면 인터넷을 찾아보는 것 처럼요...

어제 급하게 만든 4주간의 공부 계획표를 들고 큰 운영자님과 상담을 했습니다.

'매일 3문제씩 푸는데 6개월 후면 지금보다야 많이 나아져있겠지~!'라는 안일한 생각을 갖고 있던 것을 큰 영자님은 완전  꿰뚫어 보시는거 같았습니다. ㅠㅠㅠ멤버십 합격이 전부가 아닌데 제가 너무 편안하게 있던건 아닌가 반성을 했습니다.

큰 운영자님과 상담에서는

1. 알고리즘 3문제를 푸는 것을 2시간을 잡고, 다른 사람한테 물어보거나 말하지 않고 집중력 있게 하기!

2. 질문이 있을 때에는 바로 옆에 물어볼 사람이 있다하더라도 첨삭 게시판의 글을 올리고 리플 달아달라하기!

(즉, 바로바로 물어보지말고 좀 더 혼자 생각하는 시간을 많이 가지라는 의미이기도 하지요)

3. 알고리즘 문제들을 풀기만 하지않고, 문제를 풀면서 분류하기!

(이진수, 배열 등으로 문제들을 분류해놓고 나중에 같은 분류의 문제들을 비교하면서 내가 어느 부분에서 못 푸는지 확인)

4. 시험 볼때에도 '오늘은 몇 점을 받아야지!' 라던가 '오늘은 몇 개를 풀어야지!' 라는 목표를 갖고 임하기!

5. 목표 등급은 B!!

이라는 결론을 받아왔습니다..ㅎㅎ

당장은 잘 하기 힘들거라고 생각합니다. 하지만 빠르게 성장해야죠!

꼭 6개월 안에 A!! B!! 상위권으로 갈 거라고 믿습니다 ㅎㅎ

혹시나 멤버십을 준비하시는 분들이 계시다면

알고리즘 공부도 틈틈히 열심히 하시길 바랍니다.

개인적으로 추천드리는 사이트는

알고스팟 : www.algospot.com/

(알고스팟은 유명한 사이트이지만, 가끔 영어 문제도 나와서 해석해야된다는 단점(?)이 있습니다.)

dovelet : www.dovelet.com/

(dovelet의 경우 모든 문제가 한글로 번역되어 있지만, 3단계까지는 무료이고, 그 이후부터는 유료인 단점(?)이 있습니다.)