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번까지의 칸에 맞는 색깔을 하나씩 채우면 된다. 순서대로 색깔을 맞추면서, 맞춰진 색깔의 칸은 움직이지 않도록 고정한다. 빈칸으로 원하는 색깔을 옮기는 것이 또 다른 문제인데, 위 그림과 ..

종종 사용하는 std::binary_search와 그 친구들(lower_bound, upper_bound)의 구현입니다.이 친구들은 헤더에 있습니다. 평소 쓰던 스타일을 그대로 작성하여 올립니다.binary_search가 왜 그 lower_bound와 key가 같은지만 비교하는 지는, 다른 글에서 설명하였다. [보기]코드

저는 quick sort를 기반으로 구현했고, 그 중에서도 중간값이 아닌 (위치가) 중앙에 있는 값을 사용했습니다.이 정도만 구현해도 많은 문제는 생기지 않았습니다. 다만 실제 std::sort 는 구조가 조금 다른 것으로 알고 있습니다. 크기가 100개 이하인 케이스는 insertion sort를 사용하는 등 최적화를 위해서 수정했다고 하네요. template 함수로 작성했기 때문에, 타입은 별도로 명시하지 않아도 됩니다.int형 배열 a[100]에 대해서도, std::sort 함수 쓰듯이 sort(a, a+100) 이라고 호출해도 동작합니다. 이전 게시글에서 구현한 vector를 파라미터로 넘겨도 동작합니다. 즉, sort(vec.begin(), vec.end()) 가능합니다.코드

STL 라이브러리를 사용할 수 없는 환경(시험장 등)에서 vector를 간단하게 구현하는 코드입니다.크기가 동적으로 관리되는, STL 중 정말 많이 사용되는 편리한 sequence container이죠. 큰 기능은 최대한 넣지 않았고, 기존의 vector의 사용 인터페이스와 최소한으로 비슷하게 작성한 것입니다.기본 생성자 몇개와, push_back(), pop_back(), clear() 등의 기본적인 함수가 있고, begin(), end()와 같은 반복자(iterator)들은 실제 반복자는 아니고 비스무리하게만 만들었습니다. 그래도 구조가 같아서, sort(arr.begin(), arr.end()) 를 그대로 사용해도 돌아갑니다.코드