https://www.acmicpc.net/problem/11012 문제 2차원 평면에서 점들의 위치가 주어지고, [left, right]×[bottom, top] 으로 그려지는 사각형 내에 있는 점의 개수를 쿼리마다 출력하는 문제이다. 이 문제는 PST(Persistent Segment Tree)로 해결할 수 있다. PST의 이해를 위해서는 Segment Tree를 먼저 알아야한다. 이 글에서는 자세한 설명은 생략하고, 도움이 될 만한 글로 대체한다. 사실 같은 내용을 이 문제에 대해서만 다시 정리하는 것이라 봐도 무방하다. 혼동이 있을 수 있지만, 이 글에서는(필자는) 세로/수직 방향을 \(y\)축으로 가로/수평 방향을 \(x\)축으로 한다. 즉, \((0,~0)\)은 왼쪽 아래를 의미한다. y축을 ..

오랜만의 코딩으로 풀어보기 시리즈이다. 오늘은 아주 간단하고 쉬운 문제이다. 문제 1부터 9까지의 숫자를 한번씩만 사용해서, 수식을 성립시키는 문제이다. 이런 유형의 문제는 "복면산 문제"라고 불리는 수학 퍼즐의 한 종류이다. 여담이지만, 개인적으로 좋아하는 문제이다. 이와 관련한 알고리즘 문제를 출제한 적도 있다. 완전 탐색류 알고리즘을 연습하기 좋은 문제라고 생각한다. 아래 링크에서 풀어볼 수 있다. BOJ 15811 - 복면산?! (https://www.acmicpc.net/problem/15811) 위 문제는 9개의 숫자와 9개의 알파벳이니 더 쉽다. 1부터 9까지 A부터 I까지 모두 대응시켜보며 만들어지는 세 값이 일치하는 지 확인하면 된다. 즉, 모든 순열을 확인하면 된다. 경우의 수는 \(9..

OS: Windows 10 Shell: Git bash 다른 컴퓨터에서 ssh 키를 가져와서 git에 ssh 키를 등록하려고 했다. 그런데 아래와 같은 오류가 발생했다: $ ssh-add ~/.ssh/id_rsa Error loading key "/c/Users/joonas/.ssh/id_rsa": invalid format 분명 키는 "-----BEGIN OPENSSH PRIVATE KEY-----" 로 시작해서 포맷도 맞았는데, invalid format이라고 하는 것이다. id_rsa 파일을 옮기면서 뭐가 바뀐 게 없는 지 비교해봤다. 이전에 원본 파일의 인코딩은 LF였고, 옮긴 파일은 CRLF라서 포맷을 읽지 못하는 에러였다. CRLF → LF로 다시 저장했더니 정상적으로 등록되었다! $ ssh-..

macOS 10.14.6에서 진행하였다. gtest(Google Test)가 필요해서 설치하려고 하는데, brew에는 패키지가 없는 것 같았다. gtest의 git을 따와서 직접 빌드하던데, brew로 편하게 설치하고 싶으면 아래처럼 진행하면 된다. CMake가 필요하며, brew install cmake 로 설치할 수 있다. 아래 커맨드를 입력하면 설치가 될 것이다. (Kronuz/gtest.rb에서 C++11이 지원되도록 수정하였음) $ brew install --HEAD https://gist.githubusercontent.com/joonas-yoon/9ec4ce1c1374ba8b8473020ced3879d8/raw/gtest.rb 스크립트의 내용은 gist.github.com/joonas-yoo..

빌드 문서는 wiki.qt.io/Building_Qt_5_from_Git#Getting_the_source_code 를 참고하였다. 환경은 macOS 10.14.6 에서 진행하였다. Qt 5는 서브모듈을 무려 45개를 가지고 있다. 그래서 아래 커맨드로 각 서브모듈을 모두 가져오는데, $ perl init-repository 업데이트도 이걸로 한다. (-f 옵션 붙여서) 그런데 내 경우에는 서브모듈들을 가져오는데, 에러가 있었다. 정말 자주 멈췄다. 네트워크 문제인지 모르겠으나, 터미널에서 오브젝트를 받아오는 중에 그대로 멈춰버린다. 그래서 그 모듈을 직접 clone 했다. 클론을 해보려하면 이미 있으니 에러가 있다고 한다. rm -rf 로 지우고 다시 해보면 잘 된다. perl에서 문제가 생긴건지는 모..

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) 세 개 중에서 깊이가 더 깊은 노드를 출력하면 된다.증명은 사실 안 했는데, 케이스 몇 개를 두고 해보니까 계속 답이었다..혹시나 싶어서 제출해봤더니 정답코드