IT's me

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

살짝 난해한 문제 같았으나

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

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

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

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

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

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

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

01. 변수 선언

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

02. 초기화

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

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

03. 답을 찾는 함수

1. 큐에 넣고

2. 경로 체크 하고

3. 큐에서 빼고

4. 유효성 검사

04. 메인 함수

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

그룹 단어 체커에서 멘붕

01. 단어 공부

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

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

02. 그룹 단어 체커

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

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

메인 함수 

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

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

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

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