IT's me

다이나믹 알고리즘 (동적 계획법) 두 줄로 타일 깔기 (정올)

점화식을 세우는 것이 가장 중요한 부분이란다.

이 문제에 대한 점화식을 미리 알고 들어갔기 때문에

수월하게 풀었다. 즉, 점화식만 잘 세운다면 쉽게 풀 수 있다는 거

다이나믹 알고리즘이라는 게 대충 어떤 것인지는 알 수 있었다.

기존의 데이터를 차곡차곡 저장해 놓고

그 데이터를 바탕으로 값을 계산해 나간다는 것.

다음 문제부터는 다이나믹(동적 계획법)의 핵심인

점화식을 직접 구해보면서 공부해 나가도록 하겠다.

사실 문제를 제대로 읽지않아 20100529 이 부분이 왜 들어가는지 한참 찾았다.

이 것만 아니었어도 3분 내에 해결 됬을 듯..( 당연 점화식을 알고 있었기 때문에)

다이나믹(동적 계획법) 에 대해 맛만 보는 시간을 가졌다.

자 다음문제 점화식을 세우러 go go

문자열 알고리즘 기초 문제

상수 , 다이얼 , 크로아티아 알파벳 (백준)

01. 상수

왜 냈는지 의도를 모르겠다..

기존 문자열 문제보다 상당히 쉽다.

02. 다이얼

알고리즘 기초 문자열 문제 02. 다이얼

처음에 이런 식으로 풀었는데 가독성이 상당히 안좋다.

3중 for문을 썻기 때문에 입력의 크기가 컸다면

상당한 시간복잡도를 보일 것이다.

그래서 다른 사람들은 어떻게 풀었나 보니까

모두 if문 아니면 switch로 풀었더이다.

난 스위치를 좋아하기 때문에 스위치로 한번 더

근데 하드코딩을 하는 듯한 느낌

03. 크로아티아 알파벳

상당히 고민을 많이 했다.

새벽이라 집에 빨리 가고 싶기도 하고

집중도 안되고, 이리저리 해보다가 풀렸다.

함수를 적절히 이용해야겠다는 생각..?

알고리즘 기초 문자열 문제를 풀어보았다.

문자열 문제는 다른게 아니고 항상 형변환에 대해

고민을 안할 수가 없는데, 한번 날잡아서

형변환에 대해 정리하는 시간을 가지겠다.

BFS 알고리즘 경로 찾기 (정올)

살짝 난해한 문제 같았으나

비교적 빠른 시간에 풀었고 한방에 통과~

구조체에 어떠한 변수를 넣을 것인가를 잘 생각해야 하고,

중복된 곳을 다시 큐에 넣지 않게 잘 체크하는 것이

BFS 알고리즘을 푸는 데 있어 가장 중요한 부분인 것 같다.

노드를 잘 만들고 경로 체크를 하고 큐에 넣고 빼고

유효성 체크만 잘 해주면 아주 간단한 문제.

(모든 BFS의 공통된 핵심인 듯 하다.)

01. 변수 선언

BFS 알고리즘을 위한 인큐 , 디큐

02. 초기화

큐가 비었는지 체크하는 함수

그리고 헤밍 경로가 맞는지 체크하는 함수

03. 답을 찾는 함수

1. 큐에 넣고

2. 경로 체크 하고

3. 큐에서 빼고

4. 유효성 검사

04. 메인 함수

BFS 알고리즘은 앞서 말했듯이 구조체를

어떻게 구성할지 빨리 캐치만 한다면

그 후로는 쭉쭉 풀어나갈 수 있을 듯하다.

C++ 디자인 패턴 중 Builder(빌더) 패턴에 대해 알아보자.

빌더 패턴은 추상 팩토리 패턴과 상당히 유사한데,

추상 팩토리 패턴은 부품을 만들고 바로 리턴하는 반면

빌더 패턴은 부품을 만들고 완성된 제품을 리턴한다.

즉, 추상 팩토리 패턴에서 만드는 것은 꼭 모여야만

의미가 있는 것이 아니라 하나만으로 의미가 있는

제품을 생성할 때 쓰는 것이 맞다 할 수 있겠다.

솔직히 말하면 어떠한 패턴인지 그려지기는 하지만

완벽하게 이해하는 수준이 아니라 설명이 매우 허접하다.

빌더 패턴의 이해를 돕기 위해

전에 알아봤던 추상 팩토리 패턴과

비교를 해가면서 알아보도록 하겠다.

추상 팩토리 패턴에서 팩토리 클래스는

추상 클래스로 선언이 되었다. 하지만 빌더 패턴의

Builder에 있는 메서드는 가상함수로 선언하되

구현을 하지 않는 것이 일반적이다.

왜냐하면 서브클래스에서 필요한 메서드만

가져다가 재정의하기 위함이다.

01. 맵을 생성하기 위한 예제

추상 팩토리 패턴에 쓴 예제이다.

02. 추상 팩토리 패턴과는 다르게 빌더 클래스는

메소드 내에서 맵을 어떻게 구성할지를 결정한다.

추상 팩토리에서는 그저 생성하고 리턴만 할 뿐이다.

(부품을 그냥 리턴 : 추상 팩토리)

(부품을 만들고 조립까지 해서 리턴 : 빌더)

따라서 빌터 패턴은 바로 반환하는 것이 아니라

자신의 메모리에 조립이 완성될 때까지 가지고 있다가

완성되면 리턴한다. ( 아래에 계속)

03. 빌더의 서브클래스에서 구체적인 구현이 이루어 진다.

빌더 패턴의 가장 큰 특징은 맵이 어떻게 구성되는지가

빌더 클래스 내에서 캡슐화가 되었다는 것이다.

추상 팩토리 패턴에서는 CreateMap() 내에서

맵을 구성했지만, 그 부분이 이제는 빌더를

상속받는 서브클래스에서 구현하고 있다는 점!

추상 팩토리 패턴과 매우 흡사하지만

흡사해서 더 헷갈리는 느낌이 든다..

뭐가 다른지, 이렇게 해서 서로의 장단점이 무엇인지

언제 이 둘을 구분해서 써야하는지 등등

차라리 완전 다른 패턴이었다면 더 이해하기 쉬웠을 듯

지금 까지 허접한 Builder (빌더) 패턴 포스팅이었다.

알고리즘 기초 문제 - 단어 공부 , 그룹 단어 체커 (백준)

단어 공부 문제는 비교적 쉽게 풀었지만

그룹 단어 체커에서 멘붕

01. 단어 공부

알고리즘 기초 문자열 문제를 풀면서 느끼는 거지만

코드의 순서만 다르게 해줘도 복잡한 부분이 해결된다.

02. 그룹 단어 체커

상당히 짜증나게 했던 그룹 단어 체커

이런 문제가 어떻게 정답률이 60%가 넘는지..

메인 함수 

즐거워야 할 알고리즘 기초문제인데

심기가 불편하다.. 특히나 백준 사이트는

정올 처럼 어떠한 부분이 틀렸는지

볼 수 없기 때문에 걍 빡(?)침

BFS 알고리즘 보물섬 문제 (정올)

BFS는 항상 최단 경로만을 찾는다는 것을 명심하자.

목표지점까지 가는 루트가 많아도, 빙빙 둘러서

가는 경우가 없다. 왜냐하면 모든 루트가 큐에 저장되고

너비 우선탐색으로 진행되기 때문이다.

따라서 목표지점까지 중복된 곳을 방문하지 않으며,

목표지점까지 가는 길이 여러개인 경우

마지막에 비교를 통해 최저값을 찾아주기만 하면 된다.

BFS 보물섬 문제

01. 선언

02. 초기화 , 인큐, 디큐, 유효성 검사, 큐가 비었는지 검사

03. BFS 알고리즘 시작

04. 메인 함수

BFS 알고리즘은 DFS 알고리즘에 비해

이해하기도 쉬울 뿐더러 구현하기도 쉬운 것 같다.

어떠한 문제가 주어졌을 때 두 알고리즘 중에

어떤 것으로 풀어야 할 것인지 잘 캐치해야 할 것이다.

유니티 C# 자료구조 Dictionary (딕셔너리)

C#에는 많은 자료 구조가 있지만, 상황별로 가장

적절한 자료구조를 쓰는 것이 중요하다.

오늘은 게임 개발에서 유용하게 쓰일 수 있는

C# 자료구조 Dictionary에 대해 알아보고

이 자료구조가 왜 유용하지에 대해 알아보겠다.

먼저 여러 자료구조들의 추가, 검색, 삭제, 인덱스 접근에

대한 시간복잡도를 나타내는 표이다. 보시다시피 딕셔너리는

추가, 검색, 삭제 부분에서 상수시간의 시간복잡도를 보인다.

이것만 보아도 딕셔너리의 효율성을 짐작할 수 있다.

간단하게 딕셔너리의 사용법에 대해 알아보도록 하자.

먼저 Dictionary(딕셔너리)는 사용자가 원하는 대로 키를

설정할 수 있는 자료구조이다.  또한 이 키값으로 int뿐만아니라

문자열이나 다양한 변수형을 넣을 수 있다는 점이다.

 인터넷에 좋은 예제가 있어 실습겸 작성해보았다.

01. 아이템 클래스

02. Dictionary (딕셔너리) 선언 그리고 추가 , 검색

03. Dictionary(딕셔너리) 출력 , 삭제, 비우기

딕셔너리는 헤시 테이블과 상당히 유사하지만

헤시 테이블은 자료형에 대한 정의가 없다.

딕셔너리는 자료형을 명확하게 설정하기 때문에

속도면에서 딕셔너리가 좋은 성능을 보인다. (박싱 / 언박싱)

따라서 헤시 테이블 보다는 딕셔너리가 더욱 좋은 경우가 많다.

상황에 맞는 적절한 자료구조의 사용은

게임을 만드는 데 있어 성능향상을 가져오는

상당히 중요한 부분이기 때문에 많은 공부가

필요한 부분이 되겠다. 다음 포스팅은

헤시 테이블이 딕셔너리보다 느린 이유

박싱/언박싱에 대해 알아보도록 하겠다.

C++ UML 다이어그램 중

클래스 다이어그램에 대해 알아보자.

이때까지 C++을 공부하면서 UML 기호를

가끔 접했었는데, 내용 이해에 크게 문제가

되지 않아서 대충 넘어갔었다. 하지만 패턴을

공부하다보니 UML 다이어그램에 대해

꼭 알아야 할 것 같아서 포스팅을 진행한다.

배경지식이나 기본적인 이론에 대해서는 생략하겠다.

UML설계 방식은 제껴두고 클래스들간의

관계에 대해서만 짚고 넘어가겠다.

UML Class Diagram

1. 상속 (Inheritance)

02. 인터페이스 구현 (Interface Implimentation)

03. 연관 (Association)

한 클래스가 다른 클래스를 사용한다. 때문에 두 클래스 사이의

life time은 전혀 상관이 없다. 각각 독립적으로 생성되고

연결이 될 수도, 연결이 되지 않을 수도 있다.

ex)

class Car --------- class Person

class Car {

private:

Person person;

public:

setPerson(Person _p){

this.person = _p;

// setPerson 메소드를 호출해서 사용

}

}

04. 집합 (Aggregation)

Aggregation 관계로 표현되는 전체 객체의 생성 시기가

꼭 동일할 필요는 없다. 소멸시에도 Aggregatin 관계의

클래스들이 다른 객체에 의해 공유될 수도 있다.

ex)

class Car <>------------ class Engine

class Car{

private:

Engine engine;

public:

Car(Engine _e){

this.engine = _e;

// 생성자의 매개 변수로 들어온 놈이

// 꼭 Car과 같이 생성될 필요는 없으며

// 외부에서 생성된 Engine은 다른 객체에서도

// 사용되고 있을 수도 있다.

}

};

05. 구성 (Composition)

객체의 생성과 소멸 시기가 동일하다.

즉 Car 클래스 생성자 내에서 Engine 클래스를 생성한다.

ex)

class Car <<>>------------- class Engine

class Car{

private:

Engine engine;

public:

Car(...){

this.engine = new Engine( ... );

}

};

06. 의존 (Dependency)

객체의 생성과 소멸 시기와는 연관이 없다.

 ex)

Car - - - - - - - - - > Aircon

class Car{

...

public:

void Air( Aircon con){

con.turnOn();

// Aircon 클래스를 인자로 받아 메소드를 내부적으로 호출한다.

// Aircon 의 turnOn 의 정의가 바뀌면

// Car 에 영향을 주게 되므로 의존 관계에 있다고 말한다.

}

};

UML 다이어그램(클래스 다이어그램)에 대해

간략하게 알아보았다. 이 정도만 알고있어도

책에 나오는 UML기호는 어느정도 알아볼 수 있다.

간단한줄로만 알았던 UML 다이어그램이

상당히 복잡하고 덩치가 큰 분야라는 것을 알았다.

다음에 기회가 된다면 좀 더 자세히 알아보는 시간을 가지겠다.

C++ 디자인 패턴 중에 하나인 Abstract Factory

추상 팩토리 패턴에 대해 알아보도록 하겠다.

먼저 추상 팩토리 패턴이란

생성 방법을 알고 있는 객체를 매개변수로

넘겨받음으로써 생성할 객체의 유형을 달리하는 것이다.

(무슨 말인지 모르겠다. 포스팅의 마지막엔 이해가 될 것이다.)

팩토리 패턴의 특징에 대해서는 길게 설명하지 않는다.

추상 팩토리 패턴이 도대체 무엇인지, 어떻게 구현되는지만

코드로서 이해해보는 시간을 가지겠다.

(제대로된 코드는 아니지만 충분히 이해가 될 것이다)

먼저 맵을 만드는 클래스가 있다.

이 클래스는 필드와 장애물을 추가할 수 있다.

또한 이들을 묶어서 맵을 구성하는 MapMgr 클래스가 있다.

위의 코드에는 문제점이 있는데 살펴보면

그렇다. 위의 코드는 유연성과 거리가 먼 하드코딩 되어 있다는 점.

CreateMap()에서 객체를 이름으로 생성했기 때문에

저 함수는 이제 함수 내에서 생성된 객체에 의해

구성된 맵만 반환할 것이다. (재사용성 제로)

자 이제는 CreateMap() 함수 내에서 이름으로

생성하지 않고 팩토리 객체로 생성하고 있다.

따라서 어떤 객체가 들어오느냐에 따라 생성방식이 달라진다는 점.

자 그렇다면 맵의 구성요소들과 팩토리 객체를

추상 클래스로 만들고 파생시켜보자.

(수정) CreateMap()은 맵을 리턴한다.

이제는 추상 팩토리 클래스의 파생클래스 객체를 매개변수로 전달하면

그에 맞는 맵이 생성되게 된다. 위의 관계를 그림으로 나타내면

마지막으로 추상 팩토리 패턴의 단점 하나를 짚고 가겠다.

만약 맵을 만들기 위한 용도가 아닌 곳에서 사용하려 한다면

( 만약 맵이 아니라 몬스터를 찍어내려 한다면)

팩토리의 구현을 변경해야 한다. 이는 추상 팩토리와 모든

서브클래스의 변경을 가져온다. 즉 팩토리는 자신이

생성 할 수 있는 집합에만 고정되어 있다.

지금까지 C++ 디자인 패턴 인 Abstract Factory

추상 팩토리 패턴에 대해 이해하는 시간을 가져보았다.

다음에는 팩토리 메서드 패턴으로 돌아오겠다.

알고리즘의 기초가 되는 문자열 문제를 풀어보겠다.

백준 사이트에 있는 아스키 코드 , 알파벳 찾기, 문자열 반복이다.

01. 아스키코드

말할 것도 없는 문제

02. 알파벳 찾기

문자열을 찾아 체크하는 문제

문자열 체크라 해서 체크 변수를 생각없이

char로 줬는데 상당히 애를 먹었다.

출력하라는 대상의 자료형이 무엇인지 똑바로 보고

제대로 변수를 선언 하도록 하자!

03. 문자열 반복

도대체 뭐가 틀렸는지 알 수가 없다.

20 글자 넘지 마라해서 21 , 20 ,19로 다 체크해도 안되고

실행 시켜서 이것 저것 다 넣어봐도 잘 실행되는데..

기분 팍 상해서 오늘은 퇴근

알고리즘 기초가 되는 문자열

코딩 테스트 단골 메뉴이기 때문에

자주 풀어봐야겠다.