링크: 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로 적히는 경우도 없었다)여기서 합성모음은 반모음+반모음(ㅘ, ㅝ)와 둘레모음+반모음(ㅞ, ㅙ) 등을 간략히 표현한 것이다. (알맞은 표현을 알려주시면 감사합니다)화살표에서 겹받침은 ㄳ, ㄼ 등으로..