IT's me

백트래킹 알고리즘 알파벳 문제 (백준)

난이도가 어려운 편은 아니었지만

아직 재귀에 대해 익숙하지 않은 듯 하다.

좀 더 연습해서 이러한 문제는 10분 대에

해결할 수 있도록 해야겠다.

말이 지나온 알파벳을 저장해두고

중복된다면 다시 돌아가는 것이 포인트

이번 주 까지는 백트래킹과 기초적인 문제를

많이 풀어보고 다음 주 부터 BFS를 들어가도록 하겠다.

백트래킹 알고리즘 부분집합의 합 (백준)

처음부터 답을 참고하고 들어가니 쉽게 풀린듯 하다.

이제는 어떠한 문제가 백트래킹 문제라는 것을

빨리 캐치하는 연습이 필요한 것 같다.

지금까지 풀어봤던 백트래킹 문제치고는

난이도가 상당히 낮은 편이었다.

그래도 백트래킹의 대표적인 문제라고하니

좀 더 들여다 볼 필요가 있는 것 같다.

쉬운 문제인데도 30분이 걸렸다.

좀 더 분발하자.

알고리즘 기초 수열 (정올)

오름차순으로 한번 내림차순으로 한번

따로따로 함수를 만들어 값을 카운트하고

마지막에 비교해서 큰 값을 출력

01. 오름차순 카운트 , 내림차순 카운트

02. 초기화 한 후, 함수를 호출해서 값을 얻어냄

알고리즘 기초, 이러한 기초적인 문제를

많이 풀어봐야 할 듯하다.

내부에서 사용하는 객체에 대한 핸들을

반환하는 코드는 되도록 피하자.

사각형의 좌측 상단, 우측 하단의 꼭짓점을

추상화한 Rec 클래스가 있다.  꼭짓점을

Rec클래스에 넣지 않고 별도의 구조체에

넣은 후 Rec가 이 구조체를 가리키도록 만들었다.

class point{

int x,y;

...

};

struct RecData{

point ulhc;

point lrhc;

};

class Rec{

tr1::shared_ptr<RecData> pData;

...

};

Rec 클래스의 사용자는 꼭짓점의 정보를

얻을 수 있어야하므로 멤버함수를 정의한다.

class Rec{

public:

point& upper() const (return pData->ulhc;}

point& lower() const (return pData->lrhc;}

}

함수들이 모두 const로 선언되어 있으나

함수안에서 리턴되는 참조자에 의해

값이 변경될 수 있다. ulhc, lrhc는 Rec의

멤버가 아니기 때문에 충분히 가능하다.

1. 클래스 데이터 멤버는 아무리 숨겨봤자 그 멤버의

참조자를 반환하는 함수들의 최대 접근도에 따라

캡슐화 정도가 정해진다.

2. 어떤 객체에서 호출한 상수 멤버 함수의 참조자

반환 값의 실제 데이터가 그 객체의 바깥에 저장되어 있다면

이 함수의 호출부에서 그 데이터의 수정이 가능하다.

참조자 뿐만 아니라 포인터, 반복자는 모두 핸들이다.

외부 공개가 차단된 멤버 변수 뿐만 아니라 멤버 함수에

대해서도 이들의 핸들을 반환하는 멤버 함수를 만들지 않아야 한다.

const point& upper() const (return pData->ulhc;}

const point& lower() const (return pData->lrhc;}

위의 문제는 이와 같이 const를 붙여주면 해결된다.

무효참조 핸들

객체를 참조자로 반환 했을 때

그 객체가 함수 내에서 선언된

지역 객체라면 함수가 종료됨과 동시에

없어지게 된다. 따라서 반환값을 받는

변수는 없어진 객체를 받게 된다.

핸들을 반환하는 것은 const를 붙였다해도

바깥으로 떨어져 나간 핸들은 그 핸들이 참조하는

객체보다 오래 살 위험이 있다. 따라서 핸들을

리턴하는 것은 되도록이면 피하도록 하자.

POINT!!

어떤 객체의 내부요소에 대한 해들을 반환하는 것은 되도록 피하자.

여러가지 1 문제 빙고 (정올)

간단한 문제인 줄 알았지만, 상당히 코드가 길다.

내가 좀 비효율적으로 푼 것 같기도 하다..

가로, 세로, 크로스로 체크하는 함수를

따로 두어서 그 함수에서 체크된 빙고 수를 리턴

입력, 출력 등등 여러가지

알고리즘을 풀기 전에 기초부터 제대로 잡고 들어가야 할 것 같다.

그리고 코딩 테스트에서 알고리즘보다 이러한 문제 풀이형식의

문제가 더욱 많이 출제 되는 것 같다. 분발하자.

문자열 관련 문제 02 (정올)

비밀 편지, 단어 집합(하), 소수문자열, 단어세기

01. 비밀 편지

02. 단어 집함(하)

03. 소수 문자열

소수를 체크하는 부분에서 좀 더 효율적인 코드를 생각해보자.

04. 단어 세기

경고가 뜨는 이유에 대해서 좀 더 생각해보자.

변수의 정의는 늦출 수 있는 데까지 늦추는 근성을 발휘하자.

비밀번호가 충분히 길 경우에 해당 비밀번호를

암호화하여 반환하는 함수가 있다.

string encryptPassword ( const string& password){

string encrypted;  // 1번

if(password.length() < MinimumPasswordLength) {

throw logic_error ("Password is .... ");

}

//2번 string encryped

...  // 암호화 진행부분

return encrypted;

}

1번의 경우 encryped 객체는 길이 점검에서 예외가 던져지게 되면

안 쓰여질 확율이 있다. 따라서 불필요한 생성자 소멸자

비용을 지불하게 된다. 2번의 경우는 위와 같은 불필요한

비용을 지불하진 않지만 기본생성자가 호출된 후에

또 다시 대입을 해야하는 구조이기 때문에 여전히

비용에 대해 자유로울 수 없다.

void encrypt(string &s);

위 함수에서 암호화를 진행한다고 할 때

string encryptPassword ( const string& password){

if(password.length() < MinimumPasswordLength) {

throw logic_error ("Password is .... ");

}

string encrypted(password);

encrypt(encrypted);

return encrypted;

}

encrypted가 생성될 때 매개변수로 들어온

password로 초기화가 되고 있다.

변수의 정의를 늦줘서 기본생성자 호출

그리고 대입에 대한 불필요한 비용을 

최소화 하고 있다.

루프에 대해선 어떻게 해야 할까?

1번.

widget w;

for( ... ){

w = i;

}

2번.

for( ... ){

widget w(i);

}

1번의 경우 생성자와 소별자가 1번씩 호출되며

대입이 여러번 일어나고 있다. 2번의 경우에는

생성자와 소멸자의 호출이 여러번 일어나고 있다.

대입에 들어가는 비용이 생성자 소멸자 쌍보다

적게나오는 경우 1번 방법이 좋다. 하지만 A는

w의 유효범위가 넓어지기 때문에 프로그램의

이해도와 유지보수성이 역으로 안좋아질 수 있다.

POINT!!

변수 정의는 늦출 수 있을 때까지 늦추자.

알고리즘 기초 문자열 문제 (정올)

1. 그릇

2. 문자열 찾기

3. 문자열 변환

알고리즘 테스트에 자주 등장하는 것이 바로 문자열!

그래서 오늘부터 문자열에 대한 문제를 풀어보기로 했다.

01. 그릇

03. 문자열 변환

02. 문자열 찾기

백트래킹 알고리즘 02 해밀턴 순환회로

답은 다 맞았지만 시간초과..

그래도 푸는 시간이 N queen 보다 대폭 줄었다.

다음엔 재귀가 아닌 스텍으로 풀어보겠다.

01 선언 및 초기화

02 재귀 함수 호출

03 답 출력 그리고 메인 함수

백트래킹도 대충 어떤 느낌인지 알겠다.

익숙해지기만 하면 될 듯하다.

멤버 함수 보다는 비멤버 비프렌드 함수와 더 가까워지자.

웹브라우저를 나타내는 클래스가 있다.

이 클래스에는 캐시를 비우는 함수, URL 기록을

없애는 함수, 쿠키를 제거하는 함수가 있다.

이 세 동작을 한꺼번에 하고 싶은 사용자를 위해

세 함수를 불러주는 함수도 준비해 둘 수 있을 것이다.

class Web{

private:

...

public:

...

void clearEverything();

}

위와 같이 멤버함수로 제공해도 되지만,

비멤버 함수로 제공해도 된다.

void clearWeb(Web& wb){

wb.fct1();

wb.fct2();

...

}

멤버 버전인 경우 Web 클래스의 private 멤버에

접근할 수 있다. 따라서 캡슐화의 정도가 낮아진다.

반면 비멤버 비프렌드 함수일 경우 Web클래스의

어떠한 private 멤버에 접근할 수 없다.

또한 패키징 유연성과 확장성을 높히는 동시에

컴파일 의존도도 낮출 수 있다.

주의해야 할 점은 함수는 어떤 클래스의 

비멤버가 되어야 한다는 말이 그 함수는

다른 클래스의 멤버가 될 수 없다라는 의미가

아니라는 것이다. 위의 clearWeb라는 함수는

다른 클래스의 정적 멤버함수로 만들어도 된다.

(Web클래스의 멤버만 아니면 됨)

더 나아간 방법 --> 같은 네임스페이스 안에 두는 것

namespace WebStuff {

class Web { ... };

void clearWeb(Web& wb);

...

}

네임스페이스는 클래스와 달리 여러 개의

소스 파일에 나뉘어 흩어질 수 있다.

clearWeb같은 함수는 편의상 준비한 함수들

이기 때문에, 이 함수가 없다해도 사용자는

각각의 함수들을 따로 호출하면 된다.

편의 함수가 많이 생길 수 있는 클래스라면

연관이 있는 편의 함수를 하나의 헤더 파일에

몰아서 선언하고, 같은 네임스페이스에 넣어주자.

//"web.h"

namespace WebStuff {

class Web { ... };

...

}

//"bookmark.h"

namespace WebStuff {

...

}

//"cookies.h"

namespacce WebStuff {

...

}

이렇게 하면 필요한 기능에 대해서만

include해서 사용하면 되기 때문에

필요없는 기능들에 대한 컴파일 의존도를

낮출 수 있다. 클래스의 멤버함수일 경우

이런 식으로 기능을 쪼개는 것 자체가 불가능하다.

하나의 클래스는 그 전체가 통으로 정의되야 하고

여러 조각으로 나눌 수가 없기 때문이다.

편의 함수 전체를 여러 개의 헤더 파일에

나누어 놓으면 확장도 손쉬워진다.

해당 네임스페이스에 비멤버 비프렌드 함수를

원하는 만큼 추가해주면 끝난다.

POINT!!

멤버 함수보다는 비멤버 비프렌드 함수를 자주 쓰도록하자.

캡슐화 정도가 높아지고, 패키징 유연성도 커지며, 기능적인 확장성도 늘어난다.