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

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

링크: https://www.acmicpc.net/problem/1539문제주어진 순서대로 이진 검색 트리를 구축하였을 때, 모든 노드들의 높이 합을 출력하는 문제이다. 9 다음에 1이 주어지면, 위와 같은 그림일 것이다.다음으로 4가 들어오면 \(x\) 위치로 갈 텐데, 이전에 등장한 수 중에서, 자신보다 바로 작거나 바로 큰 수의 높이 중 더 큰쪽 + 1이 자신의 높이이다. 만약 \(y\) 자리에 무엇이 있다고 해도, \(x < 9 < y\) 임은 항상 보장되므로, 자신보다 바로 작거나 큰 수만 비교하면 된다.코드

2020/03/19 - [개발/C++] - [C++ STL] binary_search, upper_bound, lower_bound 구현하기 [C++ STL] binary_search, upper_bound, lower_bound 구현하기 종종 사용하는 std::binary_search와 그 친구들(lower_bound, upper_bound)의 구현입니다. 이 친구들은 헤더에 있습니다. 평소 쓰던 스타일을 그대로 작성하여 올립니다. binary_search가 왜 그 lower.. joonas.tistory.com binary_search는 찾는 key와 lower_bound 위의 값이 같은지만 확인하면 된다. 따라서 아래처럼 구현할 수 있다. bool binary_search(int arr[], int..

작년 말에 GitHub에 액션(Actions)이라는 기능이 추가되었다. 이제 GitHub에서는 자체적으로 CI 기능을 제공한다. 그 전에는 Travis-CI 아니면 CircleCI에서 빌드 & 테스트를 하고, 그 상태를 위 같은 배지 이미지로 표시했는데, 이제 직접 제공하면서 더 간편해졌다. 환경 변수를 암호화해서 Travis-CI에서 빌드하는 그런 기능까지 있는지는 써보면서 확인을 해봐야겠다. (aws나 google api key 때문에.. 이거 암호화하는 거 꼭 필요함..) CI + Chrome WebDriver + pytest 배포 전에는 미리 배포 환경으로 테스트하면서 종종 사용하는데, 이번에는 문제가 생겼다. 분명 Windows 10에서는 Chrome WebDriver 사용하는 selenium ..

Palindromic tree 영문 글 - http://adilet.org/blog/palindromic-tree/ 두 문자열 S, P의 공통 부분 문자열이면서, 팰린드롬인 문자열의 개수를 구하는 자료구조이다. 관련 문제로는:2014-2015 ACM-ICPC, Asia Xian Regional - Problem G. The Problem to Slow Down You가 있다. Mikhail Rubinchik라는 유저가 고안한 자료구조라고 한다.삼성 소멤에서 shjgkwo님이 정리해준 한국어 문서도 있다. (https://www.secmem.org/blog/2019/05/17/Palindromic-Tree/)

링크: https://www.acmicpc.net/problem/18109 문제 한글 두벌식 자판으로 타이핑할 때, 다음 글자의 초성 자음이 이전 글자의 받침으로 미리 작성되는 경우를 구하는 문제이다.자세한 예시는 문제에 자세히 나와있으니 생략한다. 풀이처음에는 영문 모드로 작성한 아무 문자열이 입력으로 들어오는 줄 알았다.그래서 모든 케이스에 대해 고려하다보니, 오토마타를 그리게 되었는 데 아래와 같다. 나중에 다시 보니 항상 "완성형 한글"이 입력되는 꼴만 입력되더라... (모음 'ㅏ'키인 k 가 대문자 K로 적히는 경우도 없었다)여기서 합성모음은 반모음+반모음(ㅘ, ㅝ)와 둘레모음+반모음(ㅞ, ㅙ) 등을 간략히 표현한 것이다. (알맞은 표현을 알려주시면 감사합니다)화살표에서 겹받침은 ㄳ, ㄼ 등으로..

게임하러 가기: https://joonas-yoon.github.io/rubik-s-race/ Rubik's Race Move the tiles, Solve the puzzle! joonas-yoon.github.io 개발기: https://joonas.tistory.com/120 게임을 계속 해보면, 사람의 직관으로 풀리기는 한다. 이러한 직관을 나름 생각해본 알고리즘(풀이) 글로 옮길까한다. 풀이 먼저, 게임의 목표는 주어진 3x3 패턴에 맞게 5x5의 중앙에 위치한 3x3 자리를 똑같게 만드는 것이다. 1번부터 9번까지의 칸에 맞는 색깔을 하나씩 채우면 된다. 순서대로 색깔을 맞추면서, 맞춰진 색깔의 칸은 움직이지 않도록 고정한다. 빈칸으로 원하는 색깔을 옮기는 것이 또 다른 문제인데, 위 그림과 ..