1. 하나 고정하고 나머지 값을 통해 찾기배열에서 세가지 값의 합을 구하는 등의 작업을 할 때, 하나의 값을 고정시켜두고 나머지 값들만 투포인터를 통해서 계산하기 2. 문제https://www.acmicpc.net/problem/2473이 문제는"중간에서 만나기"를 쓰면 추가 공간이 필요하여 메모리가 터진다.n = 5000이기 때문에 n^2은 25,000,000이 되고, 여기서 long long값과 인덱스 2개를 int로 저장하면25,000,000 * (8 + 4 + 4) = 400,000,000 400MB 메모리 필요하므로 메모리 초과가 될 것이다. 풀이더보기#include #include #include #include using namespace std;int n;vector vec;long lo..

1. 중간에서 만나기알고리즘의 전체 탐색 범위를 반으로 나누어, 양쪽에서 동시에 탐색을 시작해 중간에서 만나는 방식으로 시간 복잡도를 줄이는 기법예시00000000~99999999 비밀번호 풀기앞의 4자리와 뒤의 4자리를 따로 계산한 결과 A와 B를 합쳐서 정답이 되는지 확인하기10^8의 연산을 10^4 * 2 의 연산으로 줄여준다A+B+C+D = 0 찾기A+B = -(C+D) 로 계산하기모든 조합의 합을 계산 : n^2C+D를 정렬한 후 A+B를 순환하면서 이분탐색을 하기 : O(N^2logN)N^2사이즈의 A+B 배열을 돌면서 O(N^2)N^2사이즈의 배열을 이진탐색 O(logN^2) 하기 -> O(N^2logN^2)!중요!메모리 제한을 항상 생각하고 쓰기이 방식은 메모리를 많이 사용하게 된다! 2..

1. 개념문자열을 효율적으로 처리하기 위한 트리 자료구조삽입 삭제 탐색에 있어서 O(|S|) 시간이 소요그러나 메모리는 최대 4*글자의 종류 만큼 차지하므로 메모리 효율은 좋지 않다.이론적인 시간 복잡도와 달리 실제로는 트라이가 해시나 이진 검색 트리에 비해 느리다.그러나 이 특징을 사용해야하는 문제가 있다.문자열의 접두사 검색 등과 같은 느낌 2. 구현코드#include using namespace std;const int ROOT = 1;int unused = 2; //새로 추가할 정점const int MX = 10000 * 500 + 5; //최대 등장 가능한 글자 수 -> 최대 500인 문자열이 10000개 들어온 경우bool chk[MX];int nxt[MX][26]; // 각 정점에서 자식 ..

1. 개념방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬을 말한다.예를 들어, 교과 이수 제도가 있다.특정 과목을 듣기 위해서 선수과목이 있는 그런 형태를 말한다.주의할 점같은 그래프에서 여러 가지의 위상 정렬이 있을 수는 있다.단, 그래프의 순환이 있는 경우는 위상정렬이 될 수 없다. 위상 정렬은 사이클이 없는 방향 그래프(DAG) 에서만 정의된다. 2. 구현참고indegree : 자신에게 들어오는 간선의 수동작 방식모든 간선을 순환하여 indegree 테이블 채우기indegree가 0인 정점들을 queue에 넣기queue에서 pop을 통해 위상 정렬 결과에 추가해당 정점으로부터 연결된 모든 정점의 indegree값을 1감소, 만약 이 때 indegree가 0이라면 ..

1. 플로이드 알고리즘모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘방향 그래프나 무방향 그래프 모두 상관없음간선이 음수여도 동작함, 단 음수 사이클은 없어야 함시간 복잡도는 O(V^3)왜 쓸까?예를 들어 정점이 100개 정도일 때 쓸만함 -> 코드가 쉬우니까모든 정점에 대한 거리를 알고 싶을 때 경유지를 고려해야 할 때 (다익스트라 같은 경우는 A->Z 까지의 최단 거리만 구하기 때문)또한 음수 가중치가 있는 경우.. 2. 동작 방식먼저 테이블을 만들어 두고, 각 정점에서 인접한 정점까지의 거리만 업데이트하여 최단 거리 테이블을 만든다.지금까지 적어둔 값은 어떠한 정점을 거치지 않았을 때의 모습이다. 이제부터는 특정 정점을 거쳐가면서 더 짧은 경로가 있다면 업데이트 해주면 된다.아래 모습은 정점 1은..

보스 레벨에서 플레이어들이 사용하는 다리 Mesh가 있는데, 이것을 파괴하는 시스템을 개발하게 되었다. 1. 고민처음에는 해당 기획을 듣고 여러 방식을 떠올리게 되었다.ChaosPhysics Constraintetc...개발하기 전 가장 중요하게 생각했던 부분은 "부서진 이후의 결과물"에 대한 고민이었다.파괴된 이후의 Mesh가 사라지도록 하여 게임에 영향을 미치지 않도록 할 것인가파괴된 이후의 Mesh가 이후 게임에 영향을 미치도록 할 것인가이 부분은 게임 플레이에 영향을 미칠 수 있는 부분이라고 생각하여 최대한 게임 플레이에 있어서 지장을 주지 않는 방향으로 생각하고 개발을 하였다. 다음으로는 고민한 내용은 얼마나 예쁘게 부술 수 있는가에 대한 내용이었다.현재 팀에는 배경 모델링을 담당해주시는 분이 ..

전투 게임에 있어서 가장 중요한 부분중에 하나가 타격감이다. 여러가지 정보를 찾다가 아래 영상을 통해 Hit Stop이라는 것을 접하게 되었고 게임에 적용해 보게 되었다.https://youtu.be/IL9j4NchTvA?si=MM6F7kJEw7RysZRI&t=1951 1. 기능 구현가장 간단한 방식으로는 해당 시점에 시간을 느리게 만들어주는 방식이 존재한다. 코드를 보면SetGlobalTimeDilation을 통해 World의 시간을 지연시켜서 느려지도록 하는 방식이다.단순히 싱글플레이 게임에 있어서는 아래와 같은 방식을 사용해도 문제가 없을것이지만, 현재 게임은 멀티플레이 게임이기 때문에 멀티캐스트를 통해서 시간 지연하는 함수를 사용하기 때문에 월드에 존재하는 모든 플레이어들의 시간이 느려지는 문제..

보호되어 있는 글입니다.

멀티플레이 게임에서 UI를 개발함에 있어서 고려할 만한 점이 있다. Owner설정UI의 OwnerUI에 띄울 정보를 가질 Owner 보이는 곳Owner에게만 보여줄 것인가다른 유저들에게도 보여줄 것인가위젯에서 표시할 값이 어디에서 변하는가서버에서 변경클라이언트에서 변경1. Owner 설정과 보여지는 곳예를 들어, 우리가 자신의 체력 바를 만든다고 했을 때를 생각해 보자UI의 Owner는 나 자신이고, 띄울 정보의 Owner도 나 자신이다.보여지는 곳은 나 자신이 될 것이다.이 경우는 크게 생각할 문제가 없다.그러나 우리가 다른 플레이어의 체력 바를 또한 띄우고 싶다면UI의 Owner는 나 자신이지만, 띄울 정보는 다른 플레이어의 정보이다.보여지는 곳은 여전히 나 자신이 된다.이 경우 해당 Widget을 ..

1. 언리얼 인사이트언리얼 프로파일링 툴인 Unreal Insights를 통해서 최적화 테스트를 해 볼 생각이다. 1 - 1. 설정언리얼 엔진을 다운로드한 경로로 가서 아래와 같이 UnrealInsights.exe 파일을 찾는다.일반적으로 아래와 같은 경로로 저장된다. C:\Program Files\Epic Games\UE_5.5\Engine\Binaries\Win64쉽게 사용하기 위해 환경변수에 등록을 한다이후 프로파일링을 하고자 하는 프로젝트가 있는 폴더로 들어가서 bat 파일을 만들어준다내용은 아래와 같이 환경변수를 사용하여 만들면 된다.UnrealEditor.exe %cd%\SCC_DedicatedX.uproject -NetTrace=1 -Trace=Net 1 - 2. 사용bat 파일을 더블클릭하..