IT's me

BFS 알고리즘 저글링 방사능 오염 문제 (정올)

BFS에서 좀 난해한 부분이라 하면

큐의 사이즈를 얼마로 해줄 것인가.

경우의 수를 다 따져서 큐의 사이즈를

정해줘야 하니 이것 또한 생각해봐야 할 문제.

그리고 이 문제를 풀면서 느낀점은

좌표에 대한 개념에 좀 더 익숙해져야 할 것 같은..

01. 저글링 구조체 선언

그리고 BFS 알고리즘을 위한 큐 관련 함수

02. 유효성 검사와 큐가 비었는지 검사

03. 큐를 하나씩 빼면서 탐색

또한 탐색해야할 부분에 대해서

큐에 차곡차곡 쌓아두자.

04. 메인 함수

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

손이 많이 간다는 느낌이 든다.

하지만 뭔가 문제가 깔끔하기에 맘에 든다.

BFS 알고리즘 장기 문제 (정올)

첫 BFS문제이다. 확실히 DFS보다는 쉽게 느껴진다.

하지만 90점.. 그래도 첫 문제니 원리를 알았다는 거에

만족하며 이 문제는 여기서 마무리..

01. 구조체를 선언하고 초기화 한다.

또한 BFS 알고리즘은 큐가 핵심 원리이기 때문에

큐에 저장하는 함수 큐에서 빼내는 함수를 정의

02. 장기 말이 장기판 밖으로 나갔는지

혹은 지나왔던 곳을 또 밟았는지를 체크

03. BFS 알고리즘의 핵심 원리인 큐를 이용하여

노드를 큐에 넣고 빼고를 반복하며 답을 찾는다.

DFS를 할 때는 구정물에 발을 담그는 느낌이었는데

BFS 알고리즘은 그보단 훨씬 깔끔한 느낌이다.

유니티 C# 싱글턴 오브젝트

게임 내에서 클래스 인스턴스들은 여러개 생성된다.

몬스터, 아이템만 봐도 하나의 씬에 여러개 존재 할 수 있다.

하지만 게임 매니저, 스코어, 오디오, 저장 등을

관리하는 몇몇 클래스들은 유일한 독립체로 존재해야 한다.

하나의 클래스 인스턴스만 존재하게 되며 그보다

많은 인스턴스를 만들지 않는다. 하나보다 많은

인스턴스를 가지는 것은 모순적인 부분이 발생하거나

오브젝트의 역할을 망가뜨리고 쓸모없어질 수도 있다.

이런 종류의 오브젝트를 싱글턴이라 부른다.

싱글턴은 대게 여러 씬에 걸쳐 지속적으로 유지되는 오브젝트이다.

싱글턴 기본 요소

항상 메모리에 클래스 인스턴스가 하나만 존재해야 한다.

tip!

이처럼 씬 간 유지되는 오브젝트는 자식 없는 빈 게임오브젝트처럼

동작에 필요한 기본 컴포넌트로만 구성해 가볍게 만들어진다.

씬을 전환할 때 중요한 필수 데이터만 살아남도록 하는 전략이다.

위 클래스 인스턴스는 이제 씬이 전환되어도 사라지지 않는다.

하지만 게임의 씬이 순차적으로 진행되리라 보장되진 않는다.

따라서 이 매니저클래스가 생성된 씬으로 다시 오게 된다면

매니저 클래스 인스턴스가 두개가 생기게 되고, 문제가 발생한다.

싱글턴으로 만들어주자.

유일한 인스턴스(싱글턴)일 뿐만 아니라 모든 인스턴스에

공유가되는 변수가 되었다. 이 변수는 get 멤버만을

가지고 있는 읽기 전용 프로퍼티를 통해 외부에서 접근 가능하다.

tip!

Awake()와 Start()

Awake()는 항상 오브젝트 생성 시에 호출된다.

Start()는 게임오브젝트가 활성화되는 첫번째 프레임에

호출된다. 만약 게임오브젝트가 비활성화된 씬에서

시작되었다면 오브젝트가 활성화되어 있더라도

Start()는 호출되지 않는다.

호출 순서 Awake() -> Start()

트랜스폼 컴포넌트를 변수에 캐싱하려면

Start()보다는 Awake()를 쓰는 것이 좋다.

일반적으로 Start() 이벤트가 일어날 때엔

오브젝트에 대한 모든 지역 참조들이

이미 할당되어 유효하다고 가정된다.

C++ 디자인 패턴 : Strategy 패턴 (전략 패턴)

게임 캐릭터의 체력 구현 알고리즘을 만들고 있다고 가정하자.

기본 플레이어는 기본 체력 구현 알고리즘을 가지고 있을 것이다.

이 플레이어가 전직을 하여 전사가 되면 방어력이 더욱 강해질 것이고,

마법사로 전직을 하게 되면 방어력이 더욱 약해질 것이다.

위의 방법은 너무나 일반적인 설계이다. 하지만 여기서 캐릭터의 

알고리즘의 변경과 알고리즘 자체를 개조할 수 있는 방법이 없을까.

예를 들어 캐릭터가 너프 마법이나 버프 마법을 받게된다면

체력 구현 알고리즘이 달라져야 할 것이다. 전략 패턴을 써보자.

알고리즘을 클래스로 만들어 가상함수를 선언했다.

따라서 이를 상속하는 모든 클래스들은 이 함수를

재정의 할 수 있다. (알고리즘의 조정/개조가 가능해짐)

또한 이 알고리즘의 포인터를 가진 Player클래스는

언제든 체력 알고리즘을 바꿀 수 있는 융통성이 생기게 된다.

이 패턴의 핵심은 한쪽 클래스 계통에 속해 있는

가상 함수를 다른 쪽 계통에 속해 있는 가상 함수로 대체한다는 것이다.

DFS 알고리즘 적록 색약 (백준)

런타임 에러..

예제는 정답이고 내가 임의로

입력해봐도 맞는 값이 나오는데

런타임 에러가 뜬다. 다른 사람들의

답을 참고해봐도 비슷한거같은데..

새벽이라 고칠 의욕도 안나고..

01. 초기화

02. 답 찾기

이번 DFS 알고리즘은 답을 찾는 데 꽤 오래 걸렸다.

단지 번호 붙이기와 상당히 유사한 문제였지만

두 가지의 답을 찾아야 했기 때문에 한번의 호출로

답을 찾아야 할지, 아니면 나누어서 찾아야 할지

고민을 많이 했던 것 같다.

아무튼 BFS 알고리즘은 많이 풀어보는게 답인거 같다.

C# 프로퍼티

프로퍼티(Property)는 속성이라는 의미를 지니고 있다.

멤버 변수를 속성이라고도 하는데 정보 은닉을 위해

private로 선언을 하면 get, set 메소드를 구현해야 한다.

이를 편리하게 해주는 것이 C#의 프로퍼티이다.

C# 프로퍼티는 간단하고 유연성있게 전용 필드의

값을 읽거나 쓰는 메커니즘을 제공한다.

1. set 접근자의 value키워드는 set 접근자가 할당하는 값을

정의하는 하나의 예약어이다. 따라서 set 안에서만 유효하다.

2. set 접근자만을 구현하면 쓰기 전용 , get 접근자만을 구현하면

읽기 전용이다. private으로도 구현 가능하다.

3. get , set, 내에서 각종 조건을 걸어줄 수도,

혹은 사전 조건, 사후 조건을 프로퍼티 내에서 구현할 수도 있다.

4. 주의 사항!

변수와 프로퍼티의 이름은 같아야 하고 대 소문자로 구분한다.

자동으로 구현된 프로퍼티

1. get , set 접근자 안에 아무것도 안쓰는 경우 프로퍼티 자체를 사용한다.

2. private로 접근 지정을 해줄 수 있어 유연하게 사용가능하다.

NVI idiom

(non-virtual-interface idiom)

템플릿 메서드 패턴을 C++ 식으로 구현한 것이다.

간단한 패턴이니 예제를 통해 바로 보도록 하겠다.

가상 함수는 반드시 private 멤버로 두어야 한다는

가상함수 은폐론이 기초가 된 기법이다.

가상합수를 private으로 두면 이를 상속하는 클래스는

재정의는 할 수 있지만 실제 호출은 할 수없다.

호출을 하려면 hpValue() 라는 함수를 거쳐야 하는데

이것이 바로 NVI 관용구의 핵심이다.

여기서 hpValue()는 가상함수의 랩퍼라고 부른다.

hpValue()를 호출하게 되면 가상함수를 호출하기 전에

사전 동작이 가능하며 가상함수 호출 후 사후 동작도 가능하다.

또한 재정의가 가능하기 때문에 구현의 자유가 있지만

이 함수를 호출하는 시점은 기본 클래스의 고유권한으로 묶인다.

꼭 가상함수가 private여야 한다는 것은 아니지만

protected나 public멤버라면 NVI를 적용하는 의미가 없다.

pimpl idiom

컴파일 의존성을 줄이기 위한 하나의 설계 기법이다.

많이 쓰여지는 기법 중 하니이기 때문에 거의 패턴으로 굳어져 있다.

include가 필요한 사용자 정의 타입의 멤버 변수들을

해당 멤버 변수들을 포함한 클래스(구조체)의 포인터로 대체하는 방법이다.

이런 형식의 문제점은 헤더파일 내에서 다른 헤더파일을

include하고 있다는 것이다. include를 하게 되면 전처리기는

해당 헤더의 내용을 그대로 복사해서 집어넣는다. 그렇다면

AAA.h를 include하는 모든 cpp 파일에 AAA.h가 include하는

모든 헤더가 포함되게 되므로 코드량이 매우 커진다.

따라서 컴파일 시간이 늘어난다.

또한 myString같은 유저 정의 클래스의 경우

내용이 바뀔 가능성이 매우 높다. myString의

내용이 바뀐다면 AAA.h는 물론 AAA.h를 포함하는

모든 파일도 다시 재컴파일 될 수 밖에 없다.

pimpl idiom을 통해 해결해보자.

include가 필요한 멤버 변수들을 모아 Aimpl 구조체에 저장하자.

그리고 그 구조체에 대한 포인터를 멤버 변수로 들고 있는다.

Aimpl 구조체 정의는 cpp 파일로 미룬다.

여기서 중요한 점은 cpp파일의 include는

오직 해당 cpp 파일에만 영향을 미친다는 것이다.

따라서 위의 코드는 헤더파일의 include를

구현파일로 모두 보내버렸다는 것이 포인트다.

한 걸음 더 나아가 tr1의 shared_ptr을 사용해서

구현을 한다면 더욱 좋은 설계가 될 것이다.

물론 AAA의 소멸자에서 delete연산을 해주지 않아도 된다.

구조체가 아닌 클래스로 pimpl을 구현해보자.

필요한 클래스를 전방 선언 후 Person 클래스 선언 내에서

참조자 혹은 포인터의 정의 그리고 값의 전달 및 반환

그야말로 인터페이스와 구현이 뼈와 살이 분리되듯 떨어진다.

이러한 방법은 pimpl idiom 외에도 인터페이스 클래스를

설계하는 방법도 생각해볼 수 있으나, 패턴으로 볼 수 없기 때문에

후에 C++ 카테고리에서 포스팅하도록 하겠다.

DFS 알고리즘 단지 번호 붙이기 (백준)

DFS 문제이다. 재귀를 사용해서 풀었다.

원래는 메인에서 재귀함수를 한번 호출하고

재귀 함수 내에서 모든 작업을 다 하는 방식으로

진행하려 했지만, 메인에서 반복문으로 재귀를 불러주니

문제가 상당히 쉬워졌다.. 그래도 여전히 25분

01. 초기화

02. 재귀 함수 호출 및 답 출력

DFS 알고리즘을 풀면서 비용적인 측면까지도

생각해볼 때 인 것 같다. 위의 문제는 메인에서

하나하나 호출을 하는게 상당히 비효율적으로 보인다.

하지만 테스트는 푸는 시간 또한 중요하기에

이러한 방법으로 계속 푸는 연습을 해야겠다.

DFS 알고리즘 경로찾기 (백준)

DFS 문제이다.

재귀를 사용해 풀었지만 시간초과..

때문에 답이 맞는지도 모르겠다.

적어도 예제는 다 맞았으니 올려본다.

다음엔 스택을 이용해 풀어보겠다.

예전 같은 경우 재귀를 이용해 DFS를 풀 때

재귀 함수 내에서 모든 것을 끝내려 했다.

사실 그게 큰 부담이 되었는데, 메인 함수에서

재귀를 여러번 불러주는 식으로 진행을 하니 한결 수월했다.

비용적인 측면에 대해서도 고민해볼 시기인 것 같다.

열공합시다!