오늘은 Attach 기능 중에서 Piece와 관련된 기능들을 9할? 정도 구현을 마무리했습니다.

 

우선 Attach Replicate는 Replicate Movement에 RPC함수를 Attach를 Character에 RPC로 감싸서 해결을 보았습니다.

물론 Replicate Movement도 중요했지만, 가장 중요한건 Character에서 RPC를 제공하는 것 같습니다.

RPC 함수를 사용하지 않았던 것은 아닙니다.

다만 Piece에서 제공을 했었는데 Piece에서 제공하면 문제를 해결할 수 없었습니다.

 

그 다음 문제는 Piece가 Attach 된 이후 이를 Detach 하면 원래 장소에서 나타나는 문제였습니다.

이는 확인해보니 FAttachmentTransformRule이 잘못되어서 그런 것이었습니다.

Actor의 Socket에 Snap 하도록 설정하면서 문제는 해결되었습니다.

 

그럼에도 1할 정도 남은 것은 두가지 문제가 남았기 때문입니다.

하나는 움직이면서 Actor가 Mesh를 막아서 움직임이 부자연스럽다는 점.

특히 Host에서는 움직임 자체가 기괴하고 조종 할 수 없게 왜곡되어버립니다.

최종적으로 Dedicate Server로 구현할 것이기에 Host에서의 문제는 미뤄두고,

일단 Actor가 Attach 될 때 크기가 줄어들도록 해보려 합니다.

물론 Detach 될 때는 크기가 늘어날 것입니다.

 

다른 문제는 Client에서의 끊김 문제입니다.

부자연스러운 움직임에 포함될 수도 있으나,
Replicate 동기화를 매 Tick마다 하면 부하가 걸린다는 얘기를 들었기에 이것이 원인이지 않을까 싶기도 합니다.

그래서 Replicate 동기화를 좀 더 드문드문 발생하도록 하는 것을 찾아보고, 적용할 계획입니다.

'개발일지 > Treasure Hunter' 카테고리의 다른 글

20.08.06 개발일지  (0) 2020.08.06
20.08.05 개발일지  (0) 2020.08.05
20.08.02 개발일지  (0) 2020.08.02
20.08.01 개발일지  (0) 2020.08.01
20.07.30 개발일지  (0) 2020.07.30

조건문을 수정해서 어느정도 동작은 하도록 만들었습니다.

하지만 일부 기능은 여전히 제대로 돌아가지 않았고,

무엇보다 Client에서 Attach한 것이 Server에는 정상적으로 적용되지 않았습니다.

 

이는 아무리 봐도 Replicate가 되지 않는 것으로 Attach의 Replicate를 처리하기 위해 이리저리 고민을 해보았습니다.

하지만 Attach/Detach에서 요구하는 Struct가 UStruct가 아니라서 UFUNCTION의 parameter가 될 수 없었고, 

이것이 모든 해결방안을 막고 있었습니다.

 

하루 종일.

말 그대로 24시간 고민을 하다가 Attach Replicate라는 것을 발견하였으나 정확히 파악하지 못했고, 

커뮤니티에 질문을 올렸는데 마침 이 문제를 잘 아는 사람이 답변을 해줬습니다.

 

정리하자면 다음과 같습니다.

1. Attach는 Movement Replicate가 보장되면 저절로 동기화 된다.

2. 다만 Attach가 Movement Replicate이면 Attach 된 후 Object의 움직임에 복잡한 연산이 Tick마다 발생한다.

3. 그러니 Attach는 Replicated로 해두고 Attach된 후에 움직임을 10 Tick에 한번 발생하는 정도로 빈도를 줄여야 한다.

4. Attachment는 RPC로 묶어야 한다.

 

결국 제 입장에서는

1. Attach를 Movement Replicate를 해두고, Attach가 된 후에는 이를 해제한다.

2. Object에 Attach가 붙으면 Tick 발생 빈도를 조금 줄인다.

3. Character에 RPC 함수를 만들어 Attach 관련 함수를 묶는다.

 

이정도로 해결을 해야 할 것 같습니다.

되는지는 해봐야 알겠지만 일단 이렇게 해보려 합니다.

'개발일지 > Treasure Hunter' 카테고리의 다른 글

20.08.05 개발일지  (0) 2020.08.05
20.08.03 개발일지  (0) 2020.08.03
20.08.01 개발일지  (0) 2020.08.01
20.07.30 개발일지  (0) 2020.07.30
20.07.29 개발일지  (0) 2020.07.29

오늘은 Attach 기능을 요구하는 AttachPiece, AttachLatch, Character의 Attach 기능의 Script를 작성하였습니다.

작성하면서 여러 종류를 고민하다보니 시간이 많이 흘렀지만, 그래도 하루만에 코드 부분은 대략 작성할 수 있었습니다.

하지만 실제로 테스트를 해보니 정상적으로 작동하지는 않았습니다.

그래서 다음에는 로그를 찍어보고 문제가 되는 부분을 탐색하여 수정하는 작업을 진행해야 할 것 같습니다.

 

왠지 새벽에 조금 해주면 주말 안에 끝날법도 해서 뭔가 안심이 된달까.

반환점이 하나 보이는 것 같습니다.

8월에는 리빌딩을 꼭 마무리 하고, 했던 작업이 아닌 안해봤던 작업.

데디케이트 서버 구축 단계로 넘어가고 싶습니다.

'개발일지 > Treasure Hunter' 카테고리의 다른 글

20.08.03 개발일지  (0) 2020.08.03
20.08.02 개발일지  (0) 2020.08.02
20.07.30 개발일지  (0) 2020.07.30
20.07.29 개발일지  (0) 2020.07.29
20.07.27 개발일지  (0) 2020.07.27

오늘은 DirectX 예시 프로젝트 수정 중 발생한 오류 원인을 찾아보았습니다.

 

결과적으로, 오류의 원인을 밝힐 수는 없었지만 한가지 오류는 찾았습니다.

https://docs.microsoft.com/en-us/windows/win32/api/dxgi/nf-dxgi-idxgifactory-createswapchain

 

IDXGIFactory::CreateSwapChain (dxgi.h) - Win32 apps

Creates a swap chain.

docs.microsoft.com

https://gamedev.stackexchange.com/questions/149822/direct3d-12-cant-create-a-swap-chain

 

Direct3D 12 can't create a swap chain

I'm learning DirectX12 and I'm trying to create a simple application that clears the screen with a solid color, but I'm stuck in Direct3D initialization. I can't create the swap chain and the DXGI

gamedev.stackexchange.com

CreateSwapChain에서 문제가 발생했는데 최신 버전에서는 이 함수 사용을 지양한다는 내용입니다.

그래서 다른 방식으로 구현을 했는데, 여전히 문제가 발생하고 있습니다.

 

그래서 좀 더 근본적인 부분을 먼저 수정해보려 합니다.

바로 Window 생성 부분입니다.

DirectX 예시 코드와 Windows Template 예시 코드는 각각 다른 Main Window를 생성하고 있습니다.

우선 이 부분을 해소하기 위해 코드 분석을 해보았습니다.

 

int APIENTRY wWinMain(_In_ HINSTANCE hInstance,
                     _In_opt_ HINSTANCE hPrevInstance,
                     _In_ LPWSTR    lpCmdLine,
                     _In_ int       nCmdShow)
{
    UNREFERENCED_PARAMETER(hPrevInstance);
    UNREFERENCED_PARAMETER(lpCmdLine);

    // TODO: Place code here.

    // Initialize global strings
    LoadStringW(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
    LoadStringW(hInstance, IDC_DIRECTX12EXAMPLECODE, szWindowClass, MAX_LOADSTRING);
    MyRegisterClass(hInstance);

    // Perform application initialization:

    if (!InitInstance (hInstance, nCmdShow))
    {
        return FALSE;
    }

    HACCEL hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_DIRECTX12EXAMPLECODE));

    //D3DApp::Run
    MSG msg{ };

    // Main message loop:
    try
    {
        while (GetMessage(&msg, nullptr, 0, 0))
        {
            if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
            {
                TranslateMessage(&msg);
                DispatchMessage(&msg);
            }
        }
        return (int)msg.wParam;
    }
    catch (DXException& e)
    {
        MessageBox(nullptr, e.ToString().c_str(), L"HR Failed", MB_OK);
        return 0;
    }
}

Main 함수에 해당하는 WinMain입니다.

LoadStringW를 통해 창 이름과 Class 이름을 지정합니다.

 

그리고 MyRegisterClass로 Window Class를 등록합니다.

//
//  FUNCTION: MyRegisterClass()
//
//  PURPOSE: Registers the window class.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
    WNDCLASSEXW wcex;

    wcex.cbSize = sizeof(WNDCLASSEX);

    wcex.style          = CS_HREDRAW | CS_VREDRAW;
    wcex.lpfnWndProc    = WndProc;
    wcex.cbClsExtra     = 0;
    wcex.cbWndExtra     = 0;
    wcex.hInstance      = hInstance;
    wcex.hIcon          = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_DIRECTX12EXAMPLECODE));
    wcex.hCursor        = LoadCursor(nullptr, IDC_ARROW);
    wcex.hbrBackground  = (HBRUSH)(COLOR_WINDOW+1);
    wcex.lpszMenuName   = MAKEINTRESOURCEW(IDC_DIRECTX12EXAMPLECODE);
    wcex.lpszClassName  = szWindowClass;
    wcex.hIconSm        = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

    return RegisterClassExW(&wcex);
}

이중 WndProc는 자체적으로 선언한 함수입니다.

//
//  FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
//  PURPOSE: Processes messages for the main window.
//
//  WM_COMMAND  - process the application menu
//  WM_PAINT    - Paint the main window
//  WM_DESTROY  - post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    switch (message)
    {
    case WM_COMMAND:
        {
            int wmId = LOWORD(wParam);
            // Parse the menu selections:
            switch (wmId)
            {
            case IDM_ABOUT:
                DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
                break;
            case ID_EXAMPLE_CHAPTER6:

                break;
            case IDM_EXIT:
                DestroyWindow(hWnd);
                break;
            default:
                return DefWindowProc(hWnd, message, wParam, lParam);
            }
        }
        break;
    case WM_PAINT:
        {
            PAINTSTRUCT ps;
            HDC hdc = BeginPaint(hWnd, &ps);
            // TODO: Add any drawing code that uses hdc here...
            EndPaint(hWnd, &ps);
        }
        break;
    case WM_DESTROY:
        PostQuitMessage(0);
        break;
    default:
        return DefWindowProc(hWnd, message, wParam, lParam);
    }
    return 0;
}

Class가 등록이 되면 그 다음은 Instance를 초기화 합니다.

//
//   FUNCTION: InitInstance(HINSTANCE, int)
//
//   PURPOSE: Saves instance handle and creates main window
//
//   COMMENTS:
//
//        In this function, we save the instance handle in a global variable and
//        create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   hInst = hInstance; // Store instance handle in our global variable

   HWND hWnd = CreateWindowW(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, nullptr, nullptr, hInstance, nullptr);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

그 아래가 Main Mesage Loop입니다.

 

다음은 DirectX 코드에서 해당 부분입니다.

bool D3DApp::InitMainWindow()
{
	//--------------RegisterClass
	WNDCLASS wc;
	wc.style = CS_HREDRAW | CS_VREDRAW;
	wc.lpfnWndProc = MainWndProc;
	wc.cbClsExtra = 0;
	wc.cbWndExtra = 0;
	wc.hInstance = mhAppInst;
	wc.hIcon = LoadIcon(0, IDI_APPLICATION);
	wc.hCursor = LoadCursor(0, IDC_ARROW);
	wc.hbrBackground = static_cast<HBRUSH>(GetStockObject(NULL_BRUSH));
	wc.lpszMenuName = 0;
	wc.lpszClassName = L"MainWnd";

	if (!RegisterClass(&wc))
	{
		MessageBox(0, L"RegisterClass Failed.", 0, 0);
		return false;
	}


	//--------------------------InitInstance
	RECT R = { 0, 0, mClientWidth, mClientHeight };
	AdjustWindowRect(&R, WS_OVERLAPPEDWINDOW, false);
	int width = R.right - R.left;
	int height = R.bottom - R.top;

	mhMainWnd = CreateWindow(L"MainWnd", mMainWndCaption.c_str(), 
		WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, CW_USEDEFAULT, width, height, 0, 0, mhAppInst, 0);
	if (!mhMainWnd)
	{
		MessageBox(0, L"CreateWindow Failed.", 0, 0);
	}

	ShowWindow(mhMainWnd, SW_SHOW);
	UpdateWindow(mhMainWnd);

	return true;

}

주석으로 대략 나눠놓았습니다.

InitMainWindow( 안에 RegisterClass와 InitInstance 부분이 같이 존재합니다.

이를 각각의 함수로 나누고, 양쪽 코드에서 필요로 하는 기능을 모두 갖추도록 하고자 합니다.

그리고 Main에서는 아무런 작업 없이, 메뉴의 Event에서 화면 출력을 교체하고자 합니다.

 

이 중 InitInstance는 다음 과정을 거쳐서 호출이 됩니다.

 

bool D3DApp::Initialize()
{
	if (!InitMainWindow())
	{
		return false;
	}
	if (!InitDirect3D())
	{
		return false;
	}

	OnResize();
	return true;
}

 

bool BoxApp::Initialize()
{
	if (!D3DApp::Initialize())
	{
		return false;
	}

	ThrowIfFailed(mCommandList->Reset(mDirectCmdListAlloc.Get(), nullptr));
	BuildDescriptorHeaps();
	BuildConstantBuffers();
	BuildRootSignature();
	BuildShadersAndInputLayout();
	BuildBoxGeometry();
	BuildPSO();

	ThrowIfFailed(mCommandList->Close());
	ID3D12CommandList* cmdLists[] = { mCommandList.Get() };
	mCommandQueue->ExecuteCommandLists(_countof(cmdLists), cmdLists);

	FlushCommandQueue();
	return true;
}

 

또한 WndProc와 대응하는 함수는 MsgProc가 있습니다.

LRESULT D3DApp::MsgProc(HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
	//WndProc
	switch (msg)
	{
	case WM_ACTIVATE:
		if (LOWORD(wParam) == WA_INACTIVE)
		{
			mAppPaused = true;
			mTimer.Stop();
		}
		else
		{
			mAppPaused = false;
			mTimer.Start();
		}
		return 0;
	case WM_SIZE:
		mClientWidth = LOWORD(lParam);
		mClientHeight = HIWORD(lParam);
		if (md3dDevice)
		{
			if (wParam == SIZE_MINIMIZED)
			{
				mAppPaused = true;
				mMinimized = true;
				mMaximized = false;
			}
			else if (wParam == SIZE_MAXIMIZED)
			{
				mAppPaused = false;
				mMinimized = false;
				mMaximized = true;
				OnResize();
			}
			else if (wParam == SIZE_RESTORED)
			{
				if (mMinimized)
				{
					mAppPaused = false;
					mMinimized = false;
					OnResize();
				}
				else if (mMaximized)
				{
					mAppPaused = false;
					mMaximized = false;
					OnResize();
				}
				else if (mResizing)
				{

				}
				else
				{
					OnResize();
				}
			}
		}
		return 0;
	case WM_ENTERSIZEMOVE:
		mAppPaused = true;
		mResizing = true;
		mTimer.Stop();
		return 0;
	case WM_DESTROY:
		PostQuitMessage(0);
		return 0;
	case WM_MENUCHAR:
		return MAKELRESULT(0, MNC_CLOSE);
	case WM_GETMINMAXINFO:
		((MINMAXINFO*)lParam)->ptMinTrackSize.x = 200;
		((MINMAXINFO*)lParam)->ptMinTrackSize.y = 200;
		return 0;
	case WM_LBUTTONDOWN:
	case WM_MBUTTONDOWN:
	case WM_RBUTTONDOWN:
		OnMouseDown(wParam, GET_X_LPARAM(lParam), GET_Y_LPARAM(lParam));
		return 0;
	case WM_LBUTTONUP:
	case WM_MBUTTONUP:
	case WM_RBUTTONUP:
		OnMouseUp(wParam, GET_X_LPARAM(lParam), GET_Y_LPARAM(lParam));
		return 0;
	case WM_MOUSEMOVE:
		OnMouseMove(wParam, GET_X_LPARAM(lParam), GET_Y_LPARAM(lParam));
		return 0;
	case WM_KEYUP:
		if (wParam == VK_ESCAPE)
		{
			PostQuitMessage(0);
		}
		else if (static_cast<int>(wParam) == VK_F2)
		{
			Set4xMsaaState(!m4xMsaaState);
		}
		return 0;
	}
	return DefWindowProc(hwnd, msg, wParam, lParam);
}

 

다음에는 D3DApp의 상위 클래스를 두던가 하여 통합을 하고자 합니다.

'내용정리 > DirectX12' 카테고리의 다른 글

20.08.07 개발일지  (0) 2020.08.07
20.08.04 일지  (0) 2020.08.04
20.07.28 개발일지  (0) 2020.07.28
20.07.25 개발일지  (0) 2020.07.25
20.07.24 일지  (0) 2020.07.24

https://www.acmicpc.net/problem/3300

 

3300번: 무어 기계

문제 무어 기계는 상태에 의해서 출력이 결정되는 유한 상태 기계이다. 무어 기계는 이름은 미국의 수학자이자 컴퓨터 과학자 Edward F. Moore의 이름을 따서 지었다. 무어 기계의 상태 전이는 입력�

www.acmicpc.net

Graph 순회 방법을 대충 맞추어서 정리를 합니다.

 

하나는 String을 두어 Push_Back과 erase로 정답을 산출.

그리고 두개의 Stack을 두어 하나는 순회를 하고 다시 되돌아 올 Index를 저장.

다른 하나는 되돌아 왔을 때 어느 Node로 넘어가야 하는지를 알려주는 Stack입니다.

 

지금 개발중인 기능을 마무리 하고 8월 중으로 여러 회사들에 입사지원서를 쓰기 위해 언리얼 개발에 더 전념중입니다.

그러다보니 알고리즘 풀 체력이나 정신력이 부족해 한 문제를 몇 주씩 물고 늘어지게 되는 것 같습니다.

여태까지 못푼 문제들 위주로 잡다보니 어려운 것도 한 몫 하고 있긴 합니다만.

빨리 못푼 문제 다 털어버리고 부족한 부분을 더 다잡고 싶습니다.

'개발일지 > Algorithm' 카테고리의 다른 글

20.07.29 개발일지 - Frogger  (0) 2020.07.29
20.07.28 개발일지 - 무어기계  (0) 2020.07.28
20.07.27 - 무어기계(cont)  (0) 2020.07.27
20.07.26 - 무어 기계(cont)  (0) 2020.07.26
20.07.24 개발일지 - 무어 기계(cont)  (0) 2020.07.24

오늘은 Attach 관련 기능들을 구현하다가 시간을 다 보냈습니다.

우선 UniqueID로 관리하던 고유값을 ObjectName으로 교체했습니다.

어떤게 더 나을지는 시간이 지나봐야 알겠지만, 큰 문제는 없을 것 같습니다.

 

그리고 AttachLatch, Piece는 어느정도 기능 구현이 완료된 상태입니다.

다만 이를 테스트 하려면 Attach 기능이 Character에게도 구현이 되어 있어야 하는데, 

아직 이 부분을 완수하지 못했습니다.

 

우선 Interface의 포인터 형을 변수로 UPROPERTY 변수로 받지 못하는 부분에서 컴파일 에러가 발생하고 있습니다.

또한 Character는 Piece 뿐만 아니라 장비나 소모품과 같은 다른 Attachable도 취급하는데, 

이들에 대한 기준이 명확하지 않은 상태입니다.

 

그래서 Character 부분의 기능 구현에 하루 정도 더 투자를 해야 할 것 같습니다.

'개발일지 > Treasure Hunter' 카테고리의 다른 글

20.08.02 개발일지  (0) 2020.08.02
20.08.01 개발일지  (0) 2020.08.01
20.07.29 개발일지  (0) 2020.07.29
20.07.27 개발일지  (0) 2020.07.27
20.07.26 개발일지  (0) 2020.07.26

약 먹은 병아리 마냥 비실비실 거리다가

대규모 변경점으로 인한 기본 15분의 빌드시간들을 거쳐 겨우 무언가 해냈습니다.

 

우선 InRange 기능을 개선했습니다.

예전에 Notify와 관련해서 질문을 올린 글에서

"Character의 UniqueID를 Set으로 관리하면 되지 않느냐"라는 댓글이 올라왔습니다.

결과적으로 Notify가 없다면 원치 않은 HitEvent.

예를 들어 왼손 펀치 공격을 하는데 오른손에서 먼저 펀치 이벤트가 발생하는
불상사가 발생하기에 Notify는 꼭 필요합니다.

하지만 UniqueID와 Set은 썩 그럴듯하였고, 이를 적용해보았습니다.

 

하지만 직접 시도해본 결과, Set은 Replicate가 되지 않고

UniqueID의 타입인 uint32와 같은 numeric은 BP에서 지원하지 않았습니다.

그래서 두 차례 대규모 공사를 한 뒤, Set을 다시 Array로 되돌렸습니다.

다만 원래는 Object&를 지니고 있었으나, 이를 FString으로 교체해서 UniqueID를 적용은 유지 중입니다.

비록 FString이 uint32를 Fstring으로 형변환 해주지는 않지만, 일반 int32는 지원을 합니다.

unsigned int에서 signed int로 형변환 시 유일성이 훼손되지 않으므로, 이를 그냥 사용하고 있습니다.

 

그리고 나서 Latch와 관련된 기능들을 구현하였습니다.

이 부분에서 조금 혼동이 있었습니다.

기존의 Latch는 AttachLatch. 즉 무언가를 부착하는 기능만 구현을 했었습니다.

때문에 Latch와 AttachActivity의 기능을 계속 구분하지 못하고 몇번이고 작성과 지우기를 반복했습니다.

그러다가 Latch의 Check Answer는 정답 여부만 받아오도록 하고, 

AttachActivity. 즉 부착 주체는 부착과 해제. 그리고 각각의 가능 여부를 받아오도록 하였습니다.

부착 객체(Attachable)에게는 부착이 가능한지와,  현재 소유권자가 누구인지를 확인하는 기능을 부여했습니다.

 

이전 Latch와 Piece 안 기능들을 모두 지우고, 이를 사용하는 다른 코드에서 해당 내용을 주석처리 했습니다.

그리고 Latch와 Piece의 기능을 대략적으로 선언만 해두었고, 이를 상속받는 몇가지 Latch와 Piece를 생성했습니다.

기존 기획에서 바뀐 점이라면, 원래 Latch가 부착, 피격, Widget에 상호작용.

그리고 Piece는 부착을 생각하고 있었습니다.

하지만 피격 Latch. 즉 때려서 부숴야 하는 경우에는 상호작용을 할 수 없습니다.

때문에 이를 Piece로 옮겼습니다.

그래서 현재는 Latch에 부착, Widget. 그리고 Piece에 부착, 피격이 존재하고 있습니다.

 

이 과정에서 너무 많은 코드를 수정하여 오늘은 이쯤에서 일단락 했습니다.

내일은 Base 코드 안의 기능들을 구현하고, 부착 Latch와 Piece를 먼저 구현해보려 합니다.

이 다음에는 피격 Piece를 구현하고, 마지막에 Widget Latch를 구현하려 합니다.

Widget Latch는 간만의 Widget 작업이기도 하고, 아직 아무 생각이 없어 뒤로 미루었습니다.

 

가능하면 이번주 안에 두 기능이 완성되었으면 합니다.

 

 

'개발일지 > Treasure Hunter' 카테고리의 다른 글

20.08.01 개발일지  (0) 2020.08.01
20.07.30 개발일지  (0) 2020.07.30
20.07.27 개발일지  (0) 2020.07.27
20.07.26 개발일지  (0) 2020.07.26
20.07.23 개발일지  (0) 2020.07.23

https://www.acmicpc.net/problem/11100

 

11100번: Frogger

A group of frogs is sitting on an infinite xy grid. The frogs all have non-positive x coordinates. On the grid location (2, 0) there’s a fly. The frogs are hungry and would like to get there to eat the fly. There’s one catch; a frog can only move by ju

www.acmicpc.net

예전에 시도 했는데 풀지 못하고 보류 했던 문제입니다.

 

문제를 정리하자면

1. 개구리는 가로세로로만 움직일 수 있으며, 인접한 다른 개구리를 밟고 그 개구리의 다음 좌표로 이동할 수 있다.

2. 밟힌 개구리는 터져 죽는다.

3. 파리는 {(x, y) | x >= 0, y = 0}에, 개구리는 {(x, y) | x < 0, y = 모든 정수}에 위치한다,

4. 좌표별 파리를 먹을 수 있는 개구리의 최소 숫자를 출력하라. 불가능 할 시 Frogger 출력.

이렇습니다.

 

처음 접했을 때도 4 이후로 규칙을 찾을 수 없어 고민을 하다가 멈췄습니다.

그러다가 심심해서 커뮤니티에 올려봤는데, 누군가가 풀이를 적어줘서 보고 이해를 할 수 있었습니다.

 

https://github.com/marteloge/Programming-contests/blob/master/IDI%20Open/solutions/2007%20solutions.pdf

 

marteloge/Programming-contests

IDI Open, CodeChef, NCPC. Contribute to marteloge/Programming-contests development by creating an account on GitHub.

github.com

요약을 하자면 이렇습니다.

1. 개구리는 가로와 세로로만 움직일 수 있으니 개구리와 파리와의 거리는 맨하튼 거리로 표시한다.

2. 개구리들과 파리와의 가중치의 합을 구한다. Sum(K^d) = D_fly라고 봐도 무방할 것이다.

3. 위 과정을 거치면 개구리와 파리의 평면이 하나의 방정식으로 표시된다.

4. 하지만 5차 이상의 방정식은 근의공식이 존재하지 않는다.

https://m.blog.naver.com/PostView.nhn?blogId=iphone_dev&logNo=80145256483&proxyReferer=https:%2F%2Fwww.google.com%2F

 

N차 방정식의 일반적인 해법(=근의공식)에 대한 고찰

꼴의 방정식(단 a≠0)일반적인 해법 : (단 a≠0) 이미 기원전부터 발견됬던 해법으로 누가 발견했는지도 모...

blog.naver.com

5. 그렇기에 우리는 거리가 0~4일 때의 값만 작성을 하고, 그 위의 값은 frogger를 출력하면 된다.

 

Mathematics 문제는 항상 이런 문제? 매력?이 있습니다.

모르면 절대로 죽었다 깨어나도 풀 수 없지만, 풀면 그 쾌감이 다른 문제보다 더 강렬합니다.

하지만 이 문제는 가중치 계산을 하는 것에 전혀 다가가지 못해서 결국 이렇게 보고 풀 수 밖에 없던 것 같습니다.

 

더보기
#include <iostream>

using namespace std;

int main()
{
    const int Mem[5] = { 1, 2, 4, 8, 20 };
    int times = 0, input = 0;
    cin >> times;
    while (times-- > 0)
    {
        cin >> input;
        if (input < 5)
        {
            cout << Mem[input] << endl;
        }
        else
        {
            cout << "frogger" << endl;
        }
    }
    return 0;
}

https://www.acmicpc.net/problem/3300

 

3300번: 무어 기계

문제 무어 기계는 상태에 의해서 출력이 결정되는 유한 상태 기계이다. 무어 기계는 이름은 미국의 수학자이자 컴퓨터 과학자 Edward F. Moore의 이름을 따서 지었다. 무어 기계의 상태 전이는 입력�

www.acmicpc.net

무어 머신을 입력받고 이를 그래프로 표현하는 부분을 구상하였습니다.

원래는 이대로 끝내려 했지만 4일에 한번 있는 저녁 운동 없는 날이기도 하고,
요즘 알고리즘을 열심히 안한 느낌도 있어서 구현까지 해보았습니다.

테스트 결과 왠만한 경우에서 잘 작동하고 있습니다.

 

더보기
#include <iostream>
#include <sstream>
#include <string>   
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

int FindFormerNode(const vector<int>& Heights, const int& height, const int& index)
{
    for (int i = index - 1; i >= 0; --i)
    {
        if (Heights[i] < height)
        {
            return i;
        }
    }
    return 0;
}

vector<int> FindFormerNodes(const vector<vector<int>>& Nodes, const vector<int>& Heights, const int& height, const int& index, const int& gap)
{
    vector<int> ret;
    for (int i = index - 1; i >= 0; --i)
    {
        if (height == Heights[i])
        {
            break;;
        }
        if (!Nodes[i].empty())
        {
            continue;
        }
        if (height - Heights[i] >= gap)
        {
            ret.push_back(i);
        }
    }
    return ret;
}

int main()
{
    int testtime = 0;
    
    cin >> testtime;

    while (testtime-- > 0)
    {
        string machine, testcase;

        char result = '!', special = 0;
        int gap = 0, height = 0, index = 0;

        vector<char> Spells;
        vector<int> Indices, Heights;
        vector<vector<int>> Nodes;

        cin >> machine >> testcase;

        for (const auto& iter : machine)
        {
            if (iter == '(')
            {
                ++height;
                ++gap;
                special = iter;
                continue;
            }
            if (iter == ')')
            {
                --height;
                --gap;
                special = iter;
                continue;
            }
            if (iter == '|')
            {
                special = iter;
                continue;
            }
            switch (special)
            {
            case '|':
            {
                Spells.push_back(iter);
                Heights.push_back(height);
                Nodes.push_back(vector<int>());
                Nodes[FindFormerNode(Heights, height, index)].push_back(index);
                Indices.push_back(index++);
            }
                break;
            case ')':
            {
                Spells.push_back(iter);
                Heights.push_back(height);
                Nodes.push_back(vector<int>());
                auto Former = FindFormerNodes(Nodes, Heights, height, index, gap);
                for (const auto& i : Former)
                {
                    Nodes[i].push_back(index);
                }
                Indices.push_back(index++);
                gap = 0;
            }
                break;
            default:
            {
                Spells.push_back(iter);
                Heights.push_back(height);
                Nodes.push_back(vector<int>());
                if (Nodes.size() > 1)
                {
                    Nodes[index - 1].push_back(index);
                }
                Indices.push_back(index++);
                gap = 0;
            }
                break;
            }
            special = iter;
        }
        cout << endl;

        
        cout << result << endl;
    }
    return 0;
}

 

우선 Special Character 처리입니다.

흐름에 영향을 주는 Character는 (, |, ) 3가지가 있습니다.

 

( 문자는 입력 시 현재 높이와 이전 Node로부터의 높이가 1씩 올라갑니다.

 

) 문자는 반대로 입력 시 현재 높이와 이전 Node로부터의 높이가 1씩 내려갑니다.

 

| 문자는 입력 자체로는 영향이 없습니다.

 

이 특수 문자는 자체가 입력될 때는 아무 행동도 하지 않습니다.

그렇기에 Special이라는 메모리에 따로 저장을 합니다.

 

그리고 위 3 문자가 아닌 다른 문자 입력 시 Special 문자에 따라 흐름이 달라지게 됩니다.

 

( 문자 입력 시에는 앞 Node에 자신의 Index를 추가합니다.

하지만 이는 일반 문자도 동일하기에 따로 처리하지 않고 있습니다.

 

| 문자는 입력 시 자신의 선행 Node를 찾아 그 Node에 Index를 추가합니다.

선행 Node는 자신의 앞에 있는 Index 중 자신의 높이보다 낮은 높이를 지닌 첫번째 Node입니다.

 

) 문자는 입력 시 자신의 선행 Node을 찾아 그 Node에 Index를 추가합니다.

이 때 선행 Node는 | 문자와 다르게 검색합니다.

 

| 문자는 선행 Node가 자기 자신과 연속적으로 붙어 있기에 단순 비교로 가능합니다.

하지만 )문자는 모든 Node를 검색해야 하기에 단순 비교로는 다른 군(| 문자 앞의 문자들)을 구분할 수 없게 됩니다.

이 때문에 이전 Node와의 거리인 gap이 추가된 것입니다.

 

먼저 비교 Node와 자신의 높이가 동일하다면 함수를 마칩니다.

이는 이미 ) 범위 안의 연산이 끝났다는 것을 의미하기 때문입니다.

 

또한 비교 Node가 이미 다른 Index 값을 가지고 있으면 다음 연산으로 넘어갑니다.

) 연산은 연속적인 Node의 리스트 중 꼬리에만 붙습니다.

Node가 이미 다른 Index 값을 가지고 있다면 이는 꼬리가 아니라는 의미입니다.

 

위 두가지 경우를 제외하고, 두 Node의 높이 차가 gap보다 크거나 같을 경우 Return 할 Vector에 값을 추가합니다.

 

여기서 중요한 조건은 두번째입니다.

그 이유는 세번째 조건은 같은 군에서 이미 Node 값이 있는 것들도 옳다고 판단하기 때문입니다.

그리고 그 조건을 먼저 제거해주는 것이 두번째 조건입니다.

 

세번째 조건은 금새 다다를 수 있지만, 두번째 조건이 없다면 한참을 해맬 것입니다.

 

여기까지 짜놓고 끝까지 작성하지 않은 이유는
아직 이 Graph를 효율적으로 순회해서 탐색하는 방법은 명확하게 정하지 못했기 때문입니다.

일단 시도해보는 방법도 있지만,
이 문제를 풀어오면서 생각을 오래해서 정리를 하는 것이 좋은 답을 도출한다는 것을 느꼈습니다.

이 느낌을 더 느껴보고 싶습니다.

 

그래서 내일 Graph 순회 방법을 고려해보고자 합니다.

일단 가지고 있는 아이디어는 Spells 길이와 동일한 Vector<int>iterator를 두는 것입니다.

Graph를 한 방향으로만 가는 것이 아니라 다른 방향으로도 순회해야 하는데,

재귀문은 메모리 문제가 발생할 것 같기에 이런 방법을 사용해야 할 것 같습니다.

 

더보기
        cout << "Indices:\t";
        for (const auto& i : Indices)
        {
            cout << i << " ";
        }
        cout << endl;
        cout << "Spells:\t\t";
        for (const auto& i : Spells)
        {
            cout << i << " ";
        }
        cout << endl;
        cout << "Heights:\t";
        for (const auto& i : Heights)
        {
            cout << i << " ";
        }
        cout << endl;
        for (const auto& i : Nodes)
        {
            for (const auto& j : i)
            {
                cout << j << " ";
            }
            cout << endl;
        }

 

코드를 모두 작성하였는데 에러가 나서 에러를 수정하고 있습니다.

 

우선 디버깅으로 어느 위치에서 에러가 나는지 파악을 했는데, 라이브러리 코드라서 어떻게 뜯지를 못하고 있습니다.

 

그러다가 구글에 검색을 해보니 저와 같은 문제를 겪은 사람이 있는 것 같은데 글이 길어 읽다가 끝났습니다.

 

다음에는 좀 읽고 수정을 해보려 합니다.

'내용정리 > DirectX12' 카테고리의 다른 글

20.08.04 일지  (0) 2020.08.04
20.07.31 개발일지  (0) 2020.07.31
20.07.25 개발일지  (0) 2020.07.25
20.07.24 일지  (0) 2020.07.24
08. Direct3D의 초기화 - CPU와 GPU의 상호작용  (0) 2020.07.24

+ Recent posts