전체 글 (277) 썸네일형 리스트형 백준 2040 - 수 게임 https://www.acmicpc.net/problem/2040 이 문제는 대단히 교육적인 문제이므로 꼭 공부하는 것을 추천한다. 게임 전략 A와 B 둘 다 최적으로 플레이를 한다고 했다. 이를 수식으로 표현하면 어떻게 될까? A의 합을 $sum_{A}$, B의 합을 $sum_{B}$라고 하면 A와 B의 목표는 다음과 같이 정리할 수 있다. A는 $sum_{A} - sum_{B}$를 최소화시켜야 한다. B는 $sum_{A} - sum_{B}$를 최대화시켜야 한다. (혹은 $sum_{B} - sum_{A}$를 최소화시켜야 한다.) 그러면 저 값을 최적화 하는 문제로 표현할 수 있고 이는 동적 계획법으로 시도해볼 수 있을 것이다. 그런데 어떻게 동적 계획법을 해야 할까? 테이블을 다음과 같이 정의한다. d.. 유니티 Raycast로 3D 오브젝트 클릭과 드래그 https://github.com/nicotina04/UnityDrag3DObject GitHub - nicotina04/UnityDrag3DObject: An implementation of dragging object and it's example An implementation of dragging object and it's example - GitHub - nicotina04/UnityDrag3DObject: An implementation of dragging object and it's example github.com 이번 포스팅에서는 씬에 존재하는 3D 오브젝트를 마우스로 클릭, 그리고 드래그하는 방법을 알아본다. 그전에 어떻게 마우스의 입력이 게임 내의 오브젝트와 상호작용할 수 있는지 .. pb_ds의 간단한 고찰 - 트리 구현체 PS를 좀 오래 한 사람이라면 pb_ds의 존재를 알고 있을 것이다. 그리고 보통 트리의 구현체로 r-b 트리인 rb_tree_tag를 쓸 것이다. 하지만 r-b 트리 외에도 스플레이 트리 구현체인 splay_tree_tag가 존재한다. C++ 상에서 구현된 r-b 트리는 상수가 크다고 알려져 있는데 그럼 스플레이 트리를 대신 쓰면 성능이 좀 좋아질까? 그래서 해보았다. 백준 2104 - 스플레이 트리 http://boj.kr/1404da72672b4c429dfc8f2504ff4558 백준 2104 - r-b 트리 http://boj.kr/b9c4a1b73379447192b2c6153f223525 무려 스플레이 트리가 2배 더 빠르다! 그러면 다른 문제로 확인해보자. 백준 1572 - 스플레이 트리 ht.. 유니티 Procedural Cave Gerneration 랜덤 동굴 생성 1 유니티 버전 2021.3.9f1 들어가기 전 참고 이 포스트는 아래의 동영상의 내용을 한국어로 재구성한 자료이다. 어느 정도 영어 청취가 가능하다면 동영상을 봐도 좋다. https://youtu.be/v7yyZZjF1z4 이 포스트는 유니티 엔진에서 셀룰러 오토마타 기반으로 동굴 지형을 생성하는 cave generation을 다룰 것이다. 에피소드 1에서는 직접 동굴을 만들기 전 기즈모를 이용해 대략적인 모습을 보여주는 것을 목표로 한다. 필요 변수 세팅 필요한 변수는 다음과 같다. int width, height: 맵의 너비와 높이다. bool useRandomSeed: 랜덤에 시드를 직접 부여할지 안 할지 고르는 변수다. int randomFillPercent: 초기에 맵을 위와 같은 흑색을 어느 정.. 2차원 평면에서 모든 점 쌍의 유클리드 거리 합 구하기 오늘은 이런 문제를 풀어보자. 2차원 직교 좌표계에서 N개의 점이 있다. ($N \leq 10^{6}$) 좌표가 동일한 두 점이 존재할 수 있다. i번째 점을 $p_{i}$라 하고 i번째 점과 j번째 점의 유클리드 거리 제곱을 $dist(p_{i}, p_{j})$라고 했을 때 다음을 구하시오. $\sum\limits^{N - 1}_{i = 1}\sum\limits^{N}_{j = i + 1} dist(p_{i}, p_{j})$ 지금 생각할 수 있는 간단한 방법은 $\binom{N}{2}$의 쌍의 거리를 일일이 계산하는 것이다. 하지만 그런 걸로 되면 이 글을 쓸 필요도 없다. N이 100만까지 갈 수 있으므로 컴퓨팅으로는 빠른 계산이 당연히 어렵다. 이 포스트에서는 이 문제를 무려 $O(N)$에 풀어볼 .. 이전 1 2 3 4 5 6 ··· 56 다음
