개인사

[P3] 백준 12895번 화려한 마을 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리, 비트마스킹

리뷰 https://www.acmicpc.net/problem/12895맞왜틀 하고 있는데 질문게시판에서 쿼리의 범위 중 L이 R보다 크게 나오는 케이스가 있다는 것을 봤다.그걸 해결해주니 AC를 받았는데 음 문제에 기재하거나 예제에 있었으면 좋겠다는 생각이 들었다.로직은 맞게 구현해도 이런 것 때문에 틀린다면 시간을 많이 날릴 것 같다.  전역 변수N : 인덱스의 최대 크기를 저장할 상수 변수n : 집의 개수를 저장할 변수t : 사용할 색의 개수를 저장할 변수q : 작업의 개수를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열lazy : 업데이트 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = ..

[P5] 백준 1777번 순열복원 C++ 세그먼트 트리

리뷰 https://www.acmicpc.net/problem/1777[P4] 백준 1849번 순열 C++ 세그먼트 트리 [P4] 백준 1849번 순열 C++ 세그먼트 트리리뷰 https://www.acmicpc.net/problem/1849구간 합 세그먼트 트리를 통해 답을 도출하는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 수열 원소의 개수를 저장할 변수s : 매 원소를 입력zzzz955.tistory.com위 문제의 반대 버전  전역 변수N : 순열의 최대 크기를 저장할 상수 변수n : 순열의 크기를 저장할 변수s : 각 인버전 시퀀스 값을 저장할 변수lst : 순열의 인버전 시퀀스를 저장할 배열ans : 순열의 요소를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열..

개요빌드 환경을 구현하였으니 본격적인 서버 구현에 앞서 구현하고자 하는 아키텍쳐를 구상해봤다.내가 개발해야할 서버에선 클라이언트 세션을 관리하고 클라이언트 요청에 따라 인증, 매칭등의 서비스 로직을 구현해야 한다. 이를 데이터베이스와 통신하여 트랜잭션 처리를 통해 검증 및 상태 업데이트를 진행해 주어야 한다. 따라서 controller를 통해 클라이언트 요청을 구분하여 각 기능에 맞는 API를 호출할 수 있도록 서비스를 핸들해 주기로 했다. 예를 들어 인증 관련은 auth, 매칭 관련은 room, 게임 생명 주기 관리는 game의 컨트롤러 타입을 지정하고, 컨트롤러 핸들러를 통해 각 API가 호출될 수 있도록 나누어줬다. 처음엔 패킷을 주고 받을 때 최대한 적은 리소스를 사용하고자했지만 게임 내 이벤트에..

리뷰 https://www.acmicpc.net/problem/1849구간 합 세그먼트 트리를 통해 답을 도출하는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 수열 원소의 개수를 저장할 변수s : 매 원소를 입력 받을 변수lst : 초기엔 모두 1로, 이후엔 수열의 순서로 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = lst[s]; else { int mid = (s + e) / 2; build(node * 2, s, mid); build(node * 2 + 1, mid + 1, e); tree[node] = tree[node * 2] +..

개요Windows에선 VisualStudio를 통해 편하게 빌드할 수 있었다면, Linux환경에선 Makefile을 통해 편하게 빌드할 수 있다.CMake가 크로스 플랫폼에서의 빌드 환경에 강점이 있다고 하는데 실제로 사용해 보니 그렇게 Windows와 Linux환경이 조금 많이 차이가 나서 왜 강점이라고 하는지는 잘 느끼지 못했다. 내가 잘못 썼을 가능성이 가장 크긴 하지만... Linux환경에선 패키지 유무가 C++ 프로젝트를 제대로 수행할 수 있는지 여부가 가장 크다, vcpkg를 clone하고 설치한 후 vcpkg.json을 통해 라이브러리를 설치 할 수 있다는 것은 Windows환경과 동일하다. 하지만 해당 라이브러리를 설치하는 과정에서 다양한 리눅스 패키지가 필요하기 때문에 오류가 자주 발생하..

개요vcpkg를 통해 설치한 라이브러리를 코드 작성 및 실제 컴파일 단계에서 오류 없이 사용하기 위해선 설치된 디렉토리를 프로젝트 속성에서 명시해 주어야 한다.이를 명시해 주지 않는다면 코드 작성 시 include 단계에서 부터 라이브러리를 인식하지 못하며, 링커 단계에서 라이브러리 디렉터리를 명시해 주지 않는다면 컴파일 단계에서 에러가 발생하게 된다. CMakeLists를 통해 CMake 빌드 환경을 구축할 수도 있지만 Windows환경에서 컴파일 및 빌드할 것이라면 더 쉽고 간편하게 VisualStudio 환경에서 세팅할 수 있는 방법을 알아보자  추가 포함 디렉토리프로젝트 -> 프로젝트 속성 -> C/C++ -> 일반 탭으로 이동해 준다.추가 포함 디렉터리에 vcpkg를 통해 설치한 include디..

개요소켓 서버를 C++의 Boost.asio라이브러리를 기반으로 구현할 것이기 때문에 관련 패키지 설치가 필요하다.또한 PostgreSQL과 트랜잭션이 필요하므로 관련 라이브러리가 필요하다. 그 외에도 통신에 사용될 타입을 json으로 사용, 서버 로그를 기록하고 보안을 유지하기 위해 관련 라이브러리들의 설치가 필요하다. vcpkg를 사용한다면 마치 python의 venv처럼 프로젝트 내에서 필요한 패키지를 설치하고 사용할 수 있다.이는 컴퓨터 내에 전역으로 패키지를 설치하지 않기 때문에 다양한 장소에서도 레포지토리를 clone 후 이미 지정해 놓은 패키지들을 명시하여 설치해 줄 수 있어 편리하다.  vcpkg 설치윈도우 환경이라면 powerShell을 사용하여 설치할 수 있다.# vcpkg 저장소 클론..

리뷰 https://www.acmicpc.net/problem/11962구간 업데이트 + 최소값 및 구간합 세그먼트 트리 문제  전역 변수N : 배열 크기의 최대값을 저장할 상수 변수n : 배열의 크기를 저장할 변수q : 쿼리의 개수를 저장할 변수lst : 배열의 초기값을 저장할 배열MS : 세그먼트 트리의 최소값 M, 구간 합 S를 정의할 구조체tree : 세그먼트 트리 정보를 저장할 MS타입 배열lazy : 세그먼트 트리의 느린 업데이트 처리를 위한 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = { lst[s], lst[s] }; else { int mid = (s + e) / 2; build(node * 2,..

리뷰 https://www.acmicpc.net/problem/2934문제를 봤을 때 이해가 잘 되지 않았는데 예시 그래프를 보고 이해 된 내용으로 시도했다.  전역 변수N : 좌표의 최대 범위를 저장할 상수 변수n : 식물을 심은 날의 수를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열lazy : 업데이트 정보를 저장할 배열 함수1. propagatevoid propagate(int node, int s, int e) { if (lazy[node]) { tree[node] += (e - s + 1) * lazy[node]; if (s != e) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } lazy[no..

리뷰 https://www.acmicpc.net/problem/18227오일러 경로를 구할 때 노드의 깊이를 구해준 후 구간합 쿼리에 해당 깊이를 곱해준 뒤 출력하는 문제회사 문화 문제와 비슷하나 노드의 깊이를 구해주어야 하는 조건이 추가된 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 도시의 수를 저장할 변수c : 수도의 번호를 저장할 변수q : 쿼리의 개수를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열it : 오일러 경로의 진입 시점을 저장할 배열ot : 오일러 경로의 탈출 시점을 저장할 배열dep : 노드의 깊이를 저장할 배열t : 오일러 경로의 시간을 저장할 변수edges : 인접 리스트를 저장할 벡터 배열 함수1. dfsvoid dfs(int level, int ..

리뷰 https://www.acmicpc.net/problem/9345누적합, 최대, 최소 세그먼트 트리 모두 사용하여 AC를 받았다.  전역 변수N : DVD수의 최대값을 저장할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : DVD의 개수를 저장할 변수k : 쿼리의 개수를 저장할 변수lst : DVD의 초기 위치를 저장할 배열presum : DVD의 초기 위치를 기준으로 누적합을 저장할 배열T : 세그먼트 트리의 누적합 SUM, 최대값 MAX, 최소값 MIN을 정의할 구조체tree : T타입의 세그먼트 트리를 요소를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = { lst[s], lst[s], ls..

개요본격적인 코드 작성에 앞서 데이터를 수집 및 검증해야할 것이 무엇이 있는지 생각해 보았다. 처음엔 CRUD 트랜잭션 처리를 통해 DB검증부터 로그 수집까지 모든걸 진행할 생각이었다. 하지만 게임 내 발생하는 이벤트 동기화는 Unity Mirror을 통해 진행할 것이므로 이는 좋은 선택이 아니라는 것을 깨달았다. 따라서 게임 내부에서 발생한 로그 관련 데이터는 모두 별도의 로그 서버에서 처리하기로 했고, 나는 회원가입, 로그인 등과 같이 게임의 시작부터 로비에 진입하여 방 생성, 참가, 퇴장 및 게임 시작, 종료등과 같은 이벤트 발생 시 DB검증을 통한 클라이언트 요청 동기화를 담당하기로 했다. 관련하여 초기 엔터티의 개수는 12개였고 각 테이블간 관계도 많이 설정되었었다, 하지만 실제 검증이 필요한 ..

개요2주간의 명세와 MVP 기획 과정을 거친 후 직접 개발을 위한 기술 스택을 정리하는 시간을 가졌다. 우선 가장 크게 우려가 되었던 부분은 멀티 플레이 환경에서의 각 세션간의 동기화를 처리해주는 과정이었다. 클라이언트는 유니티를 사용하기로 결정하였으며, 서버는 지연이 가장 발생하지 않는 소켓 서버를 사용하기로 결정하였다. 직접 데디케이트 소켓 서버를 통해 연결된 모든 유저에게 브로드캐스팅 하는 방법으로 처리하고 싶었지만 프로젝트 기간이 한정되어있는 관계로 해당 부분은 프레임워크를 사용하기로 결정하였다. 선택한 프레임워크는 유니티 미러로 클라이언트 끼리의 동기화를 진행해 주는 기능을 사용하기 쉽게 제공해 준다. 프로젝트를 어느정도 진행하고 나서야 깨달은 것이지만 유니티 미러는 P2P방식으로, 만약 호스트..

개요핀테크와 메타버스 게임 프로젝트 중에서 고민을 하다가 결국 3D 메타버스를 통해 배틀로얄 게임을 구현하는 프로젝트를 시작하였다. 프로젝트 인원은 총 6명으로 클라이언트 3명, 백엔드 3명으로 구성된 팀이다. 멀티 플레이 환경의 게임 프로젝트를 진행하게 되어 기분이 좋다.여담으로 서울에서의 약 60팀 중 우리 팀이 유일하게 메타버스 게임을 선택하였으며, 전국적으로 우리팀을 포함하여 2팀만 메타버스 게임 프로젝트를 선택하였다.  주제선정어떤 게임을 만들지에 대해 약 2주간 명세기간을 가졌다.해당 기간동안 수없이 논의하며 이미 존재하는 레거시 게임을 디벨롭 하는 방향을 잡게 되었다.서로 재밌게 플레이했던 게임들을 브레인스토밍하여 리스트업 하였고 영상 자료등을 참고하여 그 중에서도 몇가지 게임을 추려내었다...

리뷰 https://www.acmicpc.net/problem/1321세그먼트 트리를 활용해 군인을 적절한 부대에 배치시키는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 부대의 개수를 저장할 변수lst : 각 부대의 병사 수를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = lst[s]; else { int mid = (s + e) / 2; build(node * 2, s, mid); build(node * 2 + 1, mid + 1, e); tree[node] = tree[node * 2] + tree[node * 2 + 1]; }} 누적..

리뷰 https://www.acmicpc.net/problem/10090세그먼트 트리를 활용하여 배열 내 자신의 뒷 숫자 중 자기보다 작은 숫자의 개수를 구하는 문제  전역 변수N : 배열의 최대 길이를 저장할 상수 변수n : 배열의 길이를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) 세그먼트 트리의 초기화를 진행할 함수매개 변수로 노드 정보 node, 탐색 구간 s, e를 전달 받는다.기저 조건으로 리프노드에 도달한 경우 현재 노드의 값을 1로 저장해 준다.좌, 우 자식 노드로 재귀를 진행하고, 재귀를 빠져나오며 현재 노드를 두 노드의 합으로 저장해 준다. 2. updatevoid update(int node,..

리뷰 https://www.acmicpc.net/problem/19598회의실의 개수와 관련된 문제들은 일반적인 회의실 문제와 좀 다른 것 같다.  전역 변수n : 회의의 개수를 저장할 변수lst : 회의의 시작과 종료 시간을 저장할 배열 함수없음  문제풀이n값을 입력 받고, n개의 회의의 시작과 종료 시간을 lst배열에 입력 받는다. 이 때 종료시간을 앞에 저장해 준다.lst배열을 오름차순으로 정렬해 준다, 종료 시간 기준으로 오름차순 되어야 한다.멀티셋 dic을 초기화 해주고, 정답을 저장할 변수 ans를 0으로 초기화 해준다.n개의 회의 정보를 순회하며 현재 회의의 시작 시간을 기준으로 dic에서 upper_bound해준다.반환된 이터레이터가 dic의 begin()이라면 dic에 현재 회의의 종료시..

리뷰 https://www.acmicpc.net/problem/25417왠진 모르겠는데 조건문에 ||와 &&를 섞어서 작성 후 제출했었다 어이없게 두번을 틀렸다.  전역 변수lst : 맵 정보를 저장할 2차원 배열v : 방문 정보를 체크할 2차원 배열Pos : 현재 위치 x, y와 소요 시간 t를 정의할 구조체, t를 기준으로 오름차순 정렬한다.dx, dy : 4방향 탐색을 위한 방향 배열 함수1. bfsint bfs(int sx, int sy) 너비 우선 탐색을 통해 출발지 부터 도착지 까지 이동 하는 최소 시간을 구하는 함수매개 변수로 시작 위치의 좌표 sx, sy를 전달 받는다.Pos타입의 우선순위 큐 pq를 초기화 하고, 초기 위치 sx, sy와 소요 시간 0을 push해준다.v배열에 시작 위치를..

리뷰 https://www.acmicpc.net/problem/26086쿼리가 들어왔을 때 마다 처리해 주는건 당연히 시간이 터질 것 같았지만 한번 내봤다.  전역 변수n : 작업 고유번호의 제한값을 저장할 변수q : 쿼리의 개수를 저장할 변수k : 최종 출력할 작업의 인덱스를 저장할 변수deq : 작업 순서를 저장할 덱OP : 작업 종류 op, op가 0일 경우 작업 번호 val을 정의할 구조체ops : 작업 정보를 저장할 OP타입 배열last1 : 마지막 정렬 작업의 인덱스를 저장할 변수 함수없음  문제풀이n, q, k값을 입력 받고, q번의 for문을 개행해 q개의 쿼리를 입력 받아준다.변수 op에 작업의 종류를 입력 받아준다.op가 0일 경우 변수 num에 작업의 고유 번호를 추가로 입력 받은 후..

리뷰 https://www.acmicpc.net/problem/1884다익스트라이지만 고려해야할 요소가 거리 뿐만이 아닌 문제  전역 변수k : 교통비의 값을 저장할 변수n : 도시의 개수를 저장할 변수r : 도로의 개수를 저장할 변수Edge : 간선 정보 다음 노드 nn, 도로의 길이 l, 도로의 통행료 t를 정의할 구조체edges : 간선 정보를 인접 리스트로 저장할 Edge타입 벡터 배열Pos : 시뮬레이션 정보 현재 노드 cn, 현재 길이 cl, 현재까지의 통행료 ct를 정의할 구조체, cl이 동일하면 ct가 작은 순서대로, 아니라면 cl이 작은 순서대로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() 다익스트라를 통해 통행료 한도 내에서 1번 도시에서 N번 도시까지 가는 최..