코딩 테스트 공부
프로그래머스 - 다리를 지나는 트럭
다리 길이(최대 트럭의 개수), 최대 하중, 트럭 무게들
길이 1을 이동하는데 1초
현재 초와 다리에 올라온 트럭 정보, 이미 지나간 트럭 정보가 있어야 하니.. 데이터가 마구 복제되는 BFS로는 어려울 것 같네요.
DFS 말고는 방법이 업으려나?
unordered_map? 다리 위치, 트럭 번호? 아니면 vector로 만들어서 현재 다리에 어느 위치에 트럭이 있는 지 표현?
초 단위로 진행할 경우, 다리 길이 만큼 매번 한 칸씩 이동 연산이 필요
아니면 bitset을 이용해서 몇번째 칸에 뭐가 있다는 식으로 진행하게 해도 될 듯한데..
이동도 << 1 연산으로 한 칸씩 이동시키고 다시 bitset에 넣으면 될 테고... 아 이러면 다리를 완전히 건넜을 때를 따로 처리해 주어야 하는 구나?
이동 전에 bitset.test(bridge_length - 1) == true 이면 이번 실행에서 다리를 건너는 거니 해당 위치의 데이터를 빼내는 걸로...
선입 선출이니 queue를 사용하면 되는 거 같은데?
근데 이러면 queue가 계속 복제될 거 같은데?
아 이거 순서가 정해져 있는 거였네요.
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 그럼 truck_weights에 나오는 순서대로 건너야 한다는 거니..
DFS를 안 써도 되겠네요.
실패 코드 1
#include <string>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
int current_weight = 0;
int current_idx = 0;
queue<int> truck_ins;
bitset<10000> bridge_pos;
answer++;
current_idx++;
bridge_pos.set(0);
truck_ins.push(0);
current_weight += truck_weights[0];
while(!truck_ins.empty())
{
answer++;
if(bridge_pos.test(bridge_length - 1) == true)
{
int out_idx = truck_ins.front();
truck_ins.pop();
current_weight -= truck_weights[out_idx];
bridge_pos.flip(bridge_length - 1);
}
// 한 칸씩 이동
bridge_pos = (bridge_pos.to_ullong()) << 1;
if(current_idx >= truck_weights.size()) continue;
int new_weight = current_weight + truck_weights[current_idx];
if(new_weight <= bridge_length)
{
bridge_pos.set(0);
truck_ins.push(current_idx);
current_idx++;
}
}
return answer;
}bitset으로 매초마다의 위치를 기록하는 방식인데
지금와서 보니 굳이 이렇게 만들어야 했나 싶기도 합니다.
중요한 것은 걸리는 시간이니 위치를 기록할 필요가 없었습니다.
정답도 틀리게 나오고 시간 제한도 넘겨버리는 엉터리 코드가 되었습니다.
다시 생각해보겠습니다.
트럭이 다리를 건너는데 걸리는 시간 = bridge_length
다리에 트럭이 최대로 올라갈 수 있는 수 = bridge_length
근데 어디까지나 무게상 조건을 충족했을 때의 이야기이긴 하지만, 최대로 올라갈 수 있는 수를 걱정하지 않아도 되는 것이.. 어차피 순차로 들어가다보니 bridge_length + 1 번째 차가 올라갈 때는 1번 째 차가 나가는 순간입니다.
필요한 정보를 다시 생각해 봅니다
1. 각 트럭이 다리에 올라온 시간 (마지막 트럭이 올라온 시간 + 다리 길이 가 정답)
2. 현재 다리에 걸리는 하중
3. 다리에 올라간 트럭의 수(무게 하중에 문제가 없다고 해도 다리 길이에 걸려 못 올라갈 수도 있음)
1, 3은 queue로 묶어서 관리하면 될 것 같고 2는 그냥 int 변수 하나면 문제없을 것 같습니다.
실패 코드 2
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
int current_weight = 0;
queue<pair<int,int>> time_in;
for(int i = 0; i < truck_weights.size(); i++)
{
int current_time = i;
while((current_weight + truck_weights[i] > weight) ||
(time_in.size() >= bridge_length))
{
int front_idx = time_in.front().first;
int front_time = time_in.front().second;
current_time = front_time;
time_in.pop();
current_time += bridge_length;
current_weight -= truck_weights[front_idx];
}
time_in.push(make_pair(i,current_time + 1));
current_weight += truck_weights[i];
}
answer = time_in.back().second;
time_in.pop();
answer += bridge_length;
return answer;
}주어진 테스트 케이스는 통과했으나 체첨하니 정답률은 14.3%가 나왔습니다.
음.. 트럭의 출발 시간 제대로 설정한 것 같은데 뭐가 문제 일까요?
실패 코드 3
#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
int current_weight = 0;
queue<pair<int,int>> time_in;
for(int i = 0; i < truck_weights.size(); i++)
{
int current_time = 1;
if(!time_in.empty())
{
current_time = time_in.back().second + 1;
}
while((current_weight + truck_weights[i] > weight) ||
(time_in.size() >= bridge_length))
{
int front_idx = time_in.front().first;
int front_time = time_in.front().second;
time_in.pop();
current_time = front_time + bridge_length;
current_weight -= truck_weights[front_idx];
}
time_in.push(make_pair(i,current_time));
current_weight += truck_weights[i];
}
answer = time_in.back().second;
time_in.pop();
answer += bridge_length;
return answer;
}시간 조건을 잘못 짠 것을 알고 다시 수정을 해보았습니다.
여전히 시간 조건이나 다리가 꽉찼을 때의 예외처리가 잘못되어 있는 것 같습니다.
무게 제햔이랑 다리가 꽉찼을 경우 맨 앞차를 내보내고, 그 시간에 들어갈 수 있게 되니 그대로 사용하는데...
정답 코드
#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
int current_weight = 0;
queue<pair<int,int>> time_in;
for(int i = 0; i < truck_weights.size(); i++)
{
int current_time = time_in.empty() ? 1 : time_in.back().second + 1;
while((current_weight + truck_weights[i] > weight) ||
(time_in.size() >= bridge_length))
{
int front_idx = time_in.front().first;
int front_time = time_in.front().second;
time_in.pop();
current_time = max(current_time, front_time + bridge_length);
current_weight -= truck_weights[front_idx];
}
time_in.push(make_pair(i,current_time));
current_weight += truck_weights[i];
}
answer = time_in.back().second;
time_in.pop();
answer += bridge_length;
return answer;
}while 내에서 다음 차 + 1 보다 작은 값으로 current_time이 덮어씌워질 수 있다는 것을 간과하고 있었습니다.
조금은 수정과 max를 사용해서 정답을 받아내었습니다.
Challenge 분반
Subsystem
=> 생명주기가 명확한 게임 시스템 관리자
Subsystem의 특징
자동 생성/소멸
- Initialize/Deinitialize 자동 호출
- 메모리 관리 걱정 없음
싱글톤 보장
- World 당 하나만 존재
- 중복 생성 방지
접근 용이
- GetSubsystem<
T>로 어디서나 접근 - nullptr 걱정 없음(엔진이 보장)
의존성 명확(접근 용이와 비슷?)
- 타입으로 의존성 표현
- 테스트 용이
언리얼의 서브 시스템 타입
언리얼 엔진에는 3가지 주요 Subsystem 타입이 있습니다.
| 종류 | 생명주기 | 접근 방법 | 사용 예시 |
|---|---|---|---|
| GameInstanceSubsystem | 게임 시작 ~ 종료 | UGameInstance::GetSubsystem() | 세이브/로드, 전역 설정, 통계 |
| WorldSubsystem(가장 많이 사용하는 편) | 레벨이랑 같이 로드~ 언로드 | UWorld::GetSubsystem() | 전투 매니저, 날씨, 시간 |
| LocalPlayerSubsystem | 플레이어 생성 ~ 소멸 | ULocalPlayer::GetSubsystem() | 플레이어별 설정, 입력 |
생명 주기를 고려해서 어떤 것을 사용할 지 결정하면 됩니다.
GameMode vs Subsystem
| 특징 | GameMode | Subsystem |
|---|---|---|
| 존재 위치 | 서버 전용 | 서버 + 클라이언트 |
| 접근 방법 | GetGameMode() (서버만) | GetSubsystem() (어디서나) |
| 역할 | 게임 규칙 정의 | 시스템 관리 |
| 예시 | 점수, 승패 조건, 리스폰 | 전투 상태, 날씨, 퀘스트 |
| 멀티플레이어 | 서버에만 존재 | 서버/클라이언트 각각 존재 |
Subsystem 설계 원칙
서브 시스템은 전역적으로 관리되어야 할 것들을 담당해야 합니다. 특정 액터나 일회성 기능은 굳이 Subsystemd으로 만들 이유가 없습니다.
Good Subsystem
- 상태 관리
- 전투 상태, 날씨, 시간, 난이도
- 이벤트 중계
- 메시지 시스템, 옵저버 패턴
- 리소스 관리
- 오브젝트 풀, 리소스 캐싱
Bad Subsystem
- 특정 Actor 로직
- Character의 공격 로직 → Character에 작성!
- UI 로직
- Widget 업데이트 → Widget에 작성!
- 일회성 유틸리티
- 단순 계산 함수 → Static 함수로 충분!
강의를 들으며 작성하 내용(검토 필요)
우리가 서브 시스템을 상속받아서 만들면 실제로 자동으로 생성이 되고 소멸이 됩니다.
하지만 서브 시스템 안에 특정한 데이터를 넣고 싶을 경우 그 데이털르 서브 시스템이 읽을 수 있도록 세팅을 해주어야 합니다.
추가적인 데이터가 서브시스템에 필요한 경우, 경로 자체를 지정하는 것을 추천합니다. 이 경로는 보통 에디터에서 집어넣게 됩니다.
문제는 경로가 변경될 때마다 새로 넣어주지 않으면 비어버려서 오류를 야기할 수도 있고, 자동 생성할 경우 에디터에서 넣어주는 그 데이터를 읽을 수 없다는 겁니다. 왜냐하면 아직 없으니까요.
때문에 호출되는 시점에 따라 데이터 유무가 달라집니다.
DefaultEngine.ini에 경로를 지정해놓고, initialize 시에 어떤 파일을 읽어올지 지정하게 할 수 있습니다.
생명주기를 따로 관리하는 형태로 만드는 것보다는 경로를 따로 넣어주는 편이 낳은 것 같다는 것이 튜터님의 의견이었습니다.
오늘 할 것은 UI랑 연동되는 서브 시스템
공격 시 전투 모드, 일정 시간 후 일반 모드로 전환 - 이 기능을 서브 시스템으로 구현
localplayersubsystem
-> EnhancedInputLocalPlayerSubsystem
상태머신으로 구현되어 있어서 새로운 상태에 대한 정의 및 처리를 작성해 주어야 해서 아주 복잡하다?
Manger 사용 자제
Manager라는 이름의 클래스를 만드는 것은 지양해야 합니다. 뭐든 Manager를 붙일 수 있기 때문에 자칫 무슨 역할을 하는 지 파악하기 어려워 질 수 있습니다.
UIManager -> 어떤 UI? 모든 UI를 촐괄하는 것인가?
CombatManagerSubsystem
Initialize(), Deinitalize() 재정의 - 필수
전역 상태 정의
전역 상태를 Broadcast 하는 함수 작성
Broadcast를 받아 동작하는 UI 구현
클라이언트에서 오는 정보는 우선 의심부터하고 보자
서버에서는 시작 시간과 끝만 체크
매 번 서버에서 브로드케스트하는 것은 낭비
가장 편한 방법은 플레이어 전체의 시간이 지나는 속도의 평균을 잡고 그 평균을 기준으로 오차 허용값을 구한다.
그 뒤 앞으로 통신 중 호차 허용값보다 늦다면 그 요청은 처리하지 않는다.
플러그인에 있는 것은 플러그인 안에서만 사용할 수 있도록 만들어 두는 것이 좋습니다.
Build.cs에서 명시해 주는 것으로도 사용이 가능하긴 한데 의존성 문제로 꼬여서 문제가 생길 위험이 있습니다
엔진에서 World가 호출되는 시점과 서브시스템이 호출되는 시점을 비교하면 World의 유무 체크 필요성이 보인다.
일반적으로는 필요없지만, 서브시스템에 추가적인 데이터를 지정해서 넣어줬을 경우 같이 초기화가 되어야 할 경우에는 null check가 필요합니다.
Unreal Engine 멀티플레이어 게임 개발
챕터 7 동기화
BP_PlayerCharacter > Details > Replicate Movement 속성을 true로 설정하면 애니메이션 블루프린트에서 사용하는 변수들도 동기화된 값으로 얻을 수 있습니다.
노티파이 중복 방직
노티파이 Details -> Category -> Event -> Montage Tick Type
Queued
- 쌓아두고 실행하는 방식, 확실한 실행이 보장되지 않음
- 나중에 실행 가능해지면 실행해도 됨.
Branch Point
- 무조건적인 실행
- 노티파이가 배치된 틱에 맞춰서 곧바로 실행될 수 있게함.
팀 회의 중 나왔던 내용 중 공부할 것
git lock
git lfs lock 경로
서버에 경로의 파일에 대한 잠금을 걸 수 있습니다.
이 lock이 에셋을 건드리면 알림이 뜬다?
서버에 락이 걸리지만 fetch 등으로 변화를 받지 않은 로컬 레포지터리에서는 알 수 없음. 후에 푸시나 머지시에 알려줍니다.
revision control
연동해 놓으면 에셋에서 충돌이 나도 변경 사항 같은 것을 엔진에서 다 확인이 가능해서, 작업 내용을 보면서 커밋이 가능합니다.
