Joonas' Note

종종 사용하는 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()) 를 그대로 사용해도 돌아갑니다.코드

이진 트리 중에서도 힙.힙 중에서도 최소힙을 구현한 코드C++에서 대소비교에 기본값인 less than(

신청 및 안내: https://github.com/NAVER-CAMPUS-HACKDAY 네이버에서 매년 여름과 겨울마다 열리는 핵데이가 올해에도 열렸다. 이번에 웨일 브라우저의 캡처 기능을 확장하여, "화면 녹화 기능 개발"을 하는 주제로 지원하였고 그것이 통과하여 핵데이에 초대받았다. 핵심 역량은 C++과 Windows/Chromium이었지만 지원서에는 과거에 C++로 프로젝트를 진행한 경험(MFC 미로 생성 프로그램)과 C++로 문제 풀이를 주로 해결한 점(BOJ 1800문제)을 중심으로 어필했다. 코딩 테스트는 KT 인적성 검사와 날짜가 정확히 겹쳤는데, 네이버 코딩 테스트는 온라인으로 09시~18시 중 선택으로 3시간 동안 진행하는 방식이라 두 테스트 모두 치를 수 있었다. 역시 IT 회사라 온라..

요구사항 최소 8GB RAM, 권장 16GB RAM 100GB 디스크 공간 Visual Studio 2017 이상 Windows 7 이상 환경 설정 Visual Studio Desktop development with C++ (C++를 사용한 데스크탑 개발) MFC/ATL support (x86 및 x64용 Visual C++ MFC) 워크로드에서 위 항목들을 설치해야 합니다. VS 2017 이상부터는 Visual Studio Installer에서 설치할 수 있습니다. Windows 10 SDK https://developer.microsoft.com/ko-kr/windows/downloads/sdk-archive 버전 10.0.17134 이상 (선택) SDK Debugging Tools Window 1..

네임스페이스 std 아래에 있는 함수 getline은 한 줄 단위로 입력 받으며, 스페이스와 탭 등의 공백 문자들도 그대로 유지된다.하지만 C++ 레퍼런스[1][2]에서는 공백에 대한 예제는 잘 나와있지 않아서 글로 남긴다. 아래 코드로 여러 케이스를 확인해보자. test-getline-input.txt에 적힌대로 입력하면, test-getline-output.txt와 같은 출력을 확인할 수 있다. ^는 문자열의 시작을, $는 문자열의 끝을 표시하기 위해 사용했다.공백 문자와 탭 문자가 포함된 문자열들, 심지어는 길이가 0인 문자열도 모두 잘 입력되는 걸 확인할 수 있다.

Red Black Tree란, Binary Search Tree의 일종으로 입력 순서에 따라 BST가 한쪽으로 기울어지는(skewed) 걸 막기 위해 스스로 균형을 맞추는(self-balanced) 트리이다. 트리가 skewed하면 연결리스트랑 다를 바 없어서 \(O(N)\)의 시간복잡도를 갖기 때문이다. 균형을 맞춘다는 것은 어떤 노드의 (자신 아래의) 모든 리프까지의 거리가 최대한 같도록 조정한다는 말인데, 균형을 잘 맞추면 트리의 깊이가 \( \log_{2}{N} \)이기 때문에 빠르게 검색할 수 있다. 레드블랙트리는 아래의 규칙을 만족하도록 조정된다. 1. 노드는 레드 혹은 블랙 중의 하나이다. 2. 루트 노드는 블랙이다. 3. 모든 리프 노드는 블랙이다. 4. 레드 노드의 자식노드 양쪽은 언제나..