Google에는 단말기에서 AR 관련 기능이 돌아갈 수 있도록 AR 플랫폼인 ARCore가 있다. 최근 이와 관련한 업데이트가 있어 글로 남겨볼까 한다. ARCore를 사용하여 개발하는 튜토리얼을 보다보면, OpenGL을 직접 사용하지 않고 Sceneform이라는 프레임워크를 사용하여 개발하는 문서가 굉장히 많다. (실제로도 공식 샘플 코드에서 사용한다.) 하지만 관리가 점점 힘들어지는 탓인지, 프로젝트를 closed해버렸고 1.16 버전부터 오픈소스로 전환, archived 해버렸다. (한국 시간 기준으로 5월 15일) [프로젝트 링크] 이렇게 되면 한가지 문제가 있다. Android Studio에는 3D Object를 쉽게 import 하기 위한 플러그인으로, Google Sceneform Tools..

링크: https://www.acmicpc.net/problem/3640문제가중치가 있는 방향 그래프가 주어지고, 1번 정점에서 V번 정점까지 서로 겹치지 않는 2개의 경로 중 비용이 최소인 경우를 출력하는 문제이다. 겹치지 않는 경로를 찾는 것은 최대 유량으로 해결 가능하고, 그 비용이 최소가 되는 것을 구해야하므로, 네트워크 플로우 유형 중에서 MCMF(Min Cost Max Flow; 최소 비용 최대 유량)인 문제이다. 그래프 문제는 항상 문제 조건을 꼼꼼히 살펴야겠다. 이번에도 "출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안 된다." 에서 정점이 겹쳐서는 안되는 조건을 깜빡해서 계속 틀렸다. 이 조건을 무시하면 틀리는 예외 케이스는 아래와 같다. 최대 유량은 1개이고, 답은 ..

링크: https://www.acmicpc.net/problem/15480문제문제 설명은 간단하다.루트를 r로 하는 트리에서 u와 v의 최소공통조상(LCA)를 출력하는 문제이다. LCA(r, u), LCA(r, v), LCA(u, v) 세 개 중에서 깊이가 더 깊은 노드를 출력하면 된다.증명은 사실 안 했는데, 케이스 몇 개를 두고 해보니까 계속 답이었다..혹시나 싶어서 제출해봤더니 정답코드

제목 그대로, 트리의 노드 순서를 다시 정리하여 구간으로 표현하는 것이다. 그림으로 보면, 트리의 구조와 왼쪽과 같았다면, 각 트리의 번호를 오른쪽처럼 변경하는 것이다. 순서는 전위순회(pre-order)로 탐색하면서 번호를 붙이면 된다. 이게 왜 필요할까? 제목에서 이미 말한거지만, 구간으로 표현하는 것이 더 용이할 때 사용한다. 특히 트리를 세그먼트 트리나 펜윅 트리 등의 구간합/부분합으로 변형하여 문제 해결이 필요한 경우이다. 노드의 번호를 위처럼 정리하면, 각 노드가 포괄하는 노드는 항상 확실하다. "자신의 번호 + 그 노드의 서브 트리(들)의 크기"가 포함할 수 있는 자식의 마지막 번호와 같다. 그럼 트리를 일렬로 펴서 다룰 수 있다. 코드 관련 문제 (+스포일러)BOJ 2820 - 자동차 공장..

링크: https://www.acmicpc.net/problem/9034오랜만의 포스팅. 아마 한동안 문제를 풀 시간은 없을 듯.. ㅠ문제매번 \(i\)번 선수에게 더해지는 점수가 주어지고, \(x\)번째 선수가 몇 등인지 실시간으로 출력하는 문제이다. 먼저 어떤 선수의 등수는 "그 선수보다 점수가 더 높은 사람의 수 + 1"이다.매번 탐색을 하거나, 정렬을 한다면 \(100,000\)명의 선수에 대한 \(200,000\)번의 질의에 대답하기엔 시간상으로 버겁다. 내 등수는 구간 [내 점수 + 1, ∞)에 있는 사람의 수 + 1과 같다. 점수의 합은 최대 \(10^{9}\)이므로, 모든 점수를 압축할 필요가 있다. 이건 좌표압축 문제(BOJ 18870 - 좌표 압축)를 먼저 풀어보기를 권장한다.점수가 더..