U E D R , A S I H C RSS

PP Project/Colume2 Exercises

1. 3번.

1.1. 저글링 방식 (JugglingAction)

  • Leonardong이 작성한 코드
  • 총 4시간 8분 걸림

~cpp 
#include <iostream> 
#include <string> 
using namespace std; 
 
string roll( string str,int n, int i ); 
int getGcd(int aN, int aM);

void main() 
{ 
	string str = "abcdefg"; 
	int n = str.length();
	int i;
	cout << "current : " << str << endl
		 << "shitf amount? : ";
	cin >> i;

	cout << "after shifting : " << roll(str, n, i) << endl;
} 

string roll( string str, int n, int i ) 
{
	if ( i % n != 0 )
		i %= n;
	int gcd = getGcd(n, i);
	char temp;
//	for ( int count = 0 ; count * gcd < i ; count ++ )
	for ( int count = 0 ; count < i ; count += gcd)
		for ( int tag = 0 ; tag < gcd ; tag++ ){
			temp = str[tag];
			for ( int base = tag ; base + gcd < n ; base += gcd)
				str[base] = str[base + gcd];
			str[base] = temp;
	}	
	return str;
}

int getGcd(int aN, int aM)
{
//assert aN > aM
	int remain;
	do{
		remain = aN % aM;
		aN = aM;
		aM = remain;
	}while( remain != 0 );

	return aN;
}
  • 작성한 후
    저장공간을 하나라도 줄이려고 변수를 최대한 안 쓰려고 노력했다. 식이 복잡해졌다. 간단한 임시변수는 써줘야 겠다.

    시프트를 일반화시켜서 생각하고 문제에 접근했다. 하지만 풀리지 않았다. 책을 다시 읽고, 그림을 봐서 무엇을 잘 못 이해했는지 살폈다. 하지만 잘못 이해한 부분은 없었다. 시간이 지나고, 문제를 다시 읽으면 힌트를 얻지 않을까 하는 생각에 문제를 읽었다. 문제에서 최대공약수라는 말을 신경쓰지 않았다는 점을 발견했다. 최대공약수를 이용해서 결국 문제를 해결했다.

    안 되는 방식에 매달리다 보니 슬슬 답답하고 짜증이 났다. 뭔가 아니다는 생각이 자꾸 들었다.

    크게는 같은 알고리즘도 다른 방식으로 접근 할 수 있다.

    막힌다는 느낌이 들면, 문제를 다시 이해해본다. HowToSolveIt에서 나왔던 발제를 스스로 해본다. 이번에는 빼먹고 넘어간 조건이있는가?라는 발제를 빨리 했더라면 해결 할 수 있었을 것이다.

1.2. 손뒤집기 방식

  • Leonardong황재선PairProgramming
  • 30분 걸림
    ~cpp 
    #include <iostream>
    #include <string>
    using namespace std;
    
    void reverse(string & str, int start, int end);
    
    void main()
    {
    	string str = "abcdefgh";
    	int n = str.size();
    	int i = 3;		//shift amount
    
    	int start, end;
    	start = 0;	end = i-1;
    	reverse( str, start, end);
    	start = i;	end = n-1;
    	reverse( str, start, end);
    	start = 0;	end = n-1;
    	reverse( str, start, end);
    	cout << str << endl;
    }
    
    void reverse(string & str, int front, int rear)
    {
    	char temp;
    	while( front < rear ){
    		temp = str[front];
    		str[front] = str[rear];
    		str[rear] = temp;
    		front++;
    		rear--;
    	}
    }
    

1.3. 알고리즘2

미해결
32m소요
~cpp 
#include <iostream>
#include <string>
using namespace std;



void swap(string & str, int start1, int end1, int start2, int end2){
	if ( end1 - start1 == end2 - start2){
		char temp;
		int limit = end1 - start1 + 1;
		for ( int i = 0 ; i < limit ; i++){
			temp = str[start1];
			str[start1] = str[start2];
			str[start2] = temp;
			start1++;
			start2++;
		}
	}
}



int main()
{
	string str= "abcdefg"; 
	int n = str.size();
	int i = 3;			// abc defg
	swap(str,0,i-1, n-i, n-1);
//	swap(str, 0, i-1, n - i, n-1);
//	swap(str, 0, i-1, i, n-i);
	cout << str << endl;
	return 0;
}


2. 후기

황재선

다소 여유를 가지고 PairProgramming 을 했다. 혼자 할때보다 문제 파악이 잘 되었고 뭔가 탁 트인 느낌이 들었다. 아쉬운 점이라면 문제 해결에 너무 매달려서 리펙토링을 게을리한 결과 우아한 프로그램을 완성하지 못했다. 늘 그렇듯이 역할에 맞는 변수명 붙이기는 어렵다. 짧았지만 흥미진진한 시간이었다.


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.6035 sec